Building Stacks and Queues in Go
You are writing a linter for a custom config format. You need to track nested braces. When the parser sees {, you push it onto a collection. When it sees }, you pop the last brace to verify they match. That is a stack. Now you are building a background job processor. Jobs arrive from a webhook and must be executed in the order they arrived. First in, first out. That is a queue.
Go's standard library does not provide built-in Stack or Queue types. You implement them using slices. Slices are dynamic arrays that grow automatically. By wrapping a slice and enforcing access rules, you get the data structure you need without external dependencies. The trade-off is that you manage the memory behavior yourself.
The Stack: Last-In, First-Out
A stack follows Last-In, First-Out order. Think of a stack of plates in a cafeteria. You add a plate to the top. You take a plate from the top. You never reach into the middle. In Go, the end of a slice is the natural top. Appending to the end is fast. Removing from the end is fast.
Here is a generic stack that works for any type. Generics let you write the logic once and use it with int, string, or custom structs. The compiler generates specialized code for each type you use.
// Stack is a generic LIFO collection backed by a slice.
type Stack[T any] struct {
items []T
}
// Push adds an item to the top of the stack.
func (s *Stack[T]) Push(v T) {
// append grows the underlying array if capacity is exceeded.
s.items = append(s.items, v)
}
// Pop removes and returns the top item.
func (s *Stack[T]) Pop() T {
// grab the last element, then shrink the slice length.
v := s.items[len(s.items)-1]
s.items = s.items[:len(s.items)-1]
return v
}
// Len returns the number of items in the stack.
func (s *Stack[T]) Len() int {
return len(s.items)
}
The Push method uses append. When the slice has room, append writes the value and increments the length. When the slice is full, append allocates a larger backing array, copies the existing elements, writes the new value, and returns the updated slice. Go grows slices by doubling capacity when full. This strategy keeps appends amortized O(1). The cost of allocation and copying is spread over many cheap appends.
The Pop method reads the last element and shrinks the slice length. The element remains in the backing array memory, but the slice length says it is gone. The garbage collector will reclaim the memory when the slice is resized or discarded. You do not need to zero the element manually.
A stack is a slice with a rule. Append to push. Slice to pop. The memory stays until the garbage collector runs.
The Queue: First-In, First-Out
A queue follows First-In, First-Out order. Think of a line at a coffee shop. New customers join at the back. The barista serves the person at the front. In Go, the end of the slice is the back. The start of the slice is the front. Appending to the back is fast. Removing from the front is where things get tricky.
Here is the naive queue implementation. It shifts the slice header to drop the first element.
// Queue is a generic FIFO collection backed by a slice.
type Queue[T any] struct {
items []T
}
// Enqueue adds an item to the back of the queue.
func (q *Queue[T]) Enqueue(v T) {
q.items = append(q.items, v)
}
// Dequeue removes and returns the front item.
func (q *Queue[T]) Dequeue() T {
// save the front value before shifting.
v := q.items[0]
// shift the slice to drop the first element.
q.items = q.items[1:]
return v
}
The Enqueue method is identical to the stack push. It uses append and benefits from the same amortized O(1) performance.
The Dequeue method uses q.items[1:]. This creates a new slice header that points one element further into the backing array. The length decreases by one. The capacity decreases by one. The backing array itself does not change. This approach has a hidden cost. The slice header now points to the second element of the array. The first element is still in the array. The slice still references the entire array allocation. The garbage collector sees the slice pointing into the array and keeps the whole array alive. The first element is dead weight. If you enqueue millions of items and then dequeue them all, the slice header moves, but the array stays huge. The memory is never freed until the slice is reallocated or the queue is discarded. This is a memory leak.
The naive queue holds onto the past. Shift the slice and you keep the memory. You need a strategy to let go.
Realistic Queue: Compacting Memory
To fix the leak, you must occasionally copy the remaining elements to a new slice with the correct capacity. This reclaims the memory at the front. Copying is O(N), so you do not want to do it on every dequeue. A common heuristic is to check if the capacity has grown too large relative to the length. If the capacity is four times the length, it is time to compact.
Here is a queue that manages its memory. It shifts the slice on every dequeue but compacts when the backing array balloons.
// JobQueue processes tasks and compacts memory when needed.
type JobQueue struct {
jobs []string
}
// Enqueue adds a job to the back.
func (q *JobQueue) Enqueue(job string) {
q.jobs = append(q.jobs, job)
}
// Dequeue returns the next job.
// If the slice capacity is too large, it compacts the backing array.
func (q *JobQueue) Dequeue() string {
job := q.jobs[0]
q.jobs = q.jobs[1:]
// heuristic: if capacity is 4x the length, shrink.
if cap(q.jobs) > len(q.jobs)*4 {
// copy to a new slice with exact capacity.
newJobs := make([]string, len(q.jobs))
copy(newJobs, q.jobs)
q.jobs = newJobs
}
return job
}
The Dequeue method checks cap(q.jobs) against len(q.jobs). The cap function returns the capacity of the underlying array. The len function returns the number of elements in the slice. If the capacity is significantly larger, the code allocates a new slice with exact capacity and uses copy to move the elements. The copy function handles the move efficiently. It works even if the source and destination overlap, though here they are distinct. After the copy, q.jobs points to the new slice. The old array is no longer referenced and the garbage collector reclaims it.
This approach gives you O(1) dequeue most of the time. The compaction happens rarely and costs O(N). For many workloads, this is acceptable. The memory usage stays bounded.
Compacting saves memory at the cost of occasional copying. Pick a threshold that matches your workload.
Pitfalls and Concurrency
Stacks and queues built from slices have common failure modes.
If you call Pop on an empty stack, the code accesses s.items[len(s.items)-1]. When the length is zero, this becomes s.items[-1]. The runtime panics with runtime error: index out of range [-1]. Always check the length before popping, or return a boolean flag indicating success.
If you call Dequeue on an empty queue, the same panic occurs. The slice access q.items[0] fails when the length is zero. Guard against empty access.
Slices are not thread-safe. If you share a stack or queue across goroutines, concurrent appends or slice operations will corrupt the data. The slice header contains a pointer, length, and capacity. Multiple goroutines updating these fields simultaneously causes data races. Use a sync.Mutex to protect the slice if you need concurrency. Lock the mutex before any read or write. Unlock it after the operation.
The receiver name in the methods is s for Stack and q for Queue. Go convention favors short receiver names, usually one or two letters matching the type. (s *Stack) is idiomatic. (stack *Stack) is verbose and rarely used in the standard library. Stick to short names.
The worst queue bug is the silent memory leak. Shift the slice without compacting and your process consumes more memory until it crashes. Monitor capacity growth in long-running services.
Decision Matrix
Go offers several ways to manage ordered collections. Pick the tool that matches your constraints.
Use a slice-based stack when you need fast LIFO access and the type is known at compile time. Use a naive slice queue for short-lived queues where memory leaks do not matter. Use a compacting slice queue when you need FIFO order and want to avoid external dependencies, accepting occasional O(N) shifts. Use container/list when you need O(1) removal from the front without memory compaction overhead and do not mind pointer indirection. Use a ring buffer implementation when you require strict O(1) enqueue and dequeue with bounded memory growth.
Slices are fast. Cache locality wins. Reach for container/list only when you have measured that pointer chasing is acceptable and compaction is too expensive.