Stacks, queues & linked lists

Dynamic sets and the operations that name a structure

A *dynamic set* is any collection that grows and shrinks over time and supports some mix of operations: queries that read the set (SEARCH, MINIMUM, MAXIMUM, SUCCESSOR, PREDECESSOR) and modifiers that change it (INSERT, DELETE). Almost every data structure in this course is a dynamic set that implements *some subset* of these operations efficiently. The whole art of Part III of CLRS is choosing the structure whose fast operations match the operations your algorithm actually performs.

This lesson covers the three simplest dynamic sets — stacks, queues, and linked lists — because the graph algorithms in Modules 6–7 are built directly on top of them: depth-first search runs on a stack, breadth-first search runs on a queue.

Stacks: last-in, first-out

A stack removes the *most recently inserted* element — last-in, first-out (LIFO), like a stack of plates. It supports three $O(1)$ operations: PUSH(S, x) adds $x$ on top, POP(S) removes and returns the top, and STACK-EMPTY(S) tests whether the stack is empty. An array implementation tracks a single index S.top: the stack holds S[1..S.top], it is empty when S.top = 0, and POP just *decrements* S.top — no element is ever erased, the slot is simply reused by the next PUSH.

Queues: first-in, first-out

A queue removes the element that has waited *longest* — first-in, first-out (FIFO), like a line of customers. ENQUEUE(Q, x) adds at the tail; DEQUEUE(Q) removes from the head. The clever implementation is a circular array Q[1..n] with two indices, Q.head and Q.tail, that wrap around modulo $n$. Wrapping is what makes both operations $O(1)$: without it, dequeuing from the front would force shifting every remaining element ($\Theta(n)$). A subtlety: a length-$n$ array holds at most $n-1$ queued elements, because storing $n$ would make head = tail, which is indistinguishable from *empty* — so implementations track a count or leave one slot open.

Linked lists: O(1) splice, no random access

A doubly linked list chains node objects, each with key, next, and prev. Given a *pointer* to a node, LIST-INSERT and LIST-DELETE are $O(1)$ — splicing changes only a constant number of pointers. But there is no random access: LIST-SEARCH is $\Theta(n)$ because you must walk the chain. A sentinel L.nil — one dummy node standing in for every NIL, turning the list circular — erases the boundary special cases (DELETE becomes two unconditional pointer writes) and roughly halves search comparisons, at the cost of $O(1)$ extra space.

The recurring trade-off

Arrays give $O(1)$ random access (address arithmetic a + b(i-1)) but $\Theta(n)$ insert/delete in the middle (shifting). Linked lists invert it: $O(1)$ pointer-mediated insert/delete, but $\Theta(k)$ to reach the $k$-th element. There is no universally best choice — you pick by the operation mix, and that justification is a recurring exam answer.

Worked example — DFS uses a stack, BFS uses a queue

Watch how the policy decides traversal order. Push 10, 20, 30 onto a stack, then pop twice: LIFO returns 30, 20 (newest first — this is exactly why an explicit stack turns recursive DFS into a loop). Enqueue the same 10, 20, 30, then dequeue twice: FIFO returns 10, 20 (oldest first — exactly the level-by-level order BFS needs). Same three values, opposite removal order, and the difference is the *only* thing that distinguishes depth-first from breadth-first search.