Stacks

Core idea

A stack follows LIFO — Last In, First Out.

       ┌───────┐
       │   30  │ ← top / first out
       ├───────┤
       │   20  │
       ├───────┤
       │   10  │
       └───────┘

Operations

• Push — add to the top
• Pop — remove and return the top
• Peek/Top — inspect the top without removing
• Is Empty — check whether the stack is empty

Example:

stack = []

stack.append(10)
stack.append(20)
stack.append(30)

stack.pop()   # 30
stack[-1]     # 20

Array-based implementation

Python’s list is a dynamic array, so use its end as the stack top.

stack.append(x)  # push
stack.pop()      # pop
stack[-1]        # peek

Do not use:

stack.insert(0, x)
stack.pop(0)

because removing from index 0 requires shifting elements → O(n).

Complexity

Operation	Complexity
Push / append()	O(1) amortized
Pop / pop()	O(1)
Peek / stack[-1]	O(1)
Is empty	O(1)
Search	O(n)

Push has:

Normal push → O(1)
Resize push → O(n) worst case
Amortized   → O(1)

Amortized O(1) does not mean every push is O(1).

Underflow and overflow

Underflow: attempting to pop from an empty stack.

Overflow: attempting to push beyond available capacity; mainly relevant to fixed-size stacks or call stacks.

Common applications

Function call stack

Function calls follow LIFO:

main()
  ↓
foo()
  ↓
bar()

bar() finishes first.

Bracket matching

Stacks are useful for nested brackets:

({[]})

Push opening brackets; when a closing bracket appears, check the most recent opening bracket.

Undo/redo

The most recent action is undone first.

Reversing data

stack = []

for x in ["A", "B", "C", "D"]:
    stack.append(x)

while stack:
    print(stack.pop())

Output:

D
C
B
A

Stack vs Queue

Stack → LIFO
Queue → FIFO

Mental model:

Stack → pile of plates
Queue → line of people

Interview pattern

When you see:

most recent
last
undo
nested
matching brackets
reverse
backtracking

consider whether a stack is appropriate.

Simple implementation

class Stack:
    def __init__(self):
        self.stack = []

    def push(self, value):
        self.stack.append(value)

    def pop(self):
        if not self.stack:
            return None
        return self.stack.pop()

    def peek(self):
        if not self.stack:
            return None
        return self.stack[-1]

    def is_empty(self):
        return len(self.stack) == 0

Interview answers

What is a stack?

A data structure that follows LIFO: the last element inserted is the first element removed.

Why is pop O(1)?

When the top is maintained at the end of an array, removing the last element does not require shifting the remaining elements.

Why is push amortized O(1)?

A dynamic array occasionally resizes in O(n), but resizing is infrequent, so the total cost across many pushes gives O(1) amortized cost.

Why not pop(0)?

Removing the first array element requires shifting the remaining elements, making it O(n).

Quick revision

STACK

LIFO = Last In, First Out

push  → O(1) amortized
pop   → O(1)
peek  → O(1)
empty → O(1)
search → O(n)

Python:
append() → push
pop()    → pop
[-1]     → peek

Avoid pop(0) for stacks → O(n)

Common uses:
- Call stack
- Bracket matching
- Undo/redo
- Reversal
- Backtracking