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.
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.
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
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.
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
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).
Visual: Queue enqueue & dequeue
Items enter from the back and leave from the front. The opposite of a stack.
Queue Operations — Step by Step
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.
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.
<= and not <?<= 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.
_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.
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
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?
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
collections.deque instead of a list for a queue in Python?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 →