Stack Implementation Using Array in DSA Python - Execution Trace

Concept Flow - Stack Implementation Using Array

Start

↓

Check if stack is full?

Yes→Cannot push, overflow

No↓

Add element at top index

↓

Increment top pointer

↓

Check if stack is empty?

Yes→Cannot pop, underflow

No↓

Remove element at top-1 index

↓

Decrement top pointer

↓

Peek element at top-1 index

↓

End

The stack uses an array and a top pointer. Push adds element at top and increments top. Pop removes element at top-1 and decrements top. Peek reads element at top-1.

Execution Sample

DSA Python

stack = []
top = 0
stack.append(10); top += 1
stack.append(20); top += 1
popped = stack.pop(); top -= 1
peek = stack[top-1]

This code pushes 10 and 20 onto the stack, pops the top element, then peeks at the current top.

Execution Table

Step	Operation	Top Pointer	Stack Array	Action Description	Visual State
1	Initialize stack	0	[]	Start with empty stack	[]
2	Push 10	1	[10]	Add 10 at index 0, increment top to 1	[10] (top=1)
3	Push 20	2	[10, 20]	Add 20 at index 1, increment top to 2	[10, 20] (top=2)
4	Pop	1	[10]	Remove element at top-1 (index 1), decrement top to 1	[10] (top=1)
5	Peek	1	[10]	Read element at top-1 (index 0), value=10	[10] (top=1)
6	Pop	0	[]	Remove element at top-1 (index 0), decrement top to 0	[] (top=0)
7	Pop	0	[]	Cannot pop, stack empty (underflow)	[] (top=0)

💡 Execution stops after underflow on pop when stack is empty (top=0).

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7
top	0	1	2	1	1	0	0
stack	[]	[10]	[10, 20]	[10]	[10]	[]	[]

Key Moments - 3 Insights

Why does the top pointer increment after push but decrement after pop?

Because top points to the next free position in the array. After push, top moves up to next free slot (see Step 2 and 3). After pop, top moves down to reflect removal (see Step 4 and 6).

Why do we access stack[top-1] when peeking or popping?

Because top points to the next free position, so the last element is at top-1 index (see Step 4 and 5 in execution_table).

What happens if we try to pop when the stack is empty?

The pop operation cannot proceed and results in underflow (see Step 7). The stack remains empty and top stays at 0.

Visual Quiz - 3 Questions

Look at the execution table, what is the value of top after pushing 20?

A 1

B 2

C 0

D 3

💡 Hint

Check Step 3 in the execution_table under 'Top Pointer'

At which step does the stack become empty again after popping all elements?

A Step 4

B Step 5

C Step 6

D Step 7

💡 Hint

Look at Step 6 where top becomes 0 and stack is []

If we try to pop when top is 0, what happens according to the execution table?

A Pop removes an element

B Stack overflows

C Underflow error, cannot pop

D Top increments

💡 Hint

See Step 7 where pop is attempted on empty stack

Concept Snapshot

Stack using array:
- Use array and top pointer
- Push: add element at top, top++
- Pop: remove element at top-1, top--
- Peek: read element at top-1
- top points to next free slot
- Underflow if pop when empty

Full Transcript

This visualization shows how a stack is implemented using an array and a top pointer. The top pointer always points to the next free position in the array. When pushing, the element is added at the current top index and then top is incremented. When popping, the element at top-1 is removed and top is decremented. Peeking reads the element at top-1 without changing top. The execution table traces each operation step-by-step, showing the stack array and top pointer changes. Key moments clarify why top increments and decrements, why we access top-1 index, and what happens on underflow. The visual quiz tests understanding of top pointer values and stack empty conditions.

Practice

1. What is the main purpose of using an array to implement a stack?

easy

A. To allow random access to elements

B. To store elements in a first-in, first-out (FIFO) order

C. To sort elements automatically

D. To store elements in a last-in, first-out (LIFO) order

Solution

1. Step 1: Understand stack behavior

   A stack stores elements so that the last element added is the first one removed, called LIFO.

2. Step 2: Role of array in stack

   An array helps store elements in order and access the last added element easily for push/pop operations.

3. Final Answer:

   To store elements in a last-in, first-out (LIFO) order -> Option D

4. Quick Check:

   Stack = LIFO [OK]

Hint: Stack means last-in, first-out order [OK]

Common Mistakes:

• Confusing stack with queue (FIFO)
• Thinking array sorts elements automatically
• Assuming random access is main stack feature

2. Which of the following is the correct way to initialize an empty stack using an array in Python?

easy

A. stack = []

B. stack = {}

C. stack = ()

D. stack = null

Solution

1. Step 1: Identify Python data types for stack

   An array-like structure for stack is a list, initialized with square brackets [].

2. Step 2: Check each option

   stack = [] uses [], which is a list. stack = {} is a dictionary, () is a tuple, null (no data).

3. Final Answer:

   stack = [] -> Option A

4. Quick Check:

   Empty list = empty stack [OK]

Hint: Use [] to create empty list for stack [OK]

Common Mistakes:

• Using {} which creates a dictionary
• Using () which creates a tuple
• Assigning null instead of a list

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

stack = []
stack.append(10)
stack.append(20)
stack.pop()
print(stack)

medium

A. [10, 20]

B. [20]

C. [10]

D. []

Solution

1. Step 1: Trace push operations

   stack.append(10) adds 10, stack becomes [10]. Then stack.append(20) adds 20, stack becomes [10, 20].

2. Step 2: Trace pop operation

   stack.pop() removes last element 20, stack becomes [10].

3. Final Answer:

   [10] -> Option C

4. Quick Check:

   Pop removes last item, stack left with [10] [OK]

Hint: Pop removes last pushed element [OK]

Common Mistakes:

• Thinking pop removes first element
• Confusing append with insert
• Expecting stack to be empty after pop

4. Identify the error in the following stack implementation code:

stack = []
stack.push(5)
stack.append(10)
print(stack)

medium

A. 'push' method does not exist for list

B. Missing initialization of stack

C. Cannot append to list

D. print statement syntax error

Solution

1. Step 1: Check list methods

   Python lists use append() to add elements, not push().

2. Step 2: Identify error

   stack.push(5) causes AttributeError because 'push' is not a list method.

3. Final Answer:

   'push' method does not exist for list -> Option A

4. Quick Check:

   Use append(), not push() for list [OK]

Hint: Use append() to add elements to list [OK]

Common Mistakes:

• Using push() instead of append()
• Assuming push() is valid for Python lists
• Ignoring error messages

5. Given a stack implemented using an array, how can you check if the stack is empty before popping an element to avoid errors?

hard

A. Check if stack is null

B. Check if stack's length is zero using len(stack) == 0

C. Try popping and catch exceptions if stack is empty

D. Use stack[0] == null to check emptiness

Solution

1. Step 1: Understand stack emptiness check

   To avoid errors, check if stack has no elements by verifying its length is zero.

2. Step 2: Evaluate options

   Check if stack's length is zero using len(stack) == 0 correctly checks length with len(stack) == 0. Try popping and catch exceptions if stack is empty is valid but less efficient. Check if stack is null checks null which is incorrect. Use stack[0] == null to check emptiness checks first element which may cause error if empty.

3. Final Answer:

   Check if stack's length is zero using len(stack) == 0 -> Option B

4. Quick Check:

   Empty stack means length zero [OK]

Hint: Use len(stack) == 0 to check empty stack [OK]

Common Mistakes:

• Checking stack is null instead of empty
• Accessing stack[0] without checking length
• Relying only on try-except without condition