Two of the simplest containers, with superpowers. A stack pushes and pops at one end — last in, first out, like a stack of plates. A queue adds at the back and removes at the front — first in, first out, like a line. Watch both fill and drain side by side and the difference is unmistakable.
stack · queue · push · pop · enqueue · dequeue
STACK · LIFO
Push and pop at the top. The last item in is the first out.
QUEUE · FIFO
Enqueue at the back, dequeue at the front. Arrival order preserved.
O(1)
Both add and remove at fixed ends — no scanning, no shifting.
On the left, a stack; on the right, a queue. Press Step to push three items and pop one from the stack, then enqueue three and dequeue one from the queue — and watch which item comes out.
—
Removed
—
Operation
Same speed, opposite order
Both a stack and a queue do their work in O(1) — they only touch fixed ends, so nothing shifts. What separates them is which end. A stack adds and removes at the same end, so the newest item is on top and comes back first. A queue adds at one end and removes at the other, so items leave in the order they arrived. That one difference decides everything they're used for.
01
Push / Pop (stack)
push puts an item on top; pop takes the top item off. Last in, first out.
02
Enqueue / Dequeue (queue)
enqueue adds at the back; dequeue removes from the front. First in, first out.
03
Stacks unwind
The call stack, undo, bracket matching, DFS and backtracking all need the most recent thing back first — that's a stack.
04
Queues stay fair
BFS, job scheduling, printer and request queues, and producer-consumer buffers process items in arrival order — that's a queue.
Push / Pop / Peek
O(1)
Enqueue / Dequeue
O(1)
Search
O(n)
Space
O(n)
Both are usually built on a dynamic array or a linked list. A deque (double-ended queue) generalizes them — add and remove at either end — and a priority queue (a heap) swaps arrival order for a “smallest-first” order when priority matters more than fairness.
The picture: same input, opposite order out
Both containers receive 1, 2, 3. A stack hands back the newest item first; a queue hands back the oldest. Only the end you take from differs, and that one choice decides whether the structure fits undo and recursion (stack) or fairness and scheduling (queue).
Worked example, step by step
Feed the same eight operations to a stack and a queue: add 1, add 2, add 3, remove, remove, add 4, remove, remove. The stack is shown with its top on the right and the queue with its front on the left.
Step
Operation
Stack after
Stack removed
Queue after
Queue removed
1
add 1
[1]
—
[1]
—
2
add 2
[1, 2]
—
[1, 2]
—
3
add 3
[1, 2, 3]
—
[1, 2, 3]
—
4
remove
[1, 2]
3
[2, 3]
1
5
remove
[1]
2
[3]
2
6
add 4
[1, 4]
—
[3, 4]
—
7
remove
[1]
4
[4]
3
8
remove
[]
1
[]
4
The stack returned 3, 2, 4, 1 and the queue 1, 2, 3, 4. The queue gives back exactly the order of arrival. The stack reverses runs: after 3 and 2 came off, the late arrival 4 jumped ahead of 1, which had been waiting since step 1 and only left last. That jump is the point: a stack serves the most recent unfinished thing, which is what a function call, an undo or a nested bracket needs; a queue never lets a newer item overtake an older one.
A queue built from two stacks. The same eight operations can run on two stacks, in and out. Add pushes onto in. Remove pops from out, and only when out is empty does it pour all of in across, which reverses it. At step 4, in holds [1, 2, 3]; pouring leaves 1 on top of out, and 1 comes off. Steps 5 to 7 need no pour, while 4 waits on in. Step 8 finds out empty and pours the single 4. The output is 1, 2, 3, 4, the queue column above. Each element crosses once, so the whole run costs 16 stack operations, at most 4 per element. One remove can be slow (step 4 moved three items), but the average stays O(1). That amortised argument is the classic interview answer.
Complexity and trade-offs
Case
Time
Space
Why
Stack on a dynamic array
push, pop, peek O(1) amortised
O(n)
An occasional resize copies the array, but averaged over many pushes it is constant.
Stack on a linked list
push, pop O(1) worst case
O(n)
No resizing pauses, at the price of a node allocation and a pointer per item.
Queue on an array, remove from index 0
dequeue O(n)
O(n)
Every removal shifts the rest left. Draining 1,000 items this way moves 499,500 elements.
Queue on a circular buffer or deque
enqueue, dequeue O(1)
O(n)
Head and tail indices wrap around a fixed array, or use a linked block deque such as Python’s collections.deque.
Queue from two stacks
O(1) amortised, O(n) worst single dequeue
O(n)
Each item moves between stacks at most once; 1,000 enqueues then 1,000 dequeues cost 1,000 moves.
Priority queue (heap)
O(log n) per operation
O(n)
Not FIFO: always yields the smallest or largest item, for scheduling by priority instead of arrival.
Searching a plain stack or queue is O(n), since neither is built for lookup; if you need to find items, use a hash set alongside. The practical rule is to pick the container whose removal rule matches the work (newest first, oldest first, best first) and then pick an implementation that makes both ends O(1).
Common mistakes
Swapping the operands in reverse Polish notation
The first value popped is the right operand. For ["3", "4", "-"] the correct result is -1; evaluating b − a instead of a − b returns 1. It is invisible for + and *, so tests that use only those pass.
Wrong division rounding
RPN division usually truncates toward zero. For ["-7", "2", "/"] that is -3, while Python's // floors to -4. Use int(a / b) in Python or Math.trunc in JavaScript.
Using a stack where BFS needs a queue
On the graph 0→{1,2}, 1→3, 2→3, a queue visits 0, 1, 2, 3 (level by level), but swapping in a stack visits 0, 2, 3, 1. The code still runs and still finds a path; it just no longer finds the shortest one.
Dequeuing with list.pop(0)
It works and it is quadratic: 1,000 removals shift 499,500 elements. Use collections.deque (popleft), or an index/circular buffer.
Confusing full with empty in a circular buffer
If head == tail means empty, a buffer of capacity 4 that has taken 4 items also has head == tail after wrapping (both 0) and looks empty. Keep a size counter, or leave one slot unused.
Where this shows up
The call stack and recursion
Every function call pushes a frame and every return pops one. CPython caps recursion at 1,000 frames by default, which is a stack with a limit.
Undo, redo and browser history
An editor pushes each action onto an undo stack; undo pops it onto a redo stack. A browser’s Back button walks a history stack the same way.
Parsing and expression evaluation
Bracket matching, the shunting-yard algorithm that converts infix to postfix, and evaluating the postfix form (the page’s exercise) all keep a stack of pending operators or operands.
Scheduling and buffering
Operating-system round-robin schedulers keep a ready queue of runnable processes, and a producer-consumer pipeline puts a bounded queue between stages so the fast side waits when the buffer is full. In Java, the documentation recommends ArrayDeque over the legacy Stack class for stack use.
SOLVE IT YOURSELF
Solve it: evaluate RPN
This one is yours to write — in Python or TypeScript, running for real in your browser. Edit the stub below, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are below and Reveal solution is one click away.
YOUR TASK
Implement eval_rpn(tokens): evaluate an expression in Reverse Polish Notation using a stack. Tokens are numbers and the operators + − * /. Push numbers; on an operator, pop the top two, apply it, push the result. Division truncates toward zero. Return the final value.
HINTS — 4 IDEAS
A stack is exactly right: numbers wait on it until an operator needs them.
See a number? push it. See an operator? pop b (top) then a — order matters for − and /.
Compute a op b, push the result back, and carry on.
For division, truncate toward zero (so −7 / 2 = −3): use int(a / b) in Python, Math.trunc(a / b) in TS. The last value on the stack is the answer.
CPython · WebAssembly✓ Solved
1
1
▶ Watch it explained
Stack and Queue: Evaluate RPN, Time and Space Complexity, From First Principles
Check yourself
1 · You push A, then B, then C onto a stack and pop once. What comes out?
A stack is last-in-first-out: the most recently pushed item, C, is on top and pops first.
2 · You enqueue A, then B, then C into a queue and dequeue once. What comes out?
A queue is first-in-first-out: items leave in arrival order, so A — enqueued first — dequeues first.
3 · Which traversal uses a queue?
BFS explores level by level in arrival order — a queue. DFS and backtracking use a stack (or recursion, which is the call stack).
Questions
How is a stack actually implemented?
Usually on a dynamic array (push/pop at the end) or a singly linked list (push/pop at the head). Both give O(1) operations; the array version is more cache-friendly, the linked-list version never needs a resize.
What's the connection between a stack and recursion?
Every function call is pushed onto the program's call stack with its local state, and popped when it returns. Deep recursion can overflow that stack — which is why some recursive algorithms are rewritten with an explicit stack.
What is a priority queue?
A queue where each item has a priority and the highest-priority item comes out first, regardless of arrival order. It's implemented with a heap and powers Dijkstra's algorithm, A*, and scheduling — see the Heap Sort lesson for the underlying structure.
Same O(1), opposite order.
Stack for the most recent, queue for the fairest. Two tiny containers behind undo, recursion, BFS and scheduling.