Stack — Last In, First Out

A stack is like a stack of plates. You add plates on top and remove from the top. The last plate you put down is the first one you pick up. That's LIFO — Last In, First Out.

📚
Real-world analogy
Browser back button, Ctrl+Z undo, call stack

Every time you visit a page, the browser pushes it onto a stack. Hit "Back" and it pops the most recent page. Undo in any editor? Stack. Function calls in Python? Also a stack — that's why it's called a "call stack" and why you get a "stack overflow" error on infinite recursion.

Three operations — all O(1)

  • push(item) — add to the top
  • pop() — remove and return the top item
  • peek() / top() — look at the top item without removing it

In Python, a plain list works perfectly as a stack. append() pushes, pop() pops from the end. Both are O(1) amortized.

stack_basics.py Stack operations with Python list
Output
Stack: ['A', 'B', 'C'] Top: C Pop: C Pop: B Stack: ['A'] Empty? False

Visual: Stack push & pop

Watch how items enter and leave a stack. The top of the stack is always where the action happens.

Stack Operations — Step by Step

1. push("A")
A
top
2. push("B")
A
B
top
3. push("C")
A
B
C
top
4. pop() → C
A
B
top
5. pop() → B
A
top

Queue — First In, First Out

A queue is like a line at a store. The first person in line is the first person served. That's FIFO — First In, First Out.

🚶
Real-world analogy
Print queue, BFS traversal, task scheduling

Print jobs, message queues in backend systems, BFS in graphs — they all use queues. When your Uber request joins a queue of riders, the earliest request gets matched first. FIFO everywhere.

Two operations

  • enqueue(item) — add to the back
  • dequeue() — remove from the front
Do NOT use list for queues.
list.pop(0) is O(n) because Python shifts every element left. Use collections.deque instead — append() adds to the right, popleft() removes from the left. Both O(1).
queue_basics.py Queue operations with collections.deque
Output
Queue: ['A', 'B', 'C'] Dequeue: A Dequeue: B Queue: ['C'] Front: C

Visual: Queue enqueue & dequeue

Items enter from the back and leave from the front. The opposite of a stack.

Queue Operations — Step by Step

1. enqueue("A")
A
frontback
2. enqueue("B")
A
B
frontback
3. enqueue("C")
A
B
C
frontback
4. dequeue() → A
B
C
frontback
5. dequeue() → B
C
frontback

Problem: Valid Parentheses

This is the most classic stack problem in interviews. Given a string of brackets ()[]{}, determine if every opening bracket has a matching closing bracket in the correct order.

Why a stack? When you see an opening bracket, push it. When you see a closing bracket, pop and check if it matches. If the stack is empty at the end, the string is valid.

valid_parentheses.py O(n) time, O(n) space
Output
True False False True
Interview tip:
Always handle edge cases — empty string (valid), single bracket (invalid), and nested brackets. The not stack check prevents popping from an empty stack when you get a closing bracket with no matching opener.

Problem: Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element — all in O(1) time. This is LeetCode 155 and a common interview question.

The trick: maintain a second stack that tracks the current minimum. When you push a value, also push it onto the min stack if it's less than or equal to the current minimum. When you pop, pop from the min stack if the value matches.

min_stack.py All operations O(1)
Output
Min: 2 Min after pop: 3
Why <= and not <?
If you push the same minimum twice (e.g., push 3 then push 3), you need both copies on the min stack. Using <= ensures that when you pop one 3, the other 3 is still tracked as the minimum.

Problem: Implement Queue using Stacks

Implement a FIFO queue using only two stacks. This is LeetCode 232. The key insight: reversing a stack gives you the opposite order — which is exactly what a queue needs.

Strategy: Use an "in" stack for pushes and an "out" stack for pops. When you need to pop/peek, if the out stack is empty, pour everything from the in stack into it. This reverses the order, giving you FIFO access.

queue_from_stacks.py Amortized O(1) per operation
Output
1 2
Amortized O(1):
Each element gets moved from in_stack to out_stack exactly once. So even though a single _move() call might transfer n elements, over n operations, the total work is O(n) — meaning O(1) per operation on average.

Monotonic Stack — Interview Pattern

A monotonic stack keeps its elements in sorted order (either increasing or decreasing). You maintain this by popping elements that violate the ordering before pushing a new one.

When to use it: "Next greater element," "next smaller element," "largest rectangle in histogram," stock span problems. If the problem asks about the next/previous larger or smaller value, think monotonic stack.

next_greater.py Next Greater Element — O(n)
Output
[8, 8, -1, 5, -1] [4, 2, 4, -1]

The stack holds indices of elements that haven't found their "next greater" yet. When a new element is larger, we pop and record the answer. Each element is pushed and popped at most once, so the total time is O(n).

Try It Yourself

Valid Parentheses — Write Your Solution

Implement is_valid(s) using a stack. The function should return True if every opening bracket has a matching closing bracket in the correct order.

Challenge

Reverse a string using a stack
Your task:

Write a function reverse_string(s) that reverses a string using only a stack (Python list). Do not use slicing (s[::-1]) or reversed(). Push every character onto the stack, then pop them all off into a new string.

Example: reverse_string("hello") should return "olleh".

Bonus: What's the time and space complexity?

Push each character with a for loop: for char in s: stack.append(char). Then pop them into a result string: while stack: result += stack.pop(). Both loops run n times, so it's O(n) time and O(n) space for the stack.

Quiz

Question 1 of 5
What does LIFO stand for, and which data structure follows it?
Question 2 of 5
Why should you use collections.deque instead of a list for a queue in Python?
Question 3 of 5
In the Valid Parentheses problem, what should you do when you encounter a closing bracket?
Question 4 of 5
How does MinStack achieve O(1) getMin()?
Question 5 of 5
In the "Queue using Two Stacks" problem, when do you transfer elements from the in_stack to the out_stack?
0
/5
Great work! You understand stacks and queues.
Africa & India's Best AI Academy
🤖 AI-first 🎓 Placement Assistance

You've mastered stacks and queues.
Now ace the full interview.

Join the Best AI Programs — three 5-month courses, fully online, with placement assistance. Week 1 is free.

Explore our AI-era courses →