Stacks and Queues: The Workhorses

There is nothing new to build this lesson. That's not a day off; it's the whole point. The two structures the last lesson promised, the stack and the queue, are barely structures at all. They're rules. Disciplines you impose on things you already own. A stack is one sentence: you may only touch the most recent thing. A queue is one sentence: things leave in the order they arrived.

And the audition lesson 5 set up, array versus list, comes with a twist: the job description is shorter than either resume. Both candidates can do the work. The interesting question is what each one charges.

But first, the deeper idea, because it's the reason these two run more production code than anything else in this course. When a structure can only be touched one way, every piece of code that touches it becomes predictable. You never have to ask "what could happen to this collection?" The contract tells you. That predictability is why these two are everywhere: the undo button, the call stack, the print queue, the message broker. All of it runs on two one-sentence rules.

The stack: you may only touch the top

The rule in full: you may add only on top (push), remove only from the top (pop), and glance at the top (peek). That's the entire interface. Last in, first out: LIFO.

Now watch how much software falls out of one rule. Press Ctrl+Z in any editor on earth. Every edit you make, the editor pushes the inverse of that edit onto a stack. You typed "hello"? It pushes "delete 5 characters". You deleted a paragraph? It pushes the paragraph back. Undo is just pop: execute whatever comes off the top. And the popped edit doesn't vanish; it gets pushed onto a second stack, the redo stack, and redo pops that one.

Which explains a detail everyone has felt but never named: undo a few times, then type something new, and redo stops working. A new edit clears the redo stack, because there's no honest way to redo on top of a different history. Your browser plays the exact same trick: back pops one stack and pushes the other, forward goes the opposite way, and navigating somewhere new empties the forward stack. Same structure, same rule, same little heartbreak.

The stack you already built

So who gets the job? Here's the anticlimax: you already built a stack in lesson 3 and called it something else. Take the dynamic array:

• push is append: write at index length, bump length. O(1) amortized, with lesson 1's doubling math.
• pop is: read the last element, drop length by one. O(1), no asterisk at all.
• peek is: read index length - 1. O(1).

Remember what was actually expensive about arrays: never the end. The front and the middle, where everything shifts. A stack never goes near the front. It lives entirely at the cheap end, hitting the same hot cache line over and over, the access pattern lesson 2 showed the hardware loves most.

The linked list auditions fine too: push and pop at the head, two pointer writes each. But it pays a pointer per element, an allocation per push, and a cache miss per hop, to win a job the array does with none of those. So every real stack you'll meet is an array touched only at one end. Python's list. C++'s std::stack, which is literally an adapter wrapped around a vector. And Go doesn't even ship a stack type, because the slice idiom is one:

stack = append(stack, x)      // push
x = stack[len(stack)-1]       // peek
stack = stack[:len(stack)-1]  // pop

The discipline costs nothing extra. It's just a promise to never use the operations that were slow anyway.

The bracket matcher

Now the marquee demo: the one piece of stack code every working programmer should be able to write from memory. Your editor runs it to rainbow your brackets. Your linter runs it. Every compiler that ever told you "missing closing brace" ran it. The question: in a string of (), [], and {}, does every opener have the right closer, in the right order?

Here's the insight. The bracket you must close next is always the one you opened most recently. Most recent first: that is the stack's exact contract. So the algorithm is a handful of lines:

function is_balanced(s):
    stack = empty stack
    pairs = { ")": "(", "]": "[", "}": "{" }
    for each ch in s:
        if ch is an opener:
            push(stack, ch)
        else if ch is a closer:
            if stack is empty: return false      # a closer with nothing open
            if pop(stack) != pairs[ch]: return false   # wrong pair off the top
    return stack is empty                        # leftovers = unclosed openers

Watch it run on {()}. Push {. Push (. First closer arrives: pop, it's the (, matches. Then }: pop, the {, matches. String over, stack empty. Valid.

Now feed it (]. Push the (. The closer arrives: pop, and a ( meets a ]. Mismatch. Reject.

Three ways to fail, and only three: a wrong pair off the top, a closer when the stack is empty, leftovers when the string ends. One pass, O(n). This is the canonical interview pattern and how real parsers track nesting; the same shape, with richer items on the stack, validates your JSON and balances your HTML tags.

The most famous stack

One more stack deserves its name spoken, because you're running it right now. Every time a function calls another function, the runtime pushes a frame: the local variables plus the address to return to. When the function returns, its frame pops, and execution lands exactly where the caller left off. That's the call stack, and notice it's the same insight as the brackets: the function you must return to next is the one that called most recently.

Call deep enough, a thousand frames, ten thousand, and the push that runs out of room throws the most famous error in programming: stack overflow. Yes, the website is named after it. That one beat is all this lesson takes; lesson 9 opens the machine up properly, frames, recursion, and why every recursive algorithm is secretly carrying a stack around.

The queue: in one end, out the other

The queue's rule is the mirror image: add at the back (enqueue), remove from the front (dequeue). First in, first out: FIFO. A line at a ticket counter, enforced by code, with both operations O(1).

Notice what the contract actually is: fairness. Order preserved, nothing skips the line, nothing starves at the back of it. Which is exactly what you want the moment work arrives faster than you can do it. Your printer queues jobs. Your web server queues the requests it can't take yet. And at datacenter scale the same discipline gets a grander name: the message queue. Amazon's SQS, RabbitMQ. One service produces work at its own pace, another consumes at its own pace, and a queue between them absorbs the mismatch. Billions of dollars of infrastructure, and the contract is still the line at the counter.

One more customer worth naming now, because it's coming: when this course reaches graphs, breadth-first search, the algorithm that explores level by level, runs entirely on a queue. The frontier of that search is a queue, and lesson 17 will lean on everything below.

The wrong end

So who implements it? This time the audition gets interesting, because the obvious answer is a trap.

Take the dynamic array again. Enqueue at the back is append: O(1), fine. Dequeue from the front is remove index 0, the array's one forbidden move: every element shifts left by one slot. A thousand items waiting, a thousand moves per dequeue.

This isn't hypothetical; it ships constantly. Python's list.pop(0). JavaScript's Array.prototype.shift(). Both look exactly as innocent as append, both are one method call, and both are O(n) every single call. Drain a queue of n items that way and you've paid n²/2 moves, the same quiet parabola that's been stalking this course since lesson 1. It's Shlemiel the painter from lesson 4 all over again: doing the job from the wrong end, over and over.

So the array, the candidate that swept the stack audition, stumbles. The stack only ever needed one cheap end. The queue needs two, and a plain array only has one. There are two real fixes.

Fix one: the linked list, finally hired

The guessable fix: a linked list with a head and a tail pointer, exactly the upgrade lesson 5 described. Dequeue at the head, enqueue at the tail, two pointer writes each. O(1), honestly, no asterisk, and notice it never violates lesson 5's honest rule: a queue never asks for element i.

It works and it ships. But it pays the toll you know by heart now: an allocation per enqueue, a pointer per element, a cache miss per hop.

Fix two: the ring buffer

The prettier fix keeps the array and kills the shifting with one question: who said the front of the queue has to be index 0?

Keep two numbers alongside the buffer: head, the index where the front currently lives, and count, how many elements are in the queue.

• dequeue: read the element at head, then move head forward one. Nothing shifts; the old slot is simply abandoned.
• enqueue: write at head + count, bump count.

Both ends are now cheap, because neither end ever moves anything. One problem left: head keeps marching right and eventually walks off the end of the array. So bend the array into a circle. When an index steps past the last slot, wrap it back to slot 0: every index is computed modulo capacity. The freed slots at the start get reused, and the queue chases its own tail around one fixed block of memory, forever. That's the ring buffer (or circular buffer): the contiguous layout lesson 2 crowned, wearing the queue contract, with not a single element ever copied.

Walk one to make it concrete. Capacity 8, head = 0, count = 0:

enqueue 5 jobs      slots 0..4 filled         head=0  count=5
dequeue 3           head walks to slot 3       head=3  count=2
enqueue 6 more      writes land in 5,6,7...    head=3  count=8
                    ...then slot 0. wrapped.   buffer full

The buffer is full, the front of the queue sits in the middle of the array, and that's perfectly fine: the two numbers tell us everything.

Full, and the system saying slow down

Every ring buffer must answer one question: what happens when it's full? Two honest answers.

Answer one: grow. Allocate double, copy the elements out in queue order so they unwrap flat into the new block starting at slot 0, reset head to 0. Lesson 3's amortized doubling, with a twist in the copy.

Answer two: refuse. Return "full" and make the producer wait. That sounds like a failure; it's a feature with a name: backpressure. A bounded queue is the system saying "slow down, I'm at capacity", which beats the unbounded alternative: a queue that silently eats memory until the process dies. Overload doesn't disappear just because you hid it in a queue.

And this exact machine is load-bearing in tools you used today:

• A buffered channel in Go is a ring buffer: a fixed block, a send index, a receive index, a count, precisely the structure above. When it fills, the sending goroutine blocks. Backpressure, built into the language.
• The Linux kernel's newest I/O interface, io_uring, is literally named for its two rings: one ring of requests from your program, one ring of completions coming back.
• Audio drivers feed your speakers from a ring; network cards deliver packets into rings. Anywhere data flows between two parties at different speeds, there's a ring absorbing the difference.

One party trick before the last structure, because it earns its keep in interviews: you can build a queue out of two stacks. Enqueue pushes onto the first. Dequeue pops from the second, and when the second runs empty, pour the first into it, pop by pop, which reverses the order on the way over. Any single dequeue might move everything, but each element makes at most two moves in its entire life, so it's O(1) amortized: lesson 1's token bank, paying out again.

The deque

One promise left to honor from lesson 5. The deque (double-ended queue, pronounced "deck"): push and pop at the front and the back, all O(1). The greedy structure, both ends cheap.

You could bolt a doubly linked list on, but the standard libraries do something smarter, the design teased when the list lost its verdict: chunked arrays. Python's collections.deque and C++'s std::deque both keep a chain of fixed-size blocks, contiguous inside, plus a small index of pointers to the blocks. Need room at the front? Add one block at the front of the index; nothing shifts. Walking it is mostly sequential and cache-friendly, because inside every block it's just an array. The list's flexibility at the ends, the array's locality in the middle, both nearly free.

When do you genuinely need both ends? The flagship case is the sliding window maximum, a window gliding over data while a deque tracks the best candidates. That's not this lesson; that's the next one.

And one structure you might expect here is missing on purpose: a queue where the line can be jumped, where the most urgent item leaves first, is a priority queue, and that takes a genuinely new machine: lesson 15's heap.

The ring buffer, in real code

The videos stay in pseudocode; here is a working ring-buffer queue in the three languages this course carries. The stack needs no section of its own: it's the lesson 3 dynamic array used politely, and the Go snippet above is the whole idea. The queue is where implementation actually earns its keep.

The TypeScript version is the growing flavor (answer one). The Go version is the bounded flavor (answer two), because bounded-with-backpressure is the shape Go's own channels chose. The C++ version grows, with the capacity owned by a vector.

class RingQueue<T> {
  private buf: (T | undefined)[]
  private head = 0
  private count = 0
 
  constructor(capacity = 8) {
    this.buf = new Array(capacity)
  }
 
  get size(): number {
    return this.count
  }
 
  enqueue(x: T): void {
    if (this.count === this.buf.length) this.grow()
    this.buf[(this.head + this.count) % this.buf.length] = x
    this.count++
  }
 
  dequeue(): T {
    if (this.count === 0) throw new Error("queue is empty")
    const x = this.buf[this.head] as T
    this.buf[this.head] = undefined // drop the reference so GC can reclaim it
    this.head = (this.head + 1) % this.buf.length
    this.count--
    return x
  }
 
  private grow(): void {
    const next = new Array<T | undefined>(this.buf.length * 2)
    for (let i = 0; i < this.count; i++) {
      next[i] = this.buf[(this.head + i) % this.buf.length] // unwrap in queue order
    }
    this.buf = next
    this.head = 0 // the queue now starts flat at slot 0
  }
}

type RingQueue struct {
	buf   []int
	head  int
	count int
}
 
var ErrFull = errors.New("queue full")
 
func NewRingQueue(capacity int) *RingQueue {
	return &RingQueue{buf: make([]int, capacity)}
}
 
func (q *RingQueue) Enqueue(x int) error {
	if q.count == len(q.buf) {
		return ErrFull // backpressure: the caller decides to wait, drop, or fail
	}
	q.buf[(q.head+q.count)%len(q.buf)] = x
	q.count++
	return nil
}
 
func (q *RingQueue) Dequeue() (int, bool) {
	if q.count == 0 {
		return 0, false
	}
	x := q.buf[q.head]
	q.head = (q.head + 1) % len(q.buf)
	q.count--
	return x, true
}

class RingQueue {
    std::vector<int> buf_;
    std::size_t head_ = 0;
    std::size_t count_ = 0;
 
public:
    explicit RingQueue(std::size_t capacity = 8) : buf_(capacity) {}
 
    std::size_t size() const { return count_; }
 
    void enqueue(int x) {
        if (count_ == buf_.size()) grow();
        buf_[(head_ + count_) % buf_.size()] = x;
        ++count_;
    }
 
    int dequeue() {
        assert(count_ > 0);
        int x = buf_[head_];
        head_ = (head_ + 1) % buf_.size();
        --count_;
        return x;
    }
 
private:
    void grow() {
        std::vector<int> next(buf_.size() * 2);
        for (std::size_t i = 0; i < count_; ++i)
            next[i] = buf_[(head_ + i) % buf_.size()]; // unwrap in queue order
        buf_ = std::move(next);
        head_ = 0;
    }
};

Walk the load-bearing lines of the TypeScript version. enqueue writes at (head + count) % length: the modulo is the "bend it into a circle" move, and it's the only arithmetic in the structure. dequeue never touches any element but the front one; it clears the slot (so a popped object isn't kept alive by a stale reference) and walks head forward, wrapping the same way. grow is where the unwrap twist lives: it copies element i of the queue, not slot i of the array, so a wrapped queue lands flat in the new buffer and head resets to 0. Forget that and a wrapped queue grows into garbage.

The Go version has the same two lines of index math, but Enqueue returns an error instead of growing. That ErrFull is the entire backpressure mechanism: the producer now knows the consumer is behind and must choose a policy. A real buffered channel makes that choice for you by blocking the goroutine; a job system might drop the oldest item instead; a web server might return 503. The point is the bound forces the decision into the open.

In the C++ version, note what grow does not do: it doesn't call buf_.resize(). Resizing in place would add empty slots at the end of the block, in the middle of a wrapped queue, splitting it in half. The new vector plus unwrap-copy is the only correct shape, and std::move hands the old block over without a second copy. One more production note: real high-performance rings (Go's channel buffer included) often skip % entirely by keeping capacity a power of two and masking with capacity - 1, because integer division is one of the slower things an ALU does. Same structure, cheaper wrap.

The contract was the product

So, the workhorses, and the real lesson underneath them. Nothing new was built today. An array touched at one end became the undo button, the bracket matcher, the call stack. An array bent into a circle became the channel buffer and half the kernel's plumbing. The structures were already on the shelf; the value was the contract. You may only touch one end. In one end, out the other. Constraints aren't a loss of power; they're what make code you can reason about and systems that don't surprise you.

Hold that thought, because everything coming next runs on it. So far this course has walked arrays one element at a time, one finger tracing the data. Next lesson, the first real algorithm patterns of the course: two pointers, and the sliding window. The same arrays you've had since lesson 2, but now two fingers walk them in choreography, and entire families of O(n²) problems collapse into a single pass. The structures are built. Time to make them dance.