Stack Implementation Using Array in DSA C++ - Execution Trace

Concept Flow - Stack Implementation Using Array

Start

↓

Check if stack is full?

Yes→Cannot push, overflow

No↓

Push element: top = top + 1, arr[top

↓

Check if stack is empty?

Yes→Cannot pop, underflow

No↓

Pop element: element = arr[top

↓

Peek element: return arr[top

↓

End

This flow shows how elements are added (push) and removed (pop) from the stack using an array, checking for overflow and underflow conditions.

Execution Sample

DSA C++

int stack[5];
int top = -1;
// Push 10
if(top < 4) stack[++top] = 10;
// Push 20
if(top < 4) stack[++top] = 20;
// Pop
if(top >= 0) top--;

This code pushes 10 and 20 onto the stack and then pops the top element.

Execution Table

Step	Operation	Top Index	Stack Array State	Pointer Changes	Visual State
1	Initialize stack	-1	[_, _, _, _, _]	top = -1	Empty stack
2	Push 10	0	[10, _, _, _, _]	top: -1 -> 0	10 -> null
3	Push 20	1	[10, 20, _, _, _]	top: 0 -> 1	10 -> 20 -> null
4	Pop	0	[10, 20, _, _, _]	top: 1 -> 0	10 -> null
5	End	0	[10, 20, _, _, _]	No change	10 -> null

💡 Execution stops after pop operation; top is 0, stack has one element 10.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
top	-1	0	1	0	0
stack	[_, _, _, _, _]	[10, _, _, _, _]	[10, 20, _, _, _]	[10, 20, _, _, _]	[10, 20, _, _, _]

Key Moments - 3 Insights

Why does top start at -1 instead of 0?

Top starts at -1 to indicate the stack is empty before any push. In execution_table step 1, top = -1 means no elements are in the stack.

What happens if we try to push when top is already at max index?

If top equals max index (4 here), pushing causes overflow and is prevented. This is shown in concept_flow where 'Check if stack is full?' leads to 'Cannot push, overflow'.

Why does popping only decrease top without clearing the array element?

Popping just moves top down to ignore the last element. The array slot remains but is considered invalid. Execution_table step 4 shows top moves from 1 to 0, effectively removing 20.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the top index and stack state?

A top = 1, stack = [10, 20, _, _, _]

B top = 0, stack = [10, _, _, _, _]

C top = 2, stack = [10, 20, _, _, _]

D top = -1, stack = [_, _, _, _, _]

💡 Hint

Refer to execution_table row with Step 3 for top and stack array state.

At which step does the stack become empty again?

A Step 2

B Step 3

C Step 4

D Stack never becomes empty

💡 Hint

Check variable_tracker for top values; top never returns to -1 after step 1.

If we push another element after step 4, what will be the new top index?

A 0

B 1

C 2

D 3

💡 Hint

After step 4, top is 0; pushing increments top by 1.

Concept Snapshot

Stack using array:
- Use array and 'top' index
- top = -1 means empty
- Push: top++, arr[top] = value
- Pop: top-- (no erase needed)
- Check overflow (top == max) and underflow (top == -1)

Full Transcript

This visualization shows how a stack is implemented using an array and a top pointer. Initially, top is -1 indicating an empty stack. When pushing, top increases by one and the new element is stored at arr[top]. When popping, top decreases by one, effectively removing the top element. Overflow is prevented by checking if top reached the maximum index, and underflow by checking if top is -1. The execution table traces pushing 10 and 20, then popping once, showing how the stack and top change step-by-step.

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