Stack Implementation Using Array in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a stack in data structures?

A stack is a collection of elements that follows the Last In, First Out (LIFO) principle. The last element added is the first one to be removed.

beginner

What are the main operations of a stack?

The main operations are:
1. Push: Add an element to the top.
2. Pop: Remove the top element.
3. Peek/Top: View the top element without removing it.
4. IsEmpty: Check if the stack is empty.

intermediate

How is a stack implemented using an array?

A stack can be implemented using an array by keeping a variable (top) to track the index of the last added element. Push adds an element at top+1, Pop removes the element at top, and top is updated accordingly.

intermediate

What happens when you try to push an element into a full stack implemented with an array?

This situation is called stack overflow. Since the array has a fixed size, no more elements can be added beyond its capacity.

beginner

What is the time complexity of push and pop operations in a stack implemented using an array?

Both push and pop operations have a time complexity of O(1) because they involve adding or removing an element at the top index without shifting other elements.

Which principle does a stack follow?

A First In, First Out (FIFO)

B Last In, First Out (LIFO)

C Random Access

D Priority Based

A stack follows the Last In, First Out (LIFO) principle where the last element added is the first to be removed.

In a stack implemented using an array, what does the 'top' variable represent?

A The first element in the stack

B The total size of the array

C The index of the last added element

D The number of empty spaces

'top' keeps track of the index of the last added element in the stack.

What happens if you pop from an empty stack?

A Stack underflow error

B Stack overflow error

C Adds a new element

D Nothing happens

Popping from an empty stack causes a stack underflow error because there are no elements to remove.

What is the time complexity of the push operation in a stack using an array?

A O(log n)

B O(n)

C O(n^2)

D O(1)

Push operation is O(1) because it adds an element at the top index without shifting other elements.

Which condition indicates that a stack implemented with an array is full?

A top == size - 1

B top == 0

C top == -1

D top > size

When top equals size - 1, the stack is full because the array is filled up to its last index.

Explain how to implement a stack using an array and how push and pop operations work.

Think about how you keep track of the last added element and how you add or remove elements.

Describe what stack overflow and stack underflow mean in the context of stack implementation using arrays.

Consider what happens when you try to add or remove elements beyond the stack's limits.

Practice

1. What is the main purpose of using an array in stack implementation?

easy

A. To store elements in a fixed-size linear structure

B. To allow random access to elements anywhere

C. To sort elements automatically

D. To store elements in a tree-like structure

Solution

1. Step 1: Understand stack storage

   A stack stores elements in a linear order, last-in first-out (LIFO).

2. Step 2: Role of array in stack

   An array provides a fixed-size linear structure to hold stack elements efficiently.

3. Final Answer:

   To store elements in a fixed-size linear structure -> Option A

4. Quick Check:

   Stack uses array for fixed linear storage [OK]

Hint: Stack uses array for fixed linear storage [OK]

Common Mistakes:

• Confusing stack with queue or tree
• Thinking array sorts elements automatically
• Assuming stack allows random access

2. Which of the following is the correct syntax to declare a stack array of size 10 in C++?

easy

A. stack int[10];

B. int stack[10];

C. int stack();

D. array stack[10];

Solution

1. Step 1: Recall C++ array declaration syntax

   In C++, arrays are declared as: type name[size];

2. Step 2: Match with options

   int stack[10]; matches correct syntax: int stack[10];

3. Final Answer:

   int stack[10]; -> Option B

4. Quick Check:

   C++ array declaration = int stack[10]; [OK]

Hint: Array declaration: type name[size]; [OK]

Common Mistakes:

• Using parentheses instead of brackets
• Wrong order of type and name
• Using non-existent 'array' keyword

3. What will be the output after executing the following code?

int stack[5];
int top = -1;
// Push 10
stack[++top] = 10;
// Push 20
stack[++top] = 20;
// Pop
int x = stack[top--];
// Push 30
stack[++top] = 30;
// Print top element
std::cout << stack[top];

medium

A. Runtime error

B. 20

C. 10

D. 30

Solution

1. Step 1: Trace stack operations step-by-step

   Initially top = -1.
   Push 10: top=0, stack[0]=10
   Push 20: top=1, stack[1]=20
   Pop: x=stack[1]=20, top=0
   Push 30: top=1, stack[1]=30

2. Step 2: Identify top element after operations

   Top is 1, stack[1] = 30, so output is 30.

3. Final Answer:

   30 -> Option D

4. Quick Check:

   Last pushed after pop is 30 [OK]

Hint: Track top index changes carefully [OK]

Common Mistakes:

• Confusing push and pop order
• Not updating top correctly
• Assuming pop removes element permanently

4. Identify the error in the following stack push function using array:

void push(int stack[], int &top, int size, int value) {
  if (top == size) {
    std::cout << "Stack Overflow";
    return;
  }
  stack[++top] = value;
}

medium

A. No error, function is correct

B. The increment of top should be after assignment

C. The condition should be 'top == size - 1' to check overflow

D. The function should return a value

Solution

1. Step 1: Understand overflow condition

   Array indices go from 0 to size-1, so top can be max size-1.

2. Step 2: Check condition in code

   Condition 'top == size' is wrong; it should be 'top == size - 1' to prevent overflow.

3. Final Answer:

   The condition should be 'top == size - 1' to check overflow -> Option C

4. Quick Check:

   Overflow check uses top == size - 1 [OK]

Hint: Array max index = size - 1 for overflow check [OK]

Common Mistakes:

• Checking top == size instead of size - 1
• Incrementing top incorrectly
• Ignoring overflow condition

5. Given a stack implemented using an array of size 4, what will be the state of the stack after these operations?

push(5); push(10); pop(); push(15); push(20); push(25); pop();

Assume stack is initially empty and top = -1. Choose the correct stack content from bottom to top.

hard

A. 5 -> 15 -> 20 -> null

B. 5 -> 10 -> 15 -> 20 -> null

C. 5 -> 15 -> 20 -> 25 -> null

D. 10 -> 15 -> 20 -> null

Solution

1. Step 1: Execute operations step-by-step

   Start: top = -1, stack empty.
   push(5): top=0, stack[0]=5
   push(10): top=1, stack[1]=10
   pop(): removes 10, top=0
   push(15): top=1, stack[1]=15
   push(20): top=2, stack[2]=20
   push(25): top=3, stack[3]=25 (stack full)
   pop(): removes 25, top=2

2. Step 2: Final stack content

   Stack from bottom to top: 5 (index 0), 15 (index 1), 20 (index 2). So output is 5 -> 15 -> 20 -> null.

3. Final Answer:

   5 -> 15 -> 20 -> null -> Option A

4. Quick Check:

   Track push/pop changes carefully [OK]

Hint: Write each push/pop step to track stack state [OK]

Common Mistakes:

• Ignoring pop effects on top
• Assuming stack grows beyond size
• Confusing order of elements