Stacks, queues and deques: interview prep with practice questions

Stacks: last in, first out

A stack allows two main operations: push puts an item on top, pop takes the top item off. The last item in is the first out (LIFO). You can also peek at the top without removing it. All three are O(1).

A stack is the natural structure for anything that has to be undone or unwound in reverse order. Your program's call stack is one: each function call pushes a frame, each return pops it. That's also why infinite recursion ends in a 'stack overflow': the stack ran out of room.

A stack of three calls on the left, a queue of four jobs on the right

In real life

Undo in an editor (each action pushed, undo pops the last one), the browser's back button, matching brackets in code: every '(' is pushed, every ')' pops and must match.

In code: Python · Rust

undo = []
undo.append("typed 'a'")   # push
undo.append("bold")
undo.pop()                   # 'bold': last in, first out
undo[-1] if undo else None   # peek

let mut undo: Vec<&str> = Vec::new();
undo.push("typed 'a'");
undo.push("bold");
let last = undo.pop();       // Some("bold")
let top = undo.last();       // peek: Some("typed 'a'")

In both languages a plain dynamic array (list, Vec) is the idiomatic stack: push and pop at the end are O(1).
Python's default recursion limit (about 1000 frames) is a guard against the call stack overflowing.

Check yourself

An editor must undo actions in reverse order of how they were done. Which structure fits?

Queues: first in, first out

A queue adds at the back (enqueue) and removes from the front (dequeue): first in, first out (FIFO). It's the fair structure: things are handled in the order they arrived.

The trap is building a queue on a plain dynamic array: removing from the front shifts everything, O(n). Use a structure that's O(1) at both ends: a deque (double-ended queue), usually implemented as a ring buffer or a chain of blocks. A deque also works as a stack, and lets you add or remove at either end.

In real life

A print queue, requests waiting for a free worker, messages between services (the same idea at system scale: a message queue), breadth-first search through a graph.

In code: Python · Rust

from collections import deque
jobs = deque()
jobs.append("job 1")      # enqueue at the back
jobs.append("job 2")
jobs.popleft()             # 'job 1', O(1)
jobs.appendleft("urgent")  # a deque works at both ends

# Between threads: queue.Queue (thread-safe, can block)

use std::collections::VecDeque;
let mut jobs: VecDeque<&str> = VecDeque::new();
jobs.push_back("job 1");
jobs.push_back("job 2");
let first = jobs.pop_front();   // Some("job 1"), O(1)
jobs.push_front("urgent");

// Between threads: std::sync::mpsc channels

Python: list.pop(0) is O(n); deque.popleft() is O(1).
Rust's VecDeque is a growable ring buffer.

Check yourself

A service handles requests in arrival order and keeps them in a Python list, taking the next one with pop(0). Throughput drops as the backlog grows. What fixes it?

Ring buffers: a queue in fixed memory

A ring buffer (circular buffer) is a fixed-size array used as a queue. Two indexes, head and tail, chase each other around it: writing advances the tail, reading advances the head, and both wrap back to index 0 at the end. Nothing ever shifts, and memory is allocated once.

When the buffer is full you have to choose a policy: overwrite the oldest item (fine for 'last N log lines' or sensor readings) or refuse new items until there's room (necessary when data must not be lost, such as audio playback or a write log).

Eight slots in a circle; four hold e1 to e4 between head and tail

In real life

Keeping the last 1,000 log lines in memory for a crash report; audio buffers between a microphone and an encoder; network cards receiving packets.

In code: Python · Rust

from collections import deque
last_lines = deque(maxlen=1000)   # a bounded deque behaves like a ring buffer
for line in ["a", "b"]:
    last_lines.append(line)       # beyond 1000, the oldest line drops off

use std::collections::VecDeque;
let cap = 1000;
let mut last_lines: VecDeque<String> = VecDeque::with_capacity(cap);
fn push(buf: &mut VecDeque<String>, cap: usize, line: String) {
    if buf.len() == cap { buf.pop_front(); }   // overwrite the oldest
    buf.push_back(line);
}

deque(maxlen=N) silently discards from the opposite end when full: an overwrite-oldest ring buffer in one line.
In systems code, ring buffers are often lock-free for one producer and one consumer.

Check yourself

Stacks, queues and deques

Stacks: last in, first out

An editor must undo actions in reverse order of how they were done. Which structure fits?

Queues: first in, first out

A service handles requests in arrival order and keeps them in a Python list, taking the next one with pop(0). Throughput drops as the backlog grows. What fixes it?

Ring buffers: a queue in fixed memory

A ring buffer is full. For which data is 'overwrite the oldest' the right policy?

Section complete