Stacks & queues basics
In one line
A stack gives back the most recently added item first (last in, first out) and a queue gives back the oldest first (first in, first out); both do their core operations in O(1).
What it is
A stack is a collection where you only touch the top: push adds an item on top, pop removes the top item, and peek reads it without removing it. The last item in is the first item out (LIFO).
A queue is a collection with two ends: enqueue adds at the back and dequeue removes from the front, so the first item in is the first item out (FIFO). In Python, a list works as a stack (append and pop at the end), and collections.deque works as a queue (append and popleft). Using list.pop(0) as a queue is a common trap: it shifts every element and costs O(n).
Why interviewers ask
Stacks and queues are the foundation for many interview patterns: brackets, expression parsing, monotonic stacks, depth-first search (stack) and breadth-first search (queue). Interviewers check that you know which one a problem needs, that you use the right Python structure for O(1) operations, and that you can explain why recursion is really a stack.
How it works
- 1Stack push: put the item on top. Pop: take the top item. Peek: look at the top. Each is O(1). Always check that the stack is not empty before pop or peek.
- 2Queue enqueue: add at the back. Dequeue: remove from the front. With a deque or a linked list both are O(1); with a plain array you would need a circular buffer to avoid shifting.
- 3When to use a stack: the most recent unfinished thing must be handled first, such as the innermost bracket, the latest directory, the last action to undo, or the next node in depth-first search.
- 4When to use a queue: things must be handled in arrival order, such as tasks, requests, or nodes level by level in breadth-first search.
- 5Recursion uses the call stack: each call pushes a frame with its local variables, and returning pops it. Any recursive algorithm can be rewritten with an explicit stack, which avoids recursion depth limits (Python's default limit is about 1,000 frames).
Worked example · Simplify the Unix path '/a/./b/../../c/'
- Split on '/': ['', 'a', '.', 'b', '..', '..', 'c', '']. Empty parts come from repeated or trailing slashes and are skipped.
- 'a': push. Stack ['a']. '.': means 'this directory', skip. Stack ['a'].
- 'b': push. Stack ['a', 'b']. '..': go up, pop 'b'. Stack ['a'].
- '..': pop 'a'. Stack []. 'c': push. Stack ['c'].
- Join: '/' + 'c' = '/c'. A '..' on an empty stack (at the root) is simply ignored.
Picture it
A stack is a pile of plates: you add and take plates from the top only. A queue is the line at a coffee shop: the person who arrived first is served first, and newcomers join at the back.
Reference code
from collections import deque
stack = [] # Python list as a stack
stack.append(3) # push, O(1)
stack.append(7)
top = stack[-1] # peek -> 7
stack.pop() # pop -> 7, O(1)
queue = deque() # deque as a queue
queue.append("a") # enqueue at the back, O(1)
queue.append("b")
queue.popleft() # dequeue from the front -> "a", O(1)
def simplify_path(path):
"""'/a/./b/../../c/' -> '/c'"""
stack = []
for part in path.split("/"):
if part == "..":
if stack:
stack.pop() # go up one directory
elif part and part != ".":
stack.append(part) # a real directory name
return "/" + "/".join(stack)
A list's append and pop at the end are O(1) amortised, so it is a good stack. deque gives O(1) at both ends, so it is the right queue. simplify_path is O(n) time and space in the length of the path.
Key patterns
Undo the latest thing
When: Backspace processing, undo, '..' in paths
How: Push normal items; on a 'remove' token, pop the top if the stack is not empty.
Explicit DFS
When: Deep trees or graphs where recursion might exceed the depth limit
How: Push the start node; loop: pop, process, push its unvisited neighbours.
BFS with a queue
When: Shortest path in an unweighted graph, level-order tree traversal
How: Enqueue the start; loop: dequeue, process, enqueue unvisited neighbours. Use collections.deque.
Reverse order
When: Reversing a string, list or the order of processing
How: Push everything, then pop everything: items come out in reverse.
Real-world use
Function calls in every program
The CPU and language runtimes keep a call stack of frames. When a function returns, its frame is popped. A runaway recursion fills it and causes a stack overflow (in Python, a RecursionError).
Browser back button
Browsers keep visited pages as a history stack: Back pops to the previous page, and visiting a new page clears the forward history, just like a stack-based undo.
Task and message queues
Celery workers, AWS SQS and RabbitMQ deliver work roughly in arrival order, so background jobs like sending emails are processed fairly and none are starved.
Printer spoolers and OS schedulers
Print jobs wait in a FIFO queue, and operating systems keep ready queues of processes waiting for the CPU (round-robin scheduling cycles through one).
In a project
You are building a file-browser feature for a cloud storage web app: users click into folders, use 'Up' and 'Back', and you also need to resolve paths typed by users such as '../shared/./reports'.
- Represent the current location as a stack of folder names; opening a folder pushes, 'Up' pops (never below the root).
- Resolve typed paths by splitting on '/', skipping empty parts and '.', popping on '..', and pushing names.
- Keep a separate back stack of previous locations so Back pops the last location you came from.
- Process thumbnail generation for uploaded files with a FIFO job queue so the earliest uploads are shown first.
Impact: Navigation and path resolution are O(1) per step and correct for edge cases like '../..' at the root, which closes a class of path-handling bugs (and path traversal mistakes) while keeping the UI responsive.
Trade-offs
Use it when
- Stack: the most recent item must be handled first (nesting, undo, DFS, backtracking)
- Queue: items must be handled in arrival order (BFS, job processing, buffering)
- You only need access to the ends, not to arbitrary positions
Avoid it when
- You need to search or remove items in the middle: use a hash map, set or linked structure
- You need the smallest or highest priority item, not the newest or oldest: use a heap
- Using list.pop(0) or list.insert(0, x) for a queue: both are O(n); use deque
Cost: Push, pop, peek, enqueue and dequeue are all O(1) (list append is O(1) amortised). Space O(n) for n items.
Common mistakes
- Popping or peeking an empty stack and crashing with an IndexError.
- Using a Python list as a queue with pop(0), which is O(n) per operation.
- Mixing up which structure DFS and BFS use: DFS uses a stack, BFS uses a queue.
- Forgetting that deep recursion uses the call stack and can overflow; an explicit stack avoids that.
- Not handling '..' at the root or empty segments from double slashes in path problems.
Interview questions
Quick revision
- Stack = LIFO: push, pop, peek, all O(1).
- Queue = FIFO: enqueue at back, dequeue at front, O(1) with deque.
- Python stack: list.append / list.pop(); queue: deque.append / deque.popleft().
- list.pop(0) is O(n): never use it as a queue.
- DFS = stack (or recursion); BFS = queue.
- Recursion = the call stack; deep recursion can overflow.
- Check for empty before pop or peek.
Check yourself
1. You push 1, 2, 3 onto a stack, pop once, then push 4. What does the next pop return?
2. Which Python operation is O(n) and should not be used for a queue?
3. Which traversal naturally uses a queue?
4. What does simplify_path return for '/../x/./y/..'?
Related
Saved on this device. Create a free account to keep it on every device.
Practise this with Sam
A real mock interview, out loud, with an honest scorecard. Free to start.