Vibe Engines
YouTube

Vibe Engines is free, interactive AI engineering & system design — runs in your browser. Pick a learning path

Algorithm · Data Structures

LIFO & FIFO.

Watch the explainer

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.

WHERE

Stack: undo, recursion, DFS. Queue: BFS, scheduling, buffers.

stack-queue.sim — LIFO vs FIFO
Ready

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

stackqueue 11223331 ← top: next out↑ front: next outback: newest add 1, 2, 3 then remove twice: stack gives 3, 2 queue gives 1, 2
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.

StepOperationStack afterStack removedQueue afterQueue removed
1add 1[1]—[1]—
2add 2[1, 2]—[1, 2]—
3add 3[1, 2, 3]—[1, 2, 3]—
4remove[1, 2]3[2, 3]1
5remove[1]2[3]2
6add 4[1, 4]—[3, 4]—
7remove[1]4[4]3
8remove[]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

CaseTimeSpaceWhy
Stack on a dynamic arraypush, pop, peek O(1) amortisedO(n)An occasional resize copies the array, but averaged over many pushes it is constant.
Stack on a linked listpush, pop O(1) worst caseO(n)No resizing pauses, at the price of a node allocation and a pointer per item.
Queue on an array, remove from index 0dequeue 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 dequeenqueue, 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 stacksO(1) amortised, O(n) worst single dequeueO(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 operationO(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
  1. A stack is exactly right: numbers wait on it until an operator needs them.
  2. See a number? push it. See an operator? pop b (top) then a — order matters for − and /.
  3. Compute a op b, push the result back, and carry on.
  4. 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
▶  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.

Finished this one? 0 / 99 Algorithms done
NextThe Instant Lookup: Hash Table Next on the “The four containers” ladder · rung 3 of 4

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

More Algorithms