Stack Implementation Using Array in DSA Python

Mental Model

A stack is a collection where you add and remove items only from the top, like a stack of plates.

Analogy: Imagine a stack of plates in your kitchen: you can only add a new plate on top or take the top plate off.

Top
 ↑
[ ] -> [ ] -> [ ] -> null
Bottom

Dry Run Walkthrough

Input: Create an empty stack, then push 10, push 20, pop once, push 30

Goal: Show how the stack changes with each push and pop operation

Step 1: Push 10 onto the stack

Top -> [10] null

Why: We add the first item, so it becomes the top

Step 2: Push 20 onto the stack

Top -> [10, 20] null

Why: New item goes on top, so 20 is now the top

Step 3: Pop the top item (20) from the stack

Top -> [10] null

Why: Remove the top item to get back to previous state

Step 4: Push 30 onto the stack

Top -> [10, 30] null

Why: Add new item on top again

Result:

Top -> [10, 30] null

Annotated Code

DSA Python

class Stack:
    def __init__(self, capacity=10):
        self.capacity = capacity
        self.array = [None] * capacity
        self.top = -1

    def is_empty(self):
        return self.top == -1

    def is_full(self):
        return self.top == self.capacity - 1

    def push(self, value):
        if self.is_full():
            print("Stack Overflow")
            return
        self.top += 1  # move top up to next free slot
        self.array[self.top] = value  # place value at top

    def pop(self):
        if self.is_empty():
            print("Stack Underflow")
            return None
        value = self.array[self.top]  # get top value
        self.array[self.top] = None  # clear top slot
        self.top -= 1  # move top down
        return value

    def __str__(self):
        if self.is_empty():
            return "Stack is empty"
        return "Top -> [" + ", ".join(str(self.array[i]) for i in range(self.top + 1)) + "] null"

# Driver code
stack = Stack()
stack.push(10)
stack.push(20)
print(stack)
popped = stack.pop()
print(f"Popped: {popped}")
stack.push(30)
print(stack)

self.top += 1 # move top up to next free slot

advance top pointer to next position for new item

self.array[self.top] = value # place value at top

store new value at the top position

value = self.array[self.top] # get top value

retrieve value from current top before removal

self.array[self.top] = None # clear top slot

clear the slot to avoid stale data

self.top -= 1 # move top down

move top pointer down after removal

Output

Top -> [10, 20] null

Popped: 20

Top -> [10, 30] null

Complexity Analysis

Time: O(1) for push and pop because we add or remove only at the top without traversing

Space: O(n) where n is capacity because we allocate fixed array space upfront

vs Alternative: Compared to linked list stack, array stack uses fixed space but faster access; linked list uses dynamic space but more memory per element

Edge Cases

Push when stack is full

Prints 'Stack Overflow' and does not add new item

DSA Python

if self.is_full():

Pop when stack is empty

Prints 'Stack Underflow' and returns None

DSA Python

if self.is_empty():

Pop until empty then push again

Stack correctly empties and accepts new pushes

DSA Python

self.top -= 1  # move top down

When to Use This Pattern

When you need last-in-first-out order with fast access, use stack with array for simple fixed-size storage.

Common Mistakes

Mistake: Incrementing top pointer after placing value instead of before
Fix: Increment top before placing value to avoid overwriting

Mistake: Not checking for stack overflow before push
Fix: Always check is_full() before pushing new item

Mistake: Not checking for stack underflow before pop
Fix: Always check is_empty() before popping

Summary

Implements a stack using a fixed-size array with push and pop at the top.

Use when you want simple, fast last-in-first-out storage with known maximum size.

The top pointer moves up on push and down on pop to track the current stack top.

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