{} The Go Reference

Linear · DSA · Beginner

Stacks & Queues

LIFO and FIFO with O(1) push and pop — a stack on a Go slice, the balanced-brackets classic, and the head-index trick that keeps a queue's dequeue cheap.

Linear Beginner ⏱ 3 min read Complete

🍽️ Analogy

A stack is a pile of plates: you add and take from the top, so the last plate on is the first off (LIFO). A queue is the line at a coffee shop: you join at the back and are served from the front, so first in is first out (FIFO). Same data, opposite discipline.

Two ends, two disciplines

graph LR
subgraph S["Stack · LIFO"]
  direction TB
  S3["3  ← top: push & pop"] --> S2["2"] --> S1["1  ← bottom"]
end
subgraph Q["Queue · FIFO"]
  direction LR
  F["front: dequeue"] --> Q1["1"] --> Q2["2"] --> Q3["3  ← rear: enqueue"]
end

A stack is just a slice

The end of a slice is the top. append pushes; reslicing off the last element pops — both O(1). The classic use is matching brackets:

▶ stack.go — editable & runnable
package main

import "fmt"

// balanced reports whether every bracket is correctly closed and nested.
func balanced(s string) bool {
closes := map[rune]rune{')': '(', ']': '[', '}': '{'}
var stack []rune
for _, c := range s {
	switch c {
	case '(', '[', '{':
		stack = append(stack, c) // push the opener
	case ')', ']', '}':
		// must match the most recent opener
		if len(stack) == 0 || stack[len(stack)-1] != closes[c] {
			return false
		}
		stack = stack[:len(stack)-1] // pop
	}
}
return len(stack) == 0 // nothing left unclosed
}

func main() {
for _, s := range []string{"({[]})", "(]", "((()))", "(()"} {
	fmt.Printf("%-8s -> %v\n", s, balanced(s))
}
}

A queue needs more care

The trap: Dequeue as q = q[1:] looks O(1), but the head drifts forward while the backing array — and everything before the head — is never reclaimed. Keep a head index and compact occasionally:

▶ queue.go — editable & runnable
package main

import "fmt"

// Queue is FIFO. A head index makes Dequeue O(1) amortized without
// leaking the front of the backing array.
type Queue[T any] struct {
buf  []T
head int
}

func (q *Queue[T]) Enqueue(v T) { q.buf = append(q.buf, v) }

func (q *Queue[T]) Dequeue() (T, bool) {
var zero T
if q.head >= len(q.buf) {
	return zero, false // empty
}
v := q.buf[q.head]
q.buf[q.head] = zero // drop the reference so the GC can collect it
q.head++
if q.head > 16 && q.head*2 > len(q.buf) {
	q.buf = append(q.buf[:0], q.buf[q.head:]...) // reclaim space
	q.head = 0
}
return v, true
}

func (q *Queue[T]) Len() int { return len(q.buf) - q.head }

func main() {
q := &Queue[string]{}
for _, s := range []string{"a", "b", "c"} {
	q.Enqueue(s)
}
for q.Len() > 0 {
	v, _ := q.Dequeue()
	fmt.Println("served:", v)
}
}

For a double-ended queue (push/pop at both ends) reach for container/list, or a ring buffer when the maximum size is known.

🐹 Channels are Go's concurrent queue

When producers and consumers run in different goroutines, you usually don’t build a queue at all — a buffered channel is a thread-safe FIFO with blocking and backpressure built in. See worker pool and pipeline.

See also

  • linked lists — the other backing for stacks/queues; container/list for a deque.
  • arrays & slices — why slice push/pop is amortized O(1).
  • graphs — BFS (queue) and DFS (stack) traversal in action.
  • worker pool — a buffered channel as a concurrent queue.

Next: keys instead of positions — hash tables.

linearArrays & Slices

A Go slice is a view over a backing array — how the (ptr, len, cap) header, append, growth, copy and re-slicing actually behave, and the aliasing traps.

linearLinked Lists

Nodes joined by pointers — O(1) insert/delete at a known position, O(n) access; singly vs doubly linked, the reversal classic, and when a slice is the better choice.

linearHash Tables

Average O(1) lookup via hashing — how Go's built-in map works, collisions and load factor, the comma-ok idiom, and the ordering and nil-map gotchas.

Check your understanding

Score: 0 / 5

1. A stack is LIFO. What does that mean?

A stack only touches one end: push and pop both act on the top, so the last thing in is the first thing out — like a stack of plates.

2. Why is repeatedly doing `q = q[1:]` to dequeue a problem?

Re-slicing moves the start forward but keeps the whole original array alive, and earlier elements are never freed. Track a head index (and occasionally compact) or use container/list.

3. How do you implement a stack on a Go slice?

The end of a slice is the natural top: append pushes (amortized O(1)) and reslicing off the last element pops (O(1)).

4. Which traversal uses a stack and which uses a queue?

Depth-first search dives down one path before backtracking — LIFO, a stack (recursion's call stack is exactly that). Breadth-first search visits level by level — FIFO, a queue. Swapping the structure swaps the traversal order. Stacks also power undo, expression evaluation, and bracket matching.

5. Across goroutines, why prefer a buffered channel over a hand-rolled queue?

When producers and consumers are separate goroutines, a buffered channel gives you a concurrent FIFO out of the box: sends block when full, receives block when empty (backpressure), all race-free. Build your own slice/list queue only for single-goroutine use.

Comments

Sign in with GitHub to join the discussion.