Lesson 13
Stacks & Queues: Order Is the Feature
Last-in-first-out vs first-in-first-out — two tiny rules that power undo, parsing and BFS.
01Why it matters & the intuition
Stacks drive function calls, undo history, bracket matching and DFS. Queues drive task schedulers, message brokers and BFS. They restrict what you can do — and that restriction is what makes them fast and predictable.
Think of it like…
A stack is a pile of plates: you add and remove from the top. A queue is the line at a chai stall: first to arrive, first to be served.
02See it move
Press play, then step through slowly. Change the input and predict the next frame before you click.
Stack · LIFO
top ↑
Queue · FIFO
03Key ideas
Stack (LIFO)
push adds to the top, pop removes from the top, peek looks without removing. An array's end is a perfect stack.
Queue (FIFO)
enqueue at the back, dequeue from the front. array.shift() is O(n) — use a head index or a linked list for O(1).
Deque
Double-ended queue: push/pop at both ends in O(1). The workhorse of the sliding-window maximum pattern.
Monotonic stack
A stack kept in sorted order answers 'next greater element' questions in O(n) total.
04Build it from scratch
A clean reference implementation. Read it line by line — then close it and write your own in the lab below.
class Stack<T> {
private items: T[] = [];
push(x: T) { this.items.push(x); }
pop(): T | undefined { return this.items.pop(); }
peek(): T | undefined { return this.items[this.items.length - 1]; }
get size() { return this.items.length; }
}
// O(1) queue: never shift — advance a head index and compact occasionally.
class Queue<T> {
private items: T[] = [];
private head = 0;
enqueue(x: T) { this.items.push(x); }
dequeue(): T | undefined {
if (this.head >= this.items.length) return undefined;
const x = this.items[this.head++];
if (this.head > 1024 && this.head * 2 > this.items.length) {
this.items = this.items.slice(this.head);
this.head = 0;
}
return x;
}
get size() { return this.items.length - this.head; }
}05Complexity
| Operation | Time | |
|---|---|---|
| Stack push / pop / peek | O(1) | — |
| Queue enqueue / dequeue (head index) | O(1) | — |
| array.shift() as dequeue | O(n) — avoid | — |
06Check your understanding
07Code lab
Write Python(or switch to JavaScript) and run it against real test cases. Python runs inside your browser — nothing is uploaded — and a C++ reference solution is under “Solution”.
Valid brackets
Write is_valid(s) returning true if every (, [, { in s is closed by the matching bracket in the correct order.