Generic Data Structures in Go: Stack, Queue and Set
This tutorial builds three reusable generic containers: a Stack[T], a Queue[T], and a Set[T], plus an iterator, a concurrency-safe wrapper, and a priority queue on container/heap. It also explains when a container earns its keep and when a plain slice is clearer. Every example was run on Go 1.24.7.
Works with Go 1.23+ (the iterator section needs 1.23; everything else works on Go 1.21+). If generics are new to you, read the Go generics guide first, then come back. For the language basics, start with the complete Go tutorial.
A generic Stack with Push, Pop, Peek and Len
A stack is last-in, first-out. Browser history, undo buffers, and recursive-to-iterative rewrites all lean on one. Before generics you either wrote a []interface{} stack that lost type safety and boxed every value, or you copy-pasted the same code for intStack, stringStack, and so on. A single type parameter ends that.
The backing store is a slice, because a slice already does the hard part: append for push, reslice for pop.
// Stack is a last-in, first-out container of any element type.
type Stack[T any] struct {
items []T
}
// Push adds an element 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 element. The bool is false if the
// stack was empty, in which case the returned value is the zero value of T.
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 // release the reference so the GC can reclaim it
s.items = s.items[:last]
return item, true
}
// Peek returns the top element 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
}
// Len reports how many elements the stack holds.
func (s *Stack[T]) Len() int {
return len(s.items)
}Two details matter. First, Stack[T any] uses the any constraint because a stack never compares or orders its elements; it only stores and returns them. Second, s.items[last] = zero before reslicing matters when T holds pointers. Without it, the popped slot keeps a live reference and the garbage collector cannot reclaim what it points to.
Driving it, with the zero-value struct as a ready-to-use empty stack:
func main() {
var pages Stack[string]
pages.Push("home")
pages.Push("products")
pages.Push("checkout")
fmt.Println("depth:", pages.Len())
if top, ok := pages.Peek(); ok {
fmt.Println("current page:", top)
}
for {
page, ok := pages.Pop()
if !ok {
break
}
fmt.Println("back to:", page)
}
if _, ok := pages.Pop(); !ok {
fmt.Println("history is empty")
}
}depth: 3
current page: checkout
back to: checkout
back to: products
back to: home
history is emptyEmpty Pop: return an ok bool or an error
What should Pop do on an empty stack? Three options: panic, return a bool, or return an error. Panic is wrong for a library type, because an empty stack is a normal state, not a programmer bug. That leaves the bool and the error, and the choice is about the caller, not the container.
Use the (T, bool) form when reaching the bottom is expected, like the for { ... ok ... break } loop above. The comma-ok shape reads like a map lookup and every Go developer parses it instantly.
Use an error when an empty pop means something went wrong upstream that the caller must handle or report:
var errEmptyStack = errors.New("pop from empty stack")
// PopErr returns an error instead of a bool when an empty pop is a real
// failure the caller must handle, not an expected end-of-loop signal.
func (s *Stack[T]) PopErr() (T, error) {
var zero T
if len(s.items) == 0 {
return zero, errEmptyStack
}
last := len(s.items) - 1
item := s.items[last]
s.items[last] = zero
s.items = s.items[:last]
return item, nil
}func main() {
var undo Stack[string]
undo.Push("type hello")
action, err := undo.PopErr()
fmt.Println(action, err)
_, err = undo.PopErr()
if errors.Is(err, errEmptyStack) {
fmt.Println("nothing to undo")
}
}type hello <nil>
nothing to undoA sentinel error checked with errors.Is lets callers branch on the specific condition. For most in-process containers the bool is the right default: it is cheaper, and empty is not exceptional. Reach for the error only when the emptiness needs to travel up a call stack. More on that tradeoff in Go error handling.
A generic Queue and the reslice growth caveat
A queue is first-in, first-out. The obvious implementation appends to the back and reslices off the front. It works, and it has a memory trap that most tutorials never mention.
// SliceQueue is a FIFO queue backed by a slice. Dequeue reslices from the
// front, which never returns memory: the backing array stays as large as
// the queue ever got, and even one remaining element pins all of it.
type SliceQueue[T any] struct {
items []T
}
func (q *SliceQueue[T]) Enqueue(item T) {
q.items = append(q.items, item)
}
func (q *SliceQueue[T]) Dequeue() (T, bool) {
var zero T
if len(q.items) == 0 {
return zero, false
}
item := q.items[0]
q.items = q.items[1:] // front pointer moves right, the head is never reclaimed
return item, true
}q.items = q.items[1:] advances the slice header past the dequeued element. It does not shrink the backing array; it just stops looking at the front of it. The abandoned front stays allocated until the entire slice is dropped. Measure what that costs after a traffic spike:
func main() {
var q SliceQueue[int]
// A traffic spike: one million enqueues build a large backing array.
for i := 0; i < 1_000_000; i++ {
q.Enqueue(i)
}
fmt.Println("at peak -> len:", len(q.items), "cap:", cap(q.items))
// Drain almost everything, leaving a single element.
for i := 0; i < 999_999; i++ {
q.Dequeue()
}
fmt.Println("after drain -> len:", len(q.items), "cap:", cap(q.items))
}at peak -> len: 1000000 cap: 1055744
after drain -> len: 1 cap: 55745One live element, and the original backing array of 1,055,744 ints (about 8 MB) is still allocated. A single item at the tail pins the whole array, because a slice cannot free part of its backing memory. For a queue that only ever grows and drains once, this is fine. For a long-lived queue under steady traffic, it is a slow leak.
A ring buffer queue keeps capacity flat
The fix is a ring buffer: a fixed-size slice with a head index and a tail index that wrap around with modulo. Dequeued slots get reused instead of abandoned, so steady enqueue/dequeue traffic holds capacity flat.
// RingQueue is a FIFO queue backed by a ring buffer. It reuses slots, so
// steady enqueue/dequeue traffic keeps capacity flat instead of growing.
type RingQueue[T any] struct {
buf []T
head int // index of the next element to dequeue
tail int // index of the next free slot
count int
}
func NewRingQueue[T any](capacity int) *RingQueue[T] {
if capacity < 1 {
capacity = 1
}
return &RingQueue[T]{buf: make([]T, capacity)}
}
func (q *RingQueue[T]) Enqueue(item T) {
if q.count == len(q.buf) {
q.grow()
}
q.buf[q.tail] = item
q.tail = (q.tail + 1) % len(q.buf)
q.count++
}
func (q *RingQueue[T]) Dequeue() (T, bool) {
var zero T
if q.count == 0 {
return zero, false
}
item := q.buf[q.head]
q.buf[q.head] = zero
q.head = (q.head + 1) % len(q.buf)
q.count--
return item, true
}
func (q *RingQueue[T]) Len() int { return q.count }
// grow doubles the buffer and re-lays the elements from head to tail.
func (q *RingQueue[T]) grow() {
bigger := make([]T, len(q.buf)*2)
for i := 0; i < q.count; i++ {
bigger[i] = q.buf[(q.head+i)%len(q.buf)]
}
q.buf = bigger
q.head = 0
q.tail = q.count
}Run the same million cycles that bloated the slice queue:
func main() {
q := NewRingQueue[string](4)
q.Enqueue("a")
q.Enqueue("b")
q.Enqueue("c")
first, _ := q.Dequeue()
fmt.Println("served:", first, "remaining:", q.Len())
for i := 0; i < 1_000_000; i++ {
q.Enqueue(fmt.Sprintf("job-%d", i))
q.Dequeue()
}
fmt.Println("after 1M cycles, cap:", cap(q.buf))
}served: a remaining: 2
after 1M cycles, cap: 4Capacity stayed at 4 through a million cycles. The tradeoff: the ring buffer is more code, and it only grows, never shrinks, so a one-time spike still leaves the buffer large. Use the simple slice queue by default. Switch to a ring buffer only for a long-lived queue with sustained throughput where the slice version’s retention appears in a memory profile.
A generic Set backed by map[T]struct{}
Go has no built-in set, so people reach for map[T]bool. Prefer map[T]struct{}: an empty struct occupies zero bytes, so the map stores keys with no wasted value space, and there is no ambiguous “present but false” state. The type parameter is constrained to comparable, because map keys must be comparable with ==.
// Set is an unordered collection of unique comparable elements.
type Set[T comparable] struct {
m map[T]struct{}
}
func NewSet[T comparable](items ...T) *Set[T] {
s := &Set[T]{m: make(map[T]struct{}, len(items))}
for _, item := range items {
s.Add(item)
}
return s
}
func (s *Set[T]) Add(item T) { s.m[item] = struct{}{} }
func (s *Set[T]) Remove(item T) { delete(s.m, item) }
func (s *Set[T]) Contains(item T) bool { _, ok := s.m[item]; return ok }
func (s *Set[T]) Len() int { return len(s.m) }
// Union returns a new set with every element from both s and other.
func (s *Set[T]) Union(other *Set[T]) *Set[T] {
out := NewSet[T]()
for item := range s.m {
out.Add(item)
}
for item := range other.m {
out.Add(item)
}
return out
}
// Intersect returns a new set with only the elements present in both sets.
func (s *Set[T]) Intersect(other *Set[T]) *Set[T] {
out := NewSet[T]()
// Range the smaller set for fewer lookups.
small, large := s, other
if large.Len() < small.Len() {
small, large = large, small
}
for item := range small.m {
if large.Contains(item) {
out.Add(item)
}
}
return out
}Intersect ranges the smaller set and probes the larger one, which turns the cost into O(min(len)) map lookups instead of scanning the bigger set. A constructor with make(map[T]struct{}, len(items)) presizes the map so bulk construction avoids repeated rehashing.
func main() {
admins := NewSet("alice", "bob", "carol")
online := NewSet("bob", "carol", "dave")
fmt.Println("is alice admin:", admins.Contains("alice"))
onlineAdmins := admins.Intersect(online)
everyone := admins.Union(online)
// Sort only for stable printing; the set itself is unordered.
adminList := make([]string, 0, onlineAdmins.Len())
for name := range onlineAdmins.m {
adminList = append(adminList, name)
}
slices.Sort(adminList)
fmt.Println("online admins:", adminList)
fmt.Println("total people:", everyone.Len())
}is alice admin: true
online admins: [bob carol]
total people: 4A set is unordered, exactly like the underlying map, so sort a slice of the elements when you need stable output.
Non-comparable element types are a compile error
The comparable constraint is enforced at compile time, which is the whole point. Try to make a set of slices, which are not comparable, and the code will not build:
type Set[T comparable] struct {
m map[T]struct{}
}
func main() {
var routes Set[[]float64] // []float64 is not comparable
routes.Add([]float64{1, 2})
fmt.Println(routes)
}./main.go:14:17: []float64 does not satisfy comparableYou get this at build time, not as a runtime panic buried in production. Valid element types are the comparable ones: numbers, strings, booleans, pointers, channels, and structs or arrays whose fields are all comparable. Slices, maps, and functions are out. This is the same rule that governs map keys, explained further in constraints for generic code.
Making containers iterable with range-over-func
A useful container should be easy to iterate. Go 1.23 shipped range-over-function iterators, so you can return an iter.Seq[T] and let callers write for v := range s.All().
// All returns an iterator that yields elements from the top of the stack
// down to the bottom. It does not modify the stack.
func (s *Stack[T]) All() iter.Seq[T] {
return func(yield func(T) bool) {
for i := len(s.items) - 1; i >= 0; i-- {
if !yield(s.items[i]) {
return // consumer used break; stop producing
}
}
}
}An iter.Seq[T] is func(yield func(T) bool). Call yield once per element; when it returns false, the consumer has left the loop and iteration stops. The range keyword connects this behavior to the loop.
func main() {
var calls Stack[string]
calls.Push("main")
calls.Push("handleRequest")
calls.Push("queryDatabase")
for frame := range calls.All() {
fmt.Println(frame)
}
fmt.Println("--- break stops iteration early ---")
for frame := range calls.All() {
fmt.Println(frame)
if frame == "handleRequest" {
break
}
}
fmt.Println("stack still has", calls.Len(), "frames")
}main.go top-down output:
queryDatabase
handleRequest
main
--- break stops iteration early ---
queryDatabase
handleRequest
stack still has 3 framesbreak in the loop makes yield return false, the iterator returns, and iteration stops without draining the stack. Because All only reads, the stack still holds all three frames afterward. The official iterators docs cover iter.Seq2 for key-value pairs, which is what you would return from a Set or a map-like container.
A generic Pair and a linked list, briefly
Not every container needs one type parameter. A Pair needs two, one per field, which is the clearest case for multiple type parameters:
// Pair holds two values of independent types.
type Pair[K, V any] struct {
Key K
Value V
}A singly linked list is the textbook generic structure, and in Go it is mostly a teaching tool. Its main advantage is O(1) prepend:
type List[T any] struct {
head *node[T]
size int
}
type node[T any] struct {
value T
next *node[T]
}
func (l *List[T]) Prepend(value T) {
l.head = &node[T]{value: value, next: l.head}
l.size++
}events stored: 2
click (2)
login (1)In practice a slice beats a linked list almost everywhere in Go: contiguous memory means fewer cache misses, and slices.Insert handles the middle. Reach for a list only when you genuinely need stable node pointers or constant-time splicing.
These containers are not goroutine-safe
None of the types above are safe for concurrent use. Two goroutines calling Push at once race on the same slice, and go run -race will flag it. This is not a flaw to fix inside the container; keeping it single-threaded keeps it fast for the common single-goroutine case. When a container is shared, wrap it with a mutex:
// ConcurrentStack wraps a Stack with a mutex so multiple goroutines can
// share it safely. The lock is held for the whole operation.
type ConcurrentStack[T any] struct {
mu sync.Mutex
inner Stack[T]
}
func (s *ConcurrentStack[T]) Push(item T) {
s.mu.Lock()
defer s.mu.Unlock()
s.inner.Push(item)
}
func (s *ConcurrentStack[T]) Pop() (T, bool) {
s.mu.Lock()
defer s.mu.Unlock()
return s.inner.Pop()
}
func (s *ConcurrentStack[T]) Len() int {
s.mu.Lock()
defer s.mu.Unlock()
return s.inner.Len()
}func main() {
var stack ConcurrentStack[int]
var wg sync.WaitGroup
for worker := 0; worker < 100; worker++ {
wg.Add(1)
go func(n int) {
defer wg.Done()
stack.Push(n)
}(worker)
}
wg.Wait()
fmt.Println("pushed by 100 goroutines, len:", stack.Len())
}pushed by 100 goroutines, len: 100Composition, not inheritance: the wrapper embeds the plain Stack and guards each method. One caution, do not expose an iterator on a locked container without a plan, because holding the lock across a range loop that runs caller code invites deadlocks. For coordinating goroutines around a queue, a buffered channel is often the better primitive than a locked container; see the goroutines tutorial.
When to skip the container and use a slice or map directly
Most of the time, you do not need a container type at all. A slice is already a stack, and a map is already a set.
func main() {
// A plain slice is already a stack. No type needed.
var stack []int
stack = append(stack, 1, 2, 3) // push
top := stack[len(stack)-1] // peek
stack = stack[:len(stack)-1] // pop
fmt.Println("popped:", top, "remaining:", stack)
// A plain map[T]struct{} is already a set.
seen := map[string]struct{}{}
for _, id := range []string{"a", "b", "a", "c"} {
if _, dup := seen[id]; dup {
fmt.Println("duplicate:", id)
continue
}
seen[id] = struct{}{}
}
fmt.Println("unique count:", len(seen))
}popped: 3 remaining: [1 2]
duplicate: a
unique count: 3Wrap these in a type when you need named operations reused across a codebase (Union, Intersect), an invariant enforced in one place, a stable API you can swap the implementation behind (slice queue to ring buffer), or safe concurrent access. If you are writing three lines of push and pop in one function, the plain slice is clearer and has zero abstraction cost. Build the type when it pays for itself, not before.
A generic priority queue on container/heap
The standard library ships container/heap, but its API predates generics and is famously clunky: you implement five methods and cast any everywhere. Wrap it once in a generic type and callers get a clean, type-safe priority queue. This is the layer where generics genuinely earn their place, turning an awkward stdlib interface into something pleasant.
// PriorityQueue is a generic priority queue built on container/heap. The
// less function decides ordering, so the same type serves min- and max-heaps.
type PriorityQueue[T any] struct {
h *heapImpl[T]
}
func NewPriorityQueue[T any](less func(a, b T) bool) *PriorityQueue[T] {
return &PriorityQueue[T]{h: &heapImpl[T]{less: less}}
}
func (pq *PriorityQueue[T]) Push(item T) { heap.Push(pq.h, item) }
func (pq *PriorityQueue[T]) Len() int { return pq.h.Len() }
func (pq *PriorityQueue[T]) Pop() (T, bool) {
var zero T
if pq.h.Len() == 0 {
return zero, false
}
return heap.Pop(pq.h).(T), true
}
// heapImpl is the unexported adapter that satisfies heap.Interface. Callers
// never see it; they use the clean PriorityQueue methods above.
type heapImpl[T any] struct {
items []T
less func(a, b T) bool
}
func (h *heapImpl[T]) Len() int { return len(h.items) }
func (h *heapImpl[T]) Less(i, j int) bool { return h.less(h.items[i], h.items[j]) }
func (h *heapImpl[T]) Swap(i, j int) { h.items[i], h.items[j] = h.items[j], h.items[i] }
func (h *heapImpl[T]) Push(x any) { h.items = append(h.items, x.(T)) }
func (h *heapImpl[T]) Pop() any {
old := h.items
n := len(old)
item := old[n-1]
var zero T
old[n-1] = zero
h.items = old[:n-1]
return item
}The any casts and the five-method heap.Interface are quarantined inside the unexported heapImpl. Passing the less function to the constructor means one type covers both min-heaps and max-heaps: flip the comparison and you flip the order. A job scheduler serving lowest priority number first:
type Job struct {
Name string
Priority int // lower runs first
}
func main() {
queue := NewPriorityQueue(func(a, b Job) bool {
return a.Priority < b.Priority
})
queue.Push(Job{Name: "send-newsletter", Priority: 5})
queue.Push(Job{Name: "charge-card", Priority: 1})
queue.Push(Job{Name: "resize-avatar", Priority: 3})
queue.Push(Job{Name: "process-refund", Priority: 1})
for queue.Len() > 0 {
job, _ := queue.Pop()
fmt.Printf("running %-16s (priority %d)\n", job.Name, job.Priority)
}
}running charge-card (priority 1)
running process-refund (priority 1)
running resize-avatar (priority 3)
running send-newsletter (priority 5)The two priority-1 jobs both come out before priority 3. A heap is not a stable sort, so their relative order is not guaranteed; add a sequence number to the comparison if you need FIFO among equal priorities. This exact shape backs task schedulers, Dijkstra’s algorithm, and rate limiters in production Go.
Common mistakes
Popping an empty container without ok or error
The version that panics: subtract one from a zero length, index -1, and the program dies.
func (s *Stack[T]) BadPop() T {
last := len(s.items) - 1
item := s.items[last] // index -1 when empty: runtime panic
s.items = s.items[:last]
return item
}panic: runtime error: index out of range [-1]Always return (T, bool) or (T, error) and check the length first. A container that panics on a normal empty state is a landmine.
Assuming the slice queue frees memory
Covered above and worth repeating because it is the most expensive mistake here: q = q[1:] does not release the front of the backing array. A long-lived slice-backed queue holds its high-water-mark memory forever. Use a ring buffer, or periodically reallocate with slices.Clone when the queue drains.
Using map[T]bool for a set
map[T]bool wastes a byte per entry and creates a “present but false” state that invites bugs, since m[key] returns false both for absent keys and for keys explicitly set to false. Use map[T]struct{} and check presence with the comma-ok form.
Assuming a generic container is thread-safe
Nothing about generics adds synchronization. A shared Stack, Queue, or Set needs a mutex wrapper or a channel. Run your tests with go test -race to catch the data race before production does.
Building a container where a slice or map is clearer
The mirror image of under-engineering. A five-line function that pushes and pops does not need a Stack[T] type; the plain slice is more readable and has no indirection. Introduce the type when it carries meaningful operations, an invariant, or a shared API, not for its own sake.
What next
You have a tested toolkit: Stack, two queues, Set, Pair, a linked list, an iterator, a mutex wrapper, and a priority queue on container/heap. Where to go from here:
- The generics pillar covers the type system these containers rely on, from basic syntax to inference.
- Type parameters and constraints explain
anyversuscomparableand how to write your own constraints for ordered or numeric containers. - Go’s type system explains the value semantics and comparability rules used by these containers.
- For sharing containers across goroutines, Go mutexes and the goroutines tutorial show the synchronization these types deliberately leave out.
Bookmark the container/heap docs and the iter package; they are the two standard-library pieces that make generic containers first-class in modern Go.