05. Stacks and Queues

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 - 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.

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) {
    q.data[q.tail] = val
    q.tail = (q.tail + 1) % q.cap
    q.size++
}

func (q *RingQueue) Dequeue() int {
    val := q.data[q.head]
    q.head = (q.head + 1) % q.cap
    q.size--
    return val
}

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.

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
}

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)