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↓

Increment top pointer

↓

Push element at top index

↓

Done

↓

Start

↓

Check if stack is empty?

Yes→Cannot pop, underflow

No↓

Return element at top index

↓

Decrement top pointer

↓

Done

The flow shows how push checks for overflow before adding an element and incrementing top, and pop checks for underflow before decrementing top and returning the element.

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	-1 -> 0	[10, _, _, _, _]	top incremented to 0	10 -> _ -> _ -> _ -> _ -> null
3	Push 20	0 -> 1	[10, 20, _, _, _]	top incremented to 1	10 -> 20 -> _ -> _ -> _ -> null
4	Pop	1 -> 0	[10, 20, _, _, _]	top decremented to 0	10 -> _ -> _ -> _ -> _ -> null
5	End	0	[10, 20, _, _, _]	No change	10 -> _ -> _ -> _ -> _ -> null

💡 Execution stops after pop operation; top is 0 indicating one element left.

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. When we push, top increments first to 0, pointing to the first element. This is shown in execution_table rows 1 and 2.

Why do we increment top before assigning the new element in push?

Incrementing top first moves the pointer to the next free position. Then we assign the element there. This prevents overwriting existing elements. See execution_table rows 2 and 3.

After popping, why does the element remain in the array?

Pop only decrements top; it doesn't erase the value. The element is considered removed because top no longer points to it. This is visible in execution_table row 4.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the value of top?

A 0

B 1

C -1

D 2

💡 Hint

Check the 'Top Index' column at step 3 in the execution_table.

At which step does the stack have only one element?

A Step 2

B Step 3

C Step 4

D Step 1

💡 Hint

Look at the 'Visual State' column and 'Top Index' to see how many elements are in the stack.

If we try to push when top is 4, what happens according to the concept_flow?

A Push succeeds and top becomes 5

B Push fails due to overflow

C Pop operation is performed instead

D Stack resets to empty

💡 Hint

Refer to the concept_flow where it checks if stack is full before pushing.

Concept Snapshot

Stack using array:
- Use an array and a 'top' index starting at -1.
- Push: increment top, then add element.
- Pop: return element at top, then decrement top.
- Check overflow (top == max size -1) before push.
- Check underflow (top == -1) before pop.

Full Transcript

This visualization shows how a stack is implemented using an array and a top pointer. The top starts at -1 to indicate the stack is empty. When pushing, top increments first to point to the next free slot, then the element is stored there. When popping, the element is not erased but top decrements to exclude it from the stack. Overflow and underflow checks prevent invalid operations. The execution table traces pushing 10 and 20, then popping once, showing how the stack array and top pointer 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 in the stack

C. To automatically resize the stack when full

D. To sort elements in ascending order

Solution

1. Step 1: Understand stack storage

   A stack stores elements in a linear order where the last added element is accessed first.

2. Step 2: Role of array in stack

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

3. Final Answer:

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

4. Quick Check:

   Array = fixed-size linear storage [OK]

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

Common Mistakes:

• Thinking array allows automatic resizing
• Confusing stack with random access structures
• Assuming array sorts elements automatically

2. Which of the following is the correct way to declare a stack array of size 5 in C?

easy

A. int[5] stack;

B. int stack[5];

C. stack int[5];

D. array stack = int[5];

Solution

1. Step 1: Recall C array declaration syntax

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

2. Step 2: Match syntax with options

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

3. Final Answer:

   int stack[5]; -> Option B

4. Quick Check:

   C array declaration = int stack[5]; [OK]

Hint: C arrays declared as type name[size]; [OK]

Common Mistakes:

• Placing type after variable name
• Using incorrect keywords like 'array'
• Misplacing brackets in declaration

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

int stack[3];
int top = -1;
// Push 10
stack[++top] = 10;
// Push 20
stack[++top] = 20;
// Pop
int x = stack[top--];
printf("%d", stack[top]);

medium

A. Runtime error

B. 20

C. 10

D. Garbage value

Solution

1. Step 1: Trace push operations

   Initially top = -1.
   Push 10: top becomes 0, stack[0] = 10.
   Push 20: top becomes 1, stack[1] = 20.

2. Step 2: Trace pop and print

   Pop: x = stack[1] = 20, then top becomes 0.
   Print stack[top] = stack[0] = 10.

3. Final Answer:

   10 -> Option C

4. Quick Check:

   After pop, top points to 10 [OK]

Hint: Pop decreases top, print uses updated top [OK]

Common Mistakes:

• Printing popped element instead of current top
• Confusing pre-increment and post-decrement
• Assuming top points beyond last element

4. Identify the error in this stack push function and select the fix:

void push(int stack[], int *top, int size, int value) {
    if (*top == size) {
        printf("Stack Overflow\n");
        return;
    }
    stack[++(*top)] = value;
}

medium

A. No error, code is correct

B. Change condition to *top == size + 1

C. Change stack[++(*top)] to stack[(*top)++]

D. Change condition to *top == size - 1

Solution

1. Step 1: Understand top indexing in stack

   Top starts at -1, max index is size - 1.
   When top == size - 1, stack is full.

2. Step 2: Analyze overflow condition

   Condition *top == size is wrong; it should be *top == size - 1 to detect full stack.

3. Final Answer:

   Change condition to *top == size - 1 -> Option D

4. Quick Check:

   Overflow when top reaches size-1 [OK]

Hint: Top max index is size-1, not size [OK]

Common Mistakes:

• Checking top == size instead of size-1
• Misusing increment operators in array indexing
• Ignoring zero-based indexing

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

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

Assume top starts at -1 and push/pop update top accordingly. Choose the correct final stack content from bottom to top.

hard

A. 5 -> 15 -> 25 -> null

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

C. 10 -> 15 -> 25 -> null

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

Solution

1. Step 1: Trace each operation 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
   pop(): removes 20, top=1
   push(25): top=2, stack[2]=25

2. Step 2: Final stack content

   Stack from bottom (index 0) to top (index 2): 5, 15, 25

3. Final Answer:

   5 -> 15 -> 25 -> null -> Option A

4. Quick Check:

   Push/pop update top correctly [OK]

Hint: Track top index after each push/pop [OK]

Common Mistakes:

• Forgetting to update top after pop
• Assuming pop removes bottom element
• Mixing order of elements after operations