Golang DSA Chapter 3 Part 2: Stacks, Queues, and Heaps
Welcome back. In the first half of Chapter 3, we covered linked lists, sets, and tuples. Now we’re finishing the chapter with queues, stacks, and heaps. These three come up constantly in real software, from job schedulers to undo buttons to sorting algorithms. Let’s get into it.
Queues
A queue is exactly what it sounds like: a line. First person in, first person out (FIFO). You add stuff to the back and remove from the front.
In real systems, queues show up everywhere. HTTP request handling, task scheduling, print job management, call center routing. Any time you need to process things in order, that’s a queue.
The book builds a priority queue example using orders. The idea is simple: orders have priorities, and higher priority orders get processed first. Here’s the type setup:
// Queue is an array of Order pointers
type Queue []*Order
// Order class
type Order struct {
priority int
quantity int
product string
customerName string
}
Each Order has a New method that sets its fields:
func (order *Order) New(priority int, quantity int, product string, customerName string) {
order.priority = priority
order.quantity = quantity
order.product = product
order.customerName = customerName
}
The interesting part is the Add method. It doesn’t just toss the order at the end. It walks through the queue and inserts the order based on priority:
func (queue *Queue) Add(order *Order) {
if len(*queue) == 0 {
*queue = append(*queue, order)
} else {
var appended bool
appended = false
var i int
var addedOrder *Order
for i, addedOrder = range *queue {
if order.priority > addedOrder.priority {
*queue = append((*queue)[:i], append(Queue{order}, (*queue)[i:]...)...)
appended = true
break
}
}
if !appended {
*queue = append(*queue, order)
}
}
}
What’s happening here: if the queue is empty, just add it. Otherwise, loop through existing orders and find the right spot based on priority. Higher priority number means it goes first. If no existing order has a lower priority, the new order goes at the end.
The main function creates two orders and adds them:
func main() {
var queue Queue
queue = make(Queue, 0)
var order1 *Order = &Order{}
order1.New(2, 20, "Computer", "Greg White")
var order2 *Order = &Order{}
order2.New(1, 10, "Monitor", "John Smith")
queue.Add(order1)
queue.Add(order2)
var i int
for i = 0; i < len(queue); i++ {
fmt.Println(queue[i])
}
}
The Computer order (priority 2) gets processed before the Monitor order (priority 1). That’s the whole point of a priority queue.
Complexity note: Adding to this priority queue is O(n) because you potentially walk the whole list to find the right insertion point. For small queues, this is fine. For large ones, you’d want a heap-based priority queue (more on heaps below).
Synchronized Queue
The book also shows a synchronized queue using Go channels. This is a more realistic example, simulating passengers waiting in line for tickets.
The queue struct uses channels for coordination:
type Queue struct {
waitPass int
waitTicket int
playPass bool
playTicket bool
queuePass chan int
queueTicket chan int
message chan int
}
Message types are defined as constants using iota:
const (
messagePassStart = iota
messageTicketStart
messagePassEnd
messageTicketEnd
)
The New method sets up the channels, and then a goroutine runs in the background listening for messages. When both a passenger and a ticket agent are ready, it pairs them up:
func (queue *Queue) New() {
queue.message = make(chan int)
queue.queuePass = make(chan int)
queue.queueTicket = make(chan int)
go func() {
var message int
for {
select {
case message = <-queue.message:
switch message {
case messagePassStart:
queue.waitPass++
case messagePassEnd:
queue.playPass = false
case messageTicketStart:
queue.waitTicket++
case messageTicketEnd:
queue.playTicket = false
}
if queue.waitPass > 0 && queue.waitTicket > 0 &&
!queue.playPass && !queue.playTicket {
queue.playPass = true
queue.playTicket = true
queue.waitTicket--
queue.waitPass--
queue.queuePass <- 1
queue.queueTicket <- 1
}
}
}
}()
}
The main method spawns 10 passenger goroutines and 5 ticket issuer goroutines, all running concurrently. Passengers randomly show up, wait for a ticket agent, get their ticket, and leave. The channels handle all the synchronization.
func main() {
var Queue *Queue = &Queue{}
Queue.New()
var i int
for i = 0; i < 10; i++ {
go passenger(Queue)
}
var j int
for j = 0; j < 5; j++ {
go ticketIssue(Queue)
}
select {}
}
That select {} at the end just blocks forever so the goroutines keep running. This is a nice pattern for demonstrating concurrent queue processing in Go.
Stacks
A stack is the opposite of a queue. Last in, first out (LIFO). Think of a stack of plates: you put one on top, and you take from the top.
Stacks show up in syntax parsing, undo/redo operations, backtracking algorithms, function call management (your program’s call stack is literally a stack), and maze solving.
The typical operations are Push (add to top), Pop (remove from top), Top (peek at top), and checking the size.
Here’s the book’s implementation. First, the element and stack types:
type Element struct {
elementValue int
}
func (element *Element) String() string {
return strconv.Itoa(element.elementValue)
}
type Stack struct {
elements []*Element
elementCount int
}
func (stack *Stack) New() {
stack.elements = make([]*Element, 0)
}
The Push method adds an element to the top and bumps the count:
func (stack *Stack) Push(element *Element) {
stack.elements = append(stack.elements[:stack.elementCount], element)
stack.elementCount = stack.elementCount + 1
}
The Pop method removes and returns the last element:
func (stack *Stack) Pop() *Element {
if stack.elementCount == 0 {
return nil
}
var length int = len(stack.elements)
var element *Element = stack.elements[length-1]
if length > 1 {
stack.elements = stack.elements[:length-1]
} else {
stack.elements = stack.elements[0:]
}
stack.elementCount = len(stack.elements)
return element
}
A few things to notice about Pop. It checks for an empty stack first and returns nil (good practice). Then it grabs the last element, shrinks the slice, updates the count, and returns what it found.
Here’s the full demo:
func main() {
var stack *Stack = &Stack{}
stack.New()
var element1 *Element = &Element{3}
var element2 *Element = &Element{5}
var element3 *Element = &Element{7}
var element4 *Element = &Element{9}
stack.Push(element1)
stack.Push(element2)
stack.Push(element3)
stack.Push(element4)
fmt.Println(stack.Pop(), stack.Pop(), stack.Pop(), stack.Pop())
}
Output: 9 7 5 3. See how the order is reversed? That’s LIFO in action. Last pushed (9) comes out first.
Complexity note: Both Push and Pop are O(1) operations. You’re always working with the end of the slice. That’s the beauty of stacks, very fast.
Heaps
The book introduces heaps earlier in the chapter as part of the broader linear data structures discussion. A heap is a partially ordered data structure based on the heap property: in a max heap, every parent node is greater than or equal to its children. In a min heap, it’s the opposite.
Heaps are used in selection algorithms, graph algorithms (like Dijkstra’s shortest path), k-way merges, and of course heap sort. The heap was originally proposed by J.W.J. Williams in 1964.
Go has heaps built into the standard library via the container/heap package. You just need to implement the heap.Interface, which requires Len, Less, Swap, Push, and Pop methods.
Here’s the book’s example of an integer min heap:
package main
import (
"container/heap"
"fmt"
)
type IntegerHeap []int
func (iheap IntegerHeap) Len() int { return len(iheap) }
func (iheap IntegerHeap) Less(i, j int) bool { return iheap[i] < iheap[j] }
func (iheap IntegerHeap) Swap(i, j int) { iheap[i], iheap[j] = iheap[j], iheap[i] }
func (iheap *IntegerHeap) Push(heapintf interface{}) {
*iheap = append(*iheap, heapintf.(int))
}
func (iheap *IntegerHeap) Pop() interface{} {
var n int
var x1 int
var previous IntegerHeap = *iheap
n = len(previous)
x1 = previous[n-1]
*iheap = previous[0 : n-1]
return x1
}
func main() {
var intHeap *IntegerHeap = &IntegerHeap{1, 4, 5}
heap.Init(intHeap)
heap.Push(intHeap, 2)
fmt.Printf("minimum: %d\n", (*intHeap)[0])
for intHeap.Len() > 0 {
fmt.Printf("%d \n", heap.Pop(intHeap))
}
}
The output prints minimum: 1, then pops all elements in sorted order: 1 2 4 5. That’s because Less uses <, making this a min heap. The smallest element is always at the root.
Complexity note: The key operations on a heap:
- Insert (Push): O(log n), because the element bubbles up to its correct position
- Remove min/max (Pop): O(log n), because the heap needs to re-balance
- Peek at min/max: O(1), it’s always at index 0
- Building a heap from scratch (Init): O(n)
This is why heaps are preferred over sorted arrays for priority queues. With a sorted array, insertion is O(n). With a heap, it’s O(log n). Big difference when you have thousands of elements.
Complexity Summary
| Data Structure | Push/Enqueue | Pop/Dequeue | Peek | Search |
|---|---|---|---|---|
| Stack | O(1) | O(1) | O(1) | O(n) |
| Queue (simple) | O(1) | O(1) | O(1) | O(n) |
| Priority Queue (array) | O(n) | O(1) | O(1) | O(n) |
| Heap | O(log n) | O(log n) | O(1) | O(n) |
Wrapping Up
That covers the second half of Chapter 3. Quick recap:
- Queues are FIFO. Great for task processing, request handling, anything that needs fair ordering. The book showed both a simple priority queue and a channel-based synchronized queue.
- Stacks are LIFO. Great for parsing, undo operations, backtracking. Push and Pop are both O(1).
- Heaps give you fast access to the min or max element. Go’s
container/heappackage makes them straightforward to use. They’re the backbone of efficient priority queues.
Next up, we’re moving into Chapter 4 where things get non-linear with trees and hash tables. That’s where data structures start getting really interesting.
This post is part of a series retelling “Learn Data Structures and Algorithms with Golang” by Bhagvan Kommadi (Packt, 2019, ISBN: 978-1-78961-850-1). The goal is to make the content easier to follow, not to replace the book.