Stacks and queues are two of the simplest data structures, and two of the most useful. They show up everywhere: undo history, parsing, graph traversal, job processing, and more. In this post we'll build both from scratch in Go, use them to solve real problems, and look at the idiomatic Go alternatives.
The examples use generics, so you'll need Go 1.18 or newer.
The core idea
Both structures are collections where you can only add and remove items in a specific order.
| Stack | Queue | |
|---|---|---|
| Order | LIFO: Last In, First Out | FIFO: First In, First Out |
| Add | Push |
Enqueue |
| Remove | Pop |
Dequeue |
| Analogy | A stack of plates | A line at a coffee shop |
With a stack, the most recently added item comes out first. With a queue, the item that has waited longest comes out first.
Building a stack
Go doesn't ship a built-in stack type, but a slice is a perfect fit. Appending to the end and removing from the end are both cheap.
package main
import "fmt"
type Stack[T any] struct {
items []T
}
// Push adds an item to the top of the stack.
func (s *Stack[T]) Push(item T) {
s.items = append(s.items, item)
}
// Pop removes and returns the top item.
// The bool is false if the stack is empty.
func (s *Stack[T]) Pop() (T, bool) {
var zero T
if len(s.items) == 0 {
return zero, false
}
last := len(s.items) - 1
item := s.items[last]
s.items[last] = zero // let the garbage collector reclaim the value
s.items = s.items[:last]
return item, true
}
// Peek returns the top item without removing it.
func (s *Stack[T]) Peek() (T, bool) {
var zero T
if len(s.items) == 0 {
return zero, false
}
return s.items[len(s.items)-1], true
}
func (s *Stack[T]) Len() int { return len(s.items) }
func (s *Stack[T]) IsEmpty() bool { return len(s.items) == 0 }
func main() {
s := &Stack[int]{}
s.Push(1)
s.Push(2)
s.Push(3)
for !s.IsEmpty() {
v, _ := s.Pop()
fmt.Println(v) // 3, 2, 1
}
}
A few Go-specific choices worth noting:
-
Returning
(T, bool)follows the same "comma ok" pattern as map lookups. It avoids panics on an empty stack and avoids returning a misleading zero value without telling the caller. -
Zeroing the popped slot matters when
Tis a pointer or contains pointers. Without it, the underlying array keeps a reference and the garbage collector can't free the object. -
Pointer receivers are needed because
PushandPopmodify the struct.
Real example: balanced brackets
Checking that (, [, and { are properly matched is the classic stack problem. Every opener gets pushed, and every closer must match the most recent opener.
func isBalanced(s string) bool {
pairs := map[rune]rune{')': '(', ']': '[', '}': '{'}
stack := &Stack[rune]{}
for _, ch := range s {
switch ch {
case '(', '[', '{':
stack.Push(ch)
case ')', ']', '}':
top, ok := stack.Pop()
if !ok || top != pairs[ch] {
return false
}
}
}
return stack.IsEmpty()
}
func main() {
fmt.Println(isBalanced("{[()]}")) // true
fmt.Println(isBalanced("{[(])}")) // false
fmt.Println(isBalanced("((")) // false
}
Other places stacks show up: undo/redo, browser history, expression evaluation, depth-first search, and the call stack itself.
Building a queue
A queue needs to add at one end and remove from the other. The simplest version uses a slice again:
type Queue[T any] struct {
items []T
}
// Enqueue adds an item to the back of the queue.
func (q *Queue[T]) Enqueue(item T) {
q.items = append(q.items, item)
}
// Dequeue removes and returns the item at the front.
func (q *Queue[T]) Dequeue() (T, bool) {
var zero T
if len(q.items) == 0 {
return zero, false
}
item := q.items[0]
q.items[0] = zero
q.items = q.items[1:]
return item, true
}
func (q *Queue[T]) Len() int { return len(q.items) }
func (q *Queue[T]) IsEmpty() bool { return len(q.items) == 0 }
func main() {
q := &Queue[string]{}
q.Enqueue("a")
q.Enqueue("b")
q.Enqueue("c")
for !q.IsEmpty() {
v, _ := q.Dequeue()
fmt.Println(v) // a, b, c
}
}
This works well for small and medium workloads, but there's a catch. q.items[1:] doesn't free the front of the underlying array. Go reclaims that memory only when append eventually reallocates. For long-lived queues with heavy traffic, you may want something better.
A better queue: container/list
The standard library includes a doubly linked list, which gives true O(1) operations at both ends:
import "container/list"
type ListQueue[T any] struct {
l *list.List
}
func NewListQueue[T any]() *ListQueue[T] {
return &ListQueue[T]{l: list.New()}
}
func (q *ListQueue[T]) Enqueue(item T) {
q.l.PushBack(item)
}
func (q *ListQueue[T]) Dequeue() (T, bool) {
var zero T
front := q.l.Front()
if front == nil {
return zero, false
}
q.l.Remove(front)
return front.Value.(T), true
}
func (q *ListQueue[T]) Len() int { return q.l.Len() }
The trade-off is that container/list stores values as any, so you need a type assertion, and each node is a separate allocation. For most programs, either approach is fine. A ring buffer is the high-performance option if you ever need one.
Real example: breadth-first search
BFS explores a graph level by level, which is exactly what FIFO order gives you:
func bfs(graph map[string][]string, start string) []string {
visited := map[string]bool{start: true}
queue := &Queue[string]{}
queue.Enqueue(start)
var order []string
for !queue.IsEmpty() {
node, _ := queue.Dequeue()
order = append(order, node)
for _, next := range graph[node] {
if !visited[next] {
visited[next] = true
queue.Enqueue(next)
}
}
}
return order
}
func main() {
graph := map[string][]string{
"A": {"B", "C"},
"B": {"D"},
"C": {"D", "E"},
"D": {"F"},
"E": {"F"},
}
fmt.Println(bfs(graph, "A")) // [A B C D E F]
}
Swap the queue for a stack and you get depth-first search instead. The traversal logic stays the same; only the order of removal changes.
The idiomatic Go queue: channels
If you need a queue between goroutines, you probably don't want to build one at all. A buffered channel is already a thread-safe FIFO queue:
func main() {
jobs := make(chan int, 10) // capacity of 10
go func() {
for i := 1; i <= 5; i++ {
jobs <- i // enqueue
}
close(jobs)
}()
for job := range jobs { // dequeue
fmt.Println("processing job", job)
}
}
Our slice and list queues are not safe for concurrent use. If multiple goroutines touch them, you'd need a sync.Mutex. Channels give you ordering, blocking, and synchronization for free, which is why they're the go-to for producer/consumer patterns.
Time complexity
| Operation | Stack (slice) | Queue (slice) | Queue (container/list) |
|---|---|---|---|
| Push / Enqueue | O(1) amortized | O(1) amortized | O(1) |
| Pop / Dequeue | O(1) | O(1) | O(1) |
| Peek | O(1) | O(1) | O(1) |
"Amortized" means an occasional append has to grow the underlying array, but averaged over many operations the cost per call is constant.
Which one should you use?
- Need to reverse things, backtrack, or track nested structure? Use a stack.
- Need to process things in the order they arrived, or explore level by level? Use a queue.
- Passing work between goroutines? Use a buffered channel.
Wrapping up
Stacks and queues are small enough to implement in a few lines, yet they power some of the most important algorithms in computing. In Go, a slice gets you surprisingly far, generics keep the code reusable, and channels cover the concurrent case.
A good next step is to try implementing a ring-buffer queue, or a thread-safe stack using sync.Mutex. What data structure should I cover next? Let me know in the comments.
Top comments (0)