05. Stacks and Queues

🎁 The undo button, the browser back button, and every function call your program makes all rely on the same invisible data structure. What is it?

Stacks and queues are restricted data structures. They limit how you access elements — and that restriction is the point. By constraining access to one end (stack) or two ends (queue), you get structures that model real problems naturally: undo history, function calls, task scheduling, breadth-first search.

Stacks — Last In, First Out

A stack lets you push to the top and pop from the top. The last thing you added is the first thing you remove. Think of a stack of plates.

// Stack using a slice
stack := []int{}

stack = append(stack, 1)  // push
stack = append(stack, 2)  // push
stack = append(stack, 3)  // push

top := stack[len(stack)-1]          // peek — 3
stack = stack[:len(stack)-1]        // pop — removes 3

All operations are O(1). No need for a special type in Go — a slice with append/truncate is a stack.

Where Stacks Appear

Function call stack — every function call pushes a frame, every return pops it. Recursion is just the call stack doing the work for you.

Undo/redo — each action pushes to the undo stack. Undo pops and pushes to redo.

Expression evaluation — parsing (3 + (4 * 2)) uses a stack to match parentheses and track operator precedence.

LeetCode 20 - Valid Parentheses

Given a string containing just the characters (, ), {, }, [ and ], determine if the input string is valid.

// Valid parentheses — O(n)
func isValid(s string) bool {
    stack := []rune{}
    pairs := map[rune]rune{')': '(', ']': '[', '}': '{'}
    for _, ch := range s {
        if ch == '(' || ch == '[' || ch == '{' {
            stack = append(stack, ch)
        } else {
            if len(stack) == 0 || stack[len(stack)-1] != pairs[ch] {
                return false
            }
            stack = stack[:len(stack)-1]
        }
    }
    return len(stack) == 0
}

Monotonic Stack

A stack where elements are always in sorted order (increasing or decreasing). Used to find the "next greater element" or "previous smaller element" in O(n).

LeetCode 496 (simplified) - Next Greater Element I

// Next greater element for each position — O(n)
func nextGreater(nums []int) []int {
    n := len(nums)
    result := make([]int, n)
    for i := range result {
        result[i] = -1
    }
    stack := []int{} // stores indices

    for i := 0; i < n; i++ {
        for len(stack) > 0 && nums[i] > nums[stack[len(stack)-1]] {
            idx := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            result[idx] = nums[i]
        }
        stack = append(stack, i)
    }
    return result
}

Without a monotonic stack, this is O(n²) — for each element, scan right to find the next greater. The stack makes it O(n) because each element is pushed and popped at most once.

Queues — First In, First Out

A queue lets you add to the back and remove from the front. First thing in is the first thing out. Think of a line at a store.

// Queue using a slice (simple but not ideal for large queues)
queue := []int{}

queue = append(queue, 1)  // enqueue
queue = append(queue, 2)  // enqueue
queue = append(queue, 3)  // enqueue

front := queue[0]         // peek — 1
queue = queue[1:]         // dequeue — removes 1

Note: queue[1:] doesn't free memory — the underlying array still holds the removed element. This is a real problem for long-running queues.

The Slice Queue Memory Leak

When you dequeue with queue = queue[1:], the slice header moves forward but the backing array never shrinks. Old elements stay in memory, unreachable but not garbage collected.

queue := make([]int, 0, 1000)
// Enqueue 1000 items, dequeue 999
// queue now has len=1, but the backing array still holds 1000 slots
// The first 999 elements are wasted memory

For short-lived queues (BFS on a small graph), this is fine. For long-running queues (server request buffers, event streams), it's a memory leak.

Alternatives:

• Ring buffer — fixed-size array with wrapping head/tail pointers (see below)
• container/list — Go's standard library linked list; each node is GC'd on removal
• Periodic re-slice — copy remaining elements to a fresh, smaller slice when utilization drops below a threshold

Ring Buffer (Circular Queue)

A ring buffer uses a fixed-size array with head and tail pointers that wrap around using modulo. Dequeue actually reuses memory.

type RingQueue struct {
    data       []int
    head, tail int
    size, cap  int
}

func NewRingQueue(capacity int) *RingQueue {
    return &RingQueue{data: make([]int, capacity), cap: capacity}
}

func (q *RingQueue) Enqueue(val int) bool {
    if q.size == q.cap {
        return false // full
    }
    q.data[q.tail] = val
    q.tail = (q.tail + 1) % q.cap
    q.size++
    return true
}

func (q *RingQueue) Dequeue() (int, bool) {
    if q.size == 0 {
        return 0, false // empty
    }
    val := q.data[q.head]
    q.head = (q.head + 1) % q.cap
    q.size--
    return val, true
}

The % cap wraps the pointer back to 0 when it reaches the end. No memory is wasted — slots are reused as soon as they're dequeued. All operations are O(1) with no amortized cost.

Where Queues Appear

BFS (Breadth-First Search) — the most important use. Process nodes level by level.

// BFS traversal of a graph
func bfs(graph map[int][]int, start int) []int {
    visited := map[int]struct{}{start: {}}
    queue := []int{start}
    order := []int{}

    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        order = append(order, node)

        for _, neighbor := range graph[node] {
            if _, ok := visited[neighbor]; !ok {
                visited[neighbor] = struct{}{}
                queue = append(queue, neighbor)
            }
        }
    }
    return order
}

Task scheduling — process jobs in the order they arrive.

Rate limiting — sliding window of timestamps.

Deque — Double-Ended Queue

A deque allows push/pop from both ends in O(1). Useful for sliding window maximum and problems where you need both stack and queue behavior.

Go has no built-in deque. In practice, a slice works fine for algorithm problems:

deque := []int{}

deque = append(deque, val)        // push back
deque = deque[:len(deque)-1]      // pop back
deque = deque[1:]                 // pop front
front := deque[0]                 // peek front
back := deque[len(deque)-1]       // peek back

The "pop front" has the same memory leak as slice queues, but for short-lived algorithm code (BFS, sliding window) it doesn't matter. For production code, use container/list or a ring buffer that grows in both directions.

LeetCode 239 - Sliding Window Maximum

Given an array and a sliding window of size k, return the maximum value in each window position.

// Sliding window maximum using a deque — O(n)
func maxSlidingWindow(nums []int, k int) []int {
    deque := []int{}   // stores indices, front is always the max
    result := []int{}

    for i := 0; i < len(nums); i++ {
        // Remove elements outside the window
        for len(deque) > 0 && deque[0] <= i-k {
            deque = deque[1:]
        }
        // Remove smaller elements from back (they'll never be the max)
        for len(deque) > 0 && nums[deque[len(deque)-1]] < nums[i] {
            deque = deque[:len(deque)-1]
        }
        deque = append(deque, i)

        if i >= k-1 {
            result = append(result, nums[deque[0]])
        }
    }
    return result
}

Trace: nums = [4, 3, 5, 2, 1, 6], k = 3

The deque stores indices. It stays in decreasing order of values — front is always the window max.

Result: [5, 5, 5, 6]

Key observations:

• i=2: 5 enters and wipes [4,3] — they can never be max while 5 is in the window
• i=5: index 2 expires (outside window [3,4,5]), then 6 wipes everything else
• Each element enters and leaves the deque exactly once → O(n) total

Operation Costs

When to Use Stack vs Queue

Stack when:

• You need to reverse order or backtrack
• Matching pairs (parentheses, HTML tags)
• DFS traversal (iterative)
• Monotonic problems (next greater/smaller)

Queue when:

• You need to process in arrival order
• BFS traversal
• Level-order processing
• Scheduling and buffering

Deque when:

• You need both stack and queue behavior
• Sliding window problems
• You need O(1) access to both ends

Practice Problems

Key Takeaways

• Stacks are LIFO (last in, first out) — use a slice with append/truncate in Go
• Queues are FIFO (first in, first out) — foundation of BFS
• Monotonic stacks solve "next greater/smaller" problems in O(n) instead of O(n²)
• Deques give O(1) operations at both ends — used for sliding window maximum
• The restriction IS the feature — limiting access makes the structure match the problem
• BFS always uses a queue; DFS always uses a stack (or recursion, which is an implicit stack)

🎁 Inserting into the middle of an array means shifting everything after it. What if there's a structure where insertion is always O(1), no matter where?