Stacks and queues are the two simplest ways to hold a line of items — and they differ in one rule: which item comes out first. A stack hands back the item you added last. A queue hands back the item you added first. That single choice shows up everywhere: undo buttons, browser back, task schedulers, and breadth-first search.
Step through the animation on the right. Phase 1 builds a stack (push, push, push, pop) and watches the LAST value leave. Phase 2 builds a queue (enqueue ×3, dequeue) and watches the FIRST value leave. The highlighted code line shows the exact operation each step.
The idea
Both are just a list of items with restricted access — you only touch one or both ends.
- Stack — LIFO (Last In, First Out). You push onto the top and pop from the top. Same end for both. Think of a stack of plates: the last plate you put down is the first one you pick up.
- Queue — FIFO (First In, First Out). You enqueue at the rear and dequeue from the front. Opposite ends. Think of a line at a coffee shop: first to arrive is first to be served.
The magic is that every operation touches only the end(s) — never the middle — so each push, pop, enqueue, and dequeue is O(1), constant time.
Walk through it
Press Play on the right, or step with Next / Back.
Phase 1 — Stack. We push 10, then 20, then 30. The top pointer climbs right with each push. Then pop() removes whatever top points at — that is 30, the last value pushed. After it leaves, top steps back to 20.
Phase 2 — Queue. We enqueue 10, 20, 30. New items join at the rear; the front stays pinned to 10. Then dequeue() removes the front — that is 10, the first value added. front then advances to 20.
Notice the contrast: from the same sequence [10, 20, 30], the stack gives back 30 first and the queue gives back 10 first.
The code, line by line
from collections import deque
stack = []
stack.append(x) # push onto the top
stack.pop() # pop the top (LIFO)
queue = deque()
queue.append(x) # enqueue at the rear
queue.popleft() # dequeue the front (FIFO)- A plain Python list is a ready-made stack:
appendpushes onto the end,popremoves the end. Both are O(1). - For a queue, use
collections.deque, a double-ended queue.appendadds at the rear andpopleftremoves from the front — both O(1). - Do not use a list as a queue with
list.pop(0). Removing the front of a list shifts every other element left, which is O(n).dequeavoids that.
Complexity
| Case | Time | Notes |
|---|---|---|
| Push / Enqueue | O(1) (fast) | add at one end |
| Pop / Dequeue | O(1) (fast) | remove from one end |
| Peek (top / front) | O(1) (fast) | look without removing |
| Search | O(n) (moderate) | no random access; scan all items |
O(n) (moderate)Every end operation is constant time. Searching is O(n) because a stack or queue gives you no random access — to find a value in the middle you would have to empty it out. Space is O(n) for the n items you store.
When to use / pitfalls
Match the structure to the order you need. Reach for a stack when the most recent thing matters first — undo/redo, matching brackets, depth-first search, the call stack itself. Reach for a queue when fairness or arrival order matters — task scheduling, printer jobs, and breadth-first search. Saying "I need LIFO here, so a stack" out loud is a strong signal in an interview.
The classic bug: using a Python list as a queue and calling list.pop(0). It looks right but is
O(n) per call because every remaining element shifts down one slot — turning an O(n) loop into
O(n²). Use collections.deque and popleft() instead. Also remember to check for empty before you
pop: popping an empty stack or queue raises an error.
Practice
You add 10, 20, 30 in that order. From a STACK you pop once; from a QUEUE you dequeue once. Which value comes out of each?
1. A stack is which ordering?
2. You enqueue 1, 2, 3 into a queue, then dequeue once. What comes out?
3. Why use collections.deque instead of a list for a queue?
4. Which problem is the most natural fit for a stack?