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.
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
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.