Stacks & Queues

Stack — LIFO (last in, first out)

Like a stack of plates: you push a new plate on top, and you take from the top. The most-recently-added thing is the next one out. Operations:

• push(x) — add x to the top.
• pop() — remove and return the top element.
• top() — peek at the top without removing.

All O(1). Easy to implement on top of a vector — push at the back, pop from the back.

std::stack<int> s;
s.push(10);
s.push(20);
s.push(30);
s.top();     // 30
s.pop();     // removes 30
s.top();     // 20

Where stacks show up:

• The call stack itself. When function A calls B, B's frame goes on the stack. When B returns, it's popped. This is why "stack overflow" happens — too many nested calls.
• Undo/redo. Each action gets pushed; "undo" pops.
• Bracket matching. Walk through code: push every open bracket, pop on close, error if mismatch.
• Depth-first search. An iterative DFS uses a stack of nodes-to-visit.
• Expression evaluation. Reverse Polish notation is evaluated by a stack.

Queue — FIFO (first in, first out)

Like a line at the bakery: first one in is first one served. Operations:

• push(x) / enqueue(x) — add to the back.
• pop() / dequeue() — remove and return the front element.
• front() — peek at the front.

All O(1) with the right backing — the standard library uses std::deque internally.

std::queue<int> q;
q.push(10);
q.push(20);
q.push(30);
q.front();   // 10
q.pop();     // removes 10
q.front();   // 20

Where queues show up:

• Task schedulers. Operating system run-queue. Print-job queue. Network packet buffer.
• Breadth-first search. Visit nodes in order of distance from the source. Used for shortest-path on unweighted graphs and pathfinding in many games.
• Producer-consumer pipelines. One thread pushes, another pops. (Need thread-safe variants for that.)
• Streaming systems. Kafka, RabbitMQ, AWS SQS — all are durable distributed queues at heart.

Priority queue — the close cousin

What if "first in" is the wrong order? std::priority_queue orders by priority: highest-priority item comes out first, regardless of insertion order. Internally it's a heap — a tree where each parent is bigger than its children — giving O(log n) push and pop.

Used heavily in Dijkstra's shortest-path, A* pathfinding, scheduler with priorities, top-K problems, and event simulation. Whenever the answer to "what's next?" depends on more than insertion order, you want a priority queue.

Why this matters for AI

Every AI training pipeline has at least two queues in it: the data loader queue (one thread reading files from disk, others batching them, the GPU thread popping ready batches), and the gradient queue (in distributed training, accumulated gradients flow through a queue to a parameter server). The throughput of an entire training cluster is limited by how well those queues are designed.

Stacks: every recursive function in a transformer's autograd graph is, ultimately, the C++ runtime's call stack. The chef has been pushing and popping the whole time.

Two operations each, three lines of code, half of computing.

What's next

One last data structure for Phase 4 — and the most general of them all. Beyond rows and chains and stacks, beyond ordered keys and unordered keys, lies the structure that captures arbitrary relationships between things.

Week 36 is Trees & Graphs.