Algorithms Ch.4: Stacks, Queues, and Heaps in Real Code

0:00 Welcome to Learning Podcasts. Algorithms, chapter four: stacks, queues, and heaps. Three small data structures that quietly run half the code in your editor. Most data structures try to be flexible. Arrays let you index anywhere. Hash tables let you look up by any key. Stacks, queues, and heaps go the other way. Each one drops a freedom on purpose. A stack only lets you touch the top. A queue only lets you push at the back and pull from the front. A heap only lets you see the next-best item. In exchange, every one of those operations is constant time, or close to it.

0:37 So the trick is the restriction. The structure is fast because you cannot poke at the middle. Right. And restricted does not mean small. These three power most of the scheduling, traversal, and ranking in real systems. A stack is a vertical pile. You push values on the top. You pop values off the top. That is the entire interface. The most recent thing in is the first thing out. People call that last-in-first-out, or LIFO. Both push and pop are O of one. Nothing has to slide, nothing has to copy.

1:11 Like a stack of plates. Like a stack of plates. The bottom plate stays put forever, and you only ever touch the one on top. You use stacks every day without naming them. Your function call stack is a stack. Every function call pushes a frame, every return pops one. Your browser's back button is a stack. Every page you visit pushes onto history, every back press pops. Your text editor's undo system is a stack. Every action pushes, every undo pops. All three are the same shape underneath. Same shape.

1:43 Different names. Three patterns worth recognizing. The first is parentheses matching. Walk a string left to right. Push every open paren onto a stack. On every close paren, pop and check it matches. If the stack is empty at the end, the string is balanced. The second is the monotonic stack. It solves the next-greater-element problem in O of n instead of O of n squared. You walk the array once, and you push or pop based on whether the new value is bigger than what is on top. Linear time for a problem that looks like it needs nested loops.

2:14 That is the recognition beat. When you see a problem that asks for the next bigger or next smaller value, the answer is usually a monotonic stack. The third pattern is expression evaluation. The reverse Polish notation a calculator uses, where two plus three is written as two three plus, is a stack walk. You push numbers, and every operator pops the top two values, applies itself, and pushes the result. That is also how compilers internally evaluate constant expressions. A queue is a horizontal line.

2:43 New items go in the back. Old items come out the front. That is first-in-first-out, or FIFO. Like a queue at a coffee shop. Both enqueue and dequeue are O of one when the queue is implemented well. First in, first out. Same idea, opposite end. Right. The stack remembers the most recent thing. The queue remembers the oldest thing still waiting. Queues are also everywhere. Breadth-first search uses a queue to hold the frontier of nodes still to explore. Operating systems use queues to schedule work in arrival order.

3:17 Message brokers like Kafka, SQS, and RabbitMQ are queues at scale, with persistence and delivery guarantees on top. Whenever you have a producer feeding a consumer at a different rate, the queue is the buffer between them. Which is also where backpressure shows up. Right. The queue tells you when the consumer is falling behind. If the queue grows without bound, the consumer cannot keep up and you have to do something: drop messages, scale up consumers, or block the producer. That feedback signal is one of the most important properties of using a queue in production, not just an implementation detail.

3:53 Now the third structure. A priority queue drops the FIFO promise. Each entry has a priority number, and the next item out is always the smallest, or always the largest, depending on which kind you built. Insert and remove-top still need to be fast, even though the queue is reorganizing itself every time. So how do you get fast insert and fast remove-top at the same time? With a heap. A binary heap is a special kind of binary tree, except it lives in a flat array. The root sits at index zero. The two children of the node at index i live at index two i plus one and index two i plus two.

4:30 The invariant is simple. In a min-heap, every parent is smaller than its children. The smallest value in the entire structure is therefore always at the root. Tree shape, array storage. Right. The array-backed shape gets the cache benefits we covered in chapter two, and the index arithmetic is fast enough to disappear. Two operations carry the data structure. Insert: place the new value at the end of the array, then sift it up by swapping with its parent as long as the parent is larger. Extract-min: take the root, move the last value in the array up to the root position, then sift it down by swapping with its smaller child until the invariant holds.

5:09 Both operations touch one path from a leaf to the root, which is at most log n nodes. So both operations are O of log n. O of log n. That is the whole basis for fast priority queues. Now the surprise. If you start with an unordered array of n values and you want to turn it into a heap, the obvious approach is to insert n times. That is n times O of log n, which is O of n log n. Most engineers stop there. But there is a better strategy. Walk the array from the bottom up, and sift each node down. The math works out to O of n.

5:45 Linear time to build the entire heap. Linear time. Almost nobody guesses that on a whiteboard. The intuition behind the math is that most nodes in a heap are leaves, and leaves require zero sift-down work. The next level up has half as many nodes and at most one swap each. Each higher level has half as many nodes again with one more potential swap. The sum across all levels collapses to a constant times n, not n times log n. The lesson is broader than this one algorithm. Where the work is concentrated in your structure determines its real cost, not just where the loops appear in the code.

6:22 Three places heaps run in production. Dijkstra's algorithm uses a min-heap to pick the next-closest unvisited node, and we will dig into that one in chapter twelve. Operating system schedulers use a heap to pick the next task to run, ordered by priority or deadline. Every "give me the top one hundred highest-rated items" problem becomes a heap of size one hundred, and you walk the data set once. The classic name is the top-K problem, and the heap is the standard answer. One last extension. The deque, pronounced deck, is a double-ended queue.

6:57 Push and pop are both O of one at either end. Python's collections deque type is one. The deque shows up in sliding-window algorithms, where you need to drop old items off the front and add new items to the back as a window moves across an array. Same idea as a queue, just open at both ends. Right. Most "process the last K items" patterns use a deque underneath. The classic example is the sliding-window maximum problem. You have an array of a million numbers and a window of size one hundred. For each window position, return the largest value.

7:30 The naive solution is one hundred million comparisons. The deque-based solution does it in linear time by keeping the deque monotonic: the front always holds the current maximum, and you pop from the back any value that is smaller than the new arrival. So the practical version. When you have a one-end constraint and you only care about the most recent thing, use a stack. When you have a strict order-of-arrival constraint, use a queue. When you need the next-best item by some priority, and the priority can change as new items arrive, use a heap.

7:59 And when you find yourself iterating to find the K largest or K smallest items, that is a heap of size K, not a sort. Pick the structure that makes the hot operation cheap. Same lesson as every chapter. The data structure is the agreement about which operations get to be fast. Three small structures. Most of the scheduling, traversal, and ranking in your code lives on top of one of them. Next chapter we look at the structure your call stack is already using. Recursion, call stacks, and memoization.

8:29 Thanks for listening to Learning Podcasts.