Stacks & Queues

Stacks

A stack is last in, first out (LIFO): push adds to the top, pop removes from the top. Whenever a problem has nested structure — brackets, function calls, undo history — the most recently opened item is the first one that must be closed, and a stack tracks it.

Slice-Backed Stack

Use the end of a slice as the top: push is append (amortized O(1)) and pop shrinks the length (O(1)). Clearing the popped slot matters when T holds pointers: otherwise the backing array keeps the popped object alive and the garbage collector cannot free it.

type Stack[T any] struct{ items []T }

func (s *Stack[T]) Push(v T) { s.items = append(s.items, v) }

func (s *Stack[T]) Pop() (T, bool) {
	var zero T
	if len(s.items) == 0 {
		return zero, false // report "empty" instead of panicking
	}
	v := s.items[len(s.items)-1]
	s.items[len(s.items)-1] = zero // release references for the GC
	s.items = s.items[:len(s.items)-1]
	return v, true
}

Matching Brackets

Push every opening bracket; on a closing bracket, pop and check that it matches. The input is balanced if no pop fails and the stack is empty at the end. Storing positions instead of characters costs nothing and lets the function report where the error is — the approach compilers and JSON parsers use.

// balanced returns (true, -1) or (false, index of the first error).
func balanced(s string) (bool, int) {
	pairs := map[rune]rune{')': '(', ']': '[', '}': '{'}
	var st Stack[int] // positions of unmatched openers
	runes := []rune(s)
	for i, c := range runes {
		switch c {
		case '(', '[', '{':
			st.Push(i)
		case ')', ']', '}':
			top, ok := st.Pop()
			if !ok || runes[top] != pairs[c] {
				return false, i // no opener, or the wrong kind
			}
		}
	}
	if len(st.items) > 0 {
		return false, st.items[len(st.items)-1] // opened, never closed
	}
	return true, -1
}

Evaluating Expressions

In postfix notation (Reverse Polish Notation), operators follow their operands: 3 4 2 * + means 3 + 4 × 2. Evaluation needs one stack and no precedence rules: push numbers; an operator pops two operands and pushes the result. Dijkstra's shunting-yard algorithm converts ordinary infix expressions to postfix with a second stack that holds operators until an operator of lower or equal precedence, or a closing parenthesis, releases them. Together they form a small calculator — the same two-stage design used by many interpreters and stack-based virtual machines.

Undo and Redo

An editor keeps two stacks. Each edit pushes the previous state onto undo. Undo pops from it and pushes the current state onto redo; redo does the reverse. Any new edit clears the redo stack, because the undone future no longer applies. Brackets, RPN, shunting-yard, and undo/redo in one program: 18_stack_applications.go.

Queues

A queue is first in, first out (FIFO): enqueue at the back, dequeue at the front. Queues model waiting lines — print jobs, network packets, tasks for workers — and drive breadth-first search in Phase 3.

A ring buffer treats a fixed array as a circle. The queue a, b, c, d wraps from the end of the array back to index 0; freed slots are reused instead of reallocated.

The Naive Slice Queue

The obvious implementation enqueues with q = append(q, x) and dequeues with q = q[1:]. Both are O(1), but the start of the slice only ever moves forward: dequeued slots at the front are never written again. Once the end of the backing array is reached, append allocates a new array, and the old one becomes garbage. Under steady traffic the queue keeps allocating memory in proportion to the total number of items that ever passed through, not the number currently waiting.

Ring Buffer

A ring buffer keeps a fixed array, the index of the front element, and a count. Positions wrap around with modulo arithmetic, so the slot freed by a dequeue is reused by a later enqueue. When the array is full, it doubles in size and copies the elements into order, which keeps every operation O(1) amortized.

type Queue[T any] struct {
	buf  []T
	head int // index of the front element
	size int // number of stored elements
}

func (q *Queue[T]) PushBack(v T) {
	if q.size == len(q.buf) {
		q.grow() // double capacity and unroll the ring so head == 0
	}
	q.buf[(q.head+q.size)%len(q.buf)] = v // the tail wraps around
	q.size++
}

func (q *Queue[T]) PopFront() (T, bool) {
	var zero T
	if q.size == 0 {
		return zero, false
	}
	v := q.buf[q.head]
	q.buf[q.head] = zero
	q.head = (q.head + 1) % len(q.buf) // the head wraps around
	q.size--
	return v, true
}

In the demo, 100,000 jobs pass through each queue in bursts of 100. The ring buffer allocates a few hundred slots in total; the naive queue allocates hundreds of thousands: 19_ring_buffer_queue.go.

Deques

A deque (double-ended queue) supports push and pop at both ends. The ring buffer already has everything needed: PushFront steps the head back one slot — (head − 1 + len) % len, where adding len keeps the result non-negative — and PopBack reads the slot before the tail. A deque can serve as a stack, a queue, or both, and it is the core of the sliding-window maximum below.

Channels Are Not General Queues

A buffered Go channel is a FIFO queue designed for passing values between goroutines, with blocking and synchronization built in. Inside a single goroutine it is the wrong tool: its capacity is fixed, and sending to a full channel blocks forever — the runtime then aborts with fatal error: all goroutines are asleep - deadlock!. Use a slice or ring buffer for algorithmic queues and channels for communication.

Monotonic Stacks and Deques

A monotonic stack keeps its elements in sorted order. Before pushing a new element, it pops everything that would break the order, and each pop is the moment an answer becomes known. A single push may pop many elements, but every element is pushed once and popped at most once, so the total work is O(n) — an amortized argument like the one for append.

Next Greater Element

For each element, find the first larger element to its right. The stack holds indices still waiting for an answer; their values decrease from bottom to top. A new value answers every waiting element smaller than itself.

func nextGreater(nums []int) []int {
	res := make([]int, len(nums))
	for i := range res {
		res[i] = -1 // default when no greater element exists
	}
	var stack []int // indices waiting for an answer
	for i, v := range nums {
		for len(stack) > 0 && nums[stack[len(stack)-1]] < v {
			res[stack[len(stack)-1]] = v // v answers the top index
			stack = stack[:len(stack)-1]
		}
		stack = append(stack, i)
	}
	return res
}

Largest Rectangle in a Histogram

The widest rectangle that uses a bar's full height extends left and right until it meets a shorter bar. An increasing stack finds both limits at once: when a bar is popped, the bar that pops it is its right limit and the bar beneath it on the stack is its left limit. A final bar of height zero flushes the remaining stack. This problem is a standard example of a difficult question that becomes simple and linear once you see the stack invariant.

Sliding Window Maximum

To report the maximum of every window of size k, keep a deque of indices whose values decrease from front to back. The front is always the current maximum; it leaves when it slides out of the window. A new value evicts smaller values from the back, because they can never be a maximum again — the new value is larger and stays in the window longer. All four problems, each cross-checked against a brute-force version on 3,000 random inputs: 20_monotonic_stack.go.

Common Pitfalls

Stack and queue code is short, so its bugs hide in edge cases.

Popping an Empty Container

s[len(s)-1] on an empty slice panics with an index out of range. Return a (value, ok) pair, as the implementations above do, and handle the empty case at each call site — an unmatched closing bracket is exactly this case.

Popped Items That Never Die

Shrinking a slice's length does not clear the slots beyond it. If the elements are pointers, large structs, or slices, the backing array keeps them reachable. Zero the slot before shrinking, as Pop and PopFront do.

Negative Modulo

In Go, -1 % 8 is -1, not 7: the result takes the sign of the dividend. Stepping an index backward in a ring buffer needs (i - 1 + n) % n.

Practice Lab

For each exercise, decide first whether the problem is about "most recent" (stack) or "oldest" (queue).

Run the Demos

1. In 18_stack_applications.go, add the ^ (power) operator to the shunting-yard converter. It is right-associative: 2 ^ 3 ^ 2 is 2⁹ = 512. Which comparison must change?
2. In 19_ring_buffer_queue.go, add a shrink step that halves the buffer when it is less than a quarter full. Why a quarter and not a half?

Exercises

1. Min stack. Build a stack that returns its minimum in O(1). Hint: push pairs of (value, minimum so far).
2. Queue from two stacks. Implement a FIFO queue using only two stacks, with O(1) amortized operations. Explain the amortized argument.
3. Simplify a path. Turn /a/./b/../../c/ into /c using a stack of directory names.
4. Stock span. For each day's price, count the consecutive preceding days (including today) with a price at most today's — with a monotonic stack.

Next lesson: Hash Tables.