Go Data Structures & Algorithms

code

Stacks and Queues in Go

Table of Contents

Stacks and queues are fundamental linear data structures that manage collections of elements based on specific ordering principles. Stacks follow the Last-In, First-Out (LIFO) principle, while queues follow the First-In, First-Out (FIFO) principle. They are widely used in various algorithms and system designs. In this comprehensive guide, we will explore stacks and queues in Go, including their implementations, use cases, and performance characteristics.

What are Stacks and Queues?

Stacks and queues are abstract data types (ADTs) that define a set of operations on a collection of elements. They differ primarily in the order in which elements are added and removed.

Stacks (LIFO)

A stack operates on the Last-In, First-Out (LIFO) principle. The last element added to the stack is the first one to be removed. Think of a stack of plates: you add plates to the top and remove plates from the top.

The primary operations on a stack are:

  • Push: Add an element to the top of the stack.
  • Pop: Remove and return the element from the top of the stack.
  • Peek (or Top): Return the element at the top of the stack without removing it.
  • IsEmpty: Check if the stack is empty.
  • Size: Get the number of elements in the stack.

Queues (FIFO)

A queue operates on the First-In, First-Out (FIFO) principle. The first element added to the queue is the first one to be removed. Think of a queue of people waiting in line: the first person in line is the first one served.

The primary operations on a queue are:

  • Enqueue (or Offer): Add an element to the rear (end) of the queue.
  • Dequeue (or Poll): Remove and return the element from the front (head) of the queue.
  • Peek (or Front): Return the element at the front of the queue without removing it.
  • IsEmpty: Check if the queue is empty.
  • Size: Get the number of elements in the queue.

Stacks (LIFO)

Stacks are essential for managing function calls, parsing expressions, backtracking algorithms, and many other computational tasks.

Implementing a Stack

Stacks can be implemented using various underlying data structures, such as slices or linked lists.

Stack Implementation using Slices

Using a slice is often the simplest and most efficient way to implement a stack in Go, especially if the maximum size is roughly known.

package main

import (
    "fmt"
    "errors"
)

// SliceStack implements a stack using a slice
type SliceStack struct {
    elements []interface{}
}

// NewSliceStack creates a new empty stack
func NewSliceStack() *SliceStack {
    return &SliceStack{elements: make([]interface{}, 0)}
}

// Push adds an element to the top of the stack
func (s *SliceStack) Push(element interface{}) {
    s.elements = append(s.elements, element)
}

// Pop removes and returns the element from the top of the stack
func (s *SliceStack) Pop() (interface{}, error) {
    if s.IsEmpty() {
        return nil, errors.New("stack is empty")
    }
    
    index := len(s.elements) - 1
    element := s.elements[index]
    s.elements = s.elements[:index] // Remove the last element
    return element, nil
}

// Peek returns the element at the top of the stack without removing it
func (s *SliceStack) Peek() (interface{}, error) {
    if s.IsEmpty() {
        return nil, errors.New("stack is empty")
    }
    
    return s.elements[len(s.elements)-1], nil
}

// IsEmpty checks if the stack is empty
func (s *SliceStack) IsEmpty() bool {
    return len(s.elements) == 0
}

// Size returns the number of elements in the stack
func (s *SliceStack) Size() int {
    return len(s.elements)
}

// String returns a string representation of the stack
func (s *SliceStack) String() string {
    return fmt.Sprintf("%v", s.elements)
}

func main() {
    stack := NewSliceStack()
    
    stack.Push(1)
    stack.Push("hello")
    stack.Push(3.14)
    
    fmt.Println("Stack:", stack)
    fmt.Println("Size:", stack.Size())
    
    top, _ := stack.Peek()
    fmt.Println("Peek:", top)
    
    popped, _ := stack.Pop()
    fmt.Println("Popped:", popped)
    fmt.Println("Stack after pop:", stack)
    
    popped, _ = stack.Pop()
    fmt.Println("Popped:", popped)
    
    popped, _ = stack.Pop()
    fmt.Println("Popped:", popped)
    
    fmt.Println("Is empty:", stack.IsEmpty())
    
    _, err := stack.Pop() // Try to pop from empty stack
    if err != nil {
        fmt.Println("Error popping from empty stack:", err)
    }
}

Stack Implementation using Linked Lists

Using a linked list (specifically, a singly linked list) is another common way to implement a stack. This approach offers true O(1) time complexity for push and pop operations, without the potential reallocation overhead of slices.

package main

import (
    "fmt"
    "errors"
)

// Node represents a node in the linked list used for the stack
type Node struct {
    Data interface{}
    Next *Node
}

// LinkedListStack implements a stack using a singly linked list
type LinkedListStack struct {
    top  *Node
    size int
}

// NewLinkedListStack creates a new empty stack
func NewLinkedListStack() *LinkedListStack {
    return &LinkedListStack{}
}

// Push adds an element to the top of the stack
func (s *LinkedListStack) Push(element interface{}) {
    newNode := &Node{Data: element, Next: s.top}
    s.top = newNode
    s.size++
}

// Pop removes and returns the element from the top of the stack
func (s *LinkedListStack) Pop() (interface{}, error) {
    if s.IsEmpty() {
        return nil, errors.New("stack is empty")
    }
    
    element := s.top.Data
    s.top = s.top.Next
    s.size--
    return element, nil
}

// Peek returns the element at the top of the stack without removing it
func (s *LinkedListStack) Peek() (interface{}, error) {
    if s.IsEmpty() {
        return nil, errors.New("stack is empty")
    }
    
    return s.top.Data, nil
}

// IsEmpty checks if the stack is empty
func (s *LinkedListStack) IsEmpty() bool {
    return s.size == 0
}

// Size returns the number of elements in the stack
func (s *LinkedListStack) Size() int {
    return s.size
}

// String returns a string representation of the stack
func (s *LinkedListStack) String() string {
    elements := make([]interface{}, s.size)
    current := s.top
    for i := 0; i < s.size; i++ {
        elements[i] = current.Data
        current = current.Next
    }
    // Reverse for top-to-bottom representation
    for i, j := 0, len(elements)-1; i < j; i, j = i+1, j-1 {
        elements[i], elements[j] = elements[j], elements[i]
    }
    return fmt.Sprintf("%v", elements)
}

func main() {
    stack := NewLinkedListStack()
    
    stack.Push(1)
    stack.Push("hello")
    stack.Push(3.14)
    
    fmt.Println("Stack:", stack)
    fmt.Println("Size:", stack.Size())
    
    top, _ := stack.Peek()
    fmt.Println("Peek:", top)
    
    popped, _ := stack.Pop()
    fmt.Println("Popped:", popped)
    fmt.Println("Stack after pop:", stack)
    
    popped, _ = stack.Pop()
    fmt.Println("Popped:", popped)
    
    popped, _ = stack.Pop()
    fmt.Println("Popped:", popped)
    
    fmt.Println("Is empty:", stack.IsEmpty())
    
    _, err := stack.Pop() // Try to pop from empty stack
    if err != nil {
        fmt.Println("Error popping from empty stack:", err)
    }
}

Stack Use Cases

Stacks have numerous applications in computer science:

  • Function Call Management: The call stack manages active function calls, local variables, and return addresses.
  • Expression Evaluation: Converting infix expressions to postfix (Reverse Polish Notation) and evaluating postfix expressions.
  • Parsing: Used in syntax analysis (parsing) in compilers.
  • Backtracking Algorithms: Solving problems like maze solving, N-Queens, and Sudoku.
  • Undo/Redo Functionality: Storing states or commands to allow users to undo or redo actions.
  • Depth-First Search (DFS): Implementing DFS traversal in graphs and trees.
  • Browser History: Managing the back button functionality (though often a combination with other structures).

Queues (FIFO)

Queues are fundamental for managing tasks, resources, and events in the order they arrive.

Implementing a Queue

Queues can also be implemented using slices or linked lists.

Queue Implementation using Slices

Implementing a queue with a slice requires careful management of the underlying array to maintain FIFO order efficiently. Simple appending and slicing from the front can lead to O(n) complexity for dequeue operations due to memory copying.

package main

import (
    "fmt"
    "errors"
)

// SliceQueue implements a queue using a slice
type SliceQueue struct {
    elements []interface{}
}

// NewSliceQueue creates a new empty queue
func NewSliceQueue() *SliceQueue {
    return &SliceQueue{elements: make([]interface{}, 0)}
}

// Enqueue adds an element to the rear of the queue
func (q *SliceQueue) Enqueue(element interface{}) {
    q.elements = append(q.elements, element)
}

// Dequeue removes and returns the element from the front of the queue
func (q *SliceQueue) Dequeue() (interface{}, error) {
    if q.IsEmpty() {
        return nil, errors.New("queue is empty")
    }
    
    element := q.elements[0]
    q.elements = q.elements[1:] // This can be O(n) due to copying
    return element, nil
}

// Peek returns the element at the front of the queue without removing it
func (q *SliceQueue) Peek() (interface{}, error) {
    if q.IsEmpty() {
        return nil, errors.New("queue is empty")
    }
    
    return q.elements[0], nil
}

// IsEmpty checks if the queue is empty
func (q *SliceQueue) IsEmpty() bool {
    return len(q.elements) == 0
}

// Size returns the number of elements in the queue
func (q *SliceQueue) Size() int {
    return len(q.elements)
}

// String returns a string representation of the queue
func (q *SliceQueue) String() string {
    return fmt.Sprintf("%v", q.elements)
}

func main() {
    queue := NewSliceQueue()
    
    queue.Enqueue(1)
    queue.Enqueue("hello")
    queue.Enqueue(3.14)
    
    fmt.Println("Queue:", queue)
    fmt.Println("Size:", queue.Size())
    
    front, _ := queue.Peek()
    fmt.Println("Peek:", front)
    
    dequeued, _ := queue.Dequeue()
    fmt.Println("Dequeued:", dequeued)
    fmt.Println("Queue after dequeue:", queue)
    
    dequeued, _ = queue.Dequeue()
    fmt.Println("Dequeued:", dequeued)
    
    dequeued, _ = queue.Dequeue()
    fmt.Println("Dequeued:", dequeued)
    
    fmt.Println("Is empty:", queue.IsEmpty())
    
    _, err := queue.Dequeue() // Try to dequeue from empty queue
    if err != nil {
        fmt.Println("Error dequeuing from empty queue:", err)
    }
}

Note: The slice-based queue implementation shown above has an O(n) dequeue operation due to the slice re-allocation. For more efficient slice-based queues, consider using a circular buffer approach or accepting the amortized cost if dequeue operations are infrequent.

Queue Implementation using Linked Lists

Using a doubly linked list (or a singly linked list with both head and tail pointers) provides an efficient way to implement a queue with O(1) time complexity for both enqueue and dequeue operations.

package main

import (
    "fmt"
    "errors"
    "container/list" // Using Go's standard library doubly linked list
)

// LinkedListQueue implements a queue using container/list
type LinkedListQueue struct {
    elements *list.List
}

// NewLinkedListQueue creates a new empty queue
func NewLinkedListQueue() *LinkedListQueue {
    return &LinkedListQueue{elements: list.New()}
}

// Enqueue adds an element to the rear of the queue
func (q *LinkedListQueue) Enqueue(element interface{}) {
    q.elements.PushBack(element)
}

// Dequeue removes and returns the element from the front of the queue
func (q *LinkedListQueue) Dequeue() (interface{}, error) {
    if q.IsEmpty() {
        return nil, errors.New("queue is empty")
    }
    
    element := q.elements.Front()
    q.elements.Remove(element)
    return element.Value, nil
}

// Peek returns the element at the front of the queue without removing it
func (q *LinkedListQueue) Peek() (interface{}, error) {
    if q.IsEmpty() {
        return nil, errors.New("queue is empty")
    }
    
    return q.elements.Front().Value, nil
}

// IsEmpty checks if the queue is empty
func (q *LinkedListQueue) IsEmpty() bool {
    return q.elements.Len() == 0
}

// Size returns the number of elements in the queue
func (q *LinkedListQueue) Size() int {
    return q.elements.Len()
}

// String returns a string representation of the queue
func (q *LinkedListQueue) String() string {
    values := make([]interface{}, 0, q.Size())
    for e := q.elements.Front(); e != nil; e = e.Next() {
        values = append(values, e.Value)
    }
    return fmt.Sprintf("%v", values)
}

func main() {
    queue := NewLinkedListQueue()
    
    queue.Enqueue(1)
    queue.Enqueue("hello")
    queue.Enqueue(3.14)
    
    fmt.Println("Queue:", queue)
    fmt.Println("Size:", queue.Size())
    
    front, _ := queue.Peek()
    fmt.Println("Peek:", front)
    
    dequeued, _ := queue.Dequeue()
    fmt.Println("Dequeued:", dequeued)
    fmt.Println("Queue after dequeue:", queue)
    
    dequeued, _ = queue.Dequeue()
    fmt.Println("Dequeued:", dequeued)
    
    dequeued, _ = queue.Dequeue()
    fmt.Println("Dequeued:", dequeued)
    
    fmt.Println("Is empty:", queue.IsEmpty())
    
    _, err := queue.Dequeue() // Try to dequeue from empty queue
    if err != nil {
        fmt.Println("Error dequeuing from empty queue:", err)
    }
}

This implementation leverages Go's built-in container/list package, which provides a ready-to-use doubly linked list, ensuring O(1) enqueue and dequeue operations.

Queue Use Cases

Queues are fundamental in many areas of computer science:

  • Task Scheduling: Managing tasks to be executed by worker threads or processes (e.g., print queues, job queues).
  • Resource Management: Allocating shared resources (e.g., CPU scheduling, network packet handling).
  • Breadth-First Search (BFS): Implementing BFS traversal in graphs and trees.
  • Buffering: Temporarily storing data between processes or components that operate at different speeds (e.g., I/O buffers).
  • Message Queues: Used in distributed systems for asynchronous communication between services.
  • Simulations: Modeling real-world waiting lines.
  • Level Order Traversal: Traversing a tree level by level.

Performance Analysis

Let's analyze the time complexity of stack and queue operations based on their implementations.

Stack Performance

Operation Slice Implementation Linked List Implementation
Push O(1) amortized O(1)
Pop O(1) amortized O(1)
Peek O(1) O(1)
Size O(1) O(1)
IsEmpty O(1) O(1)

Slice implementation has amortized O(1) complexity because appending might trigger a reallocation (O(n)), but this happens infrequently.

Queue Performance

Operation Simple Slice Implementation Linked List Implementation (container/list)
Enqueue O(1) amortized O(1)
Dequeue O(n) O(1)
Peek O(1) O(1)
Size O(1) O(1)
IsEmpty O(1) O(1)

For queues, the linked list implementation (especially using container/list) offers better performance guarantees (O(1) for both enqueue and dequeue) compared to the simple slice implementation.

Best Practices

Here are some best practices for using stacks and queues in Go:

Choose the Right Implementation

  • For stacks, slices are often simpler and perform well due to cache locality, unless you need strict O(1) guarantees for very large stacks.
  • For queues, linked lists (like container/list) are generally preferred for guaranteed O(1) enqueue and dequeue operations. If using slices, consider a circular buffer implementation for efficiency.

Handle Empty Conditions

Always check if the stack or queue is empty before performing Pop, Peek, or Dequeue operations to avoid errors or panics.

Consider Thread Safety

The implementations shown are not thread-safe. If you need concurrent access, use mutexes or channels to synchronize operations, or consider using specialized concurrent data structures.

Use Standard Library When Possible

Leverage Go's standard library, such as container/list for linked-list-based queues, when appropriate. It's well-tested and optimized.

Define Clear Interfaces

If you implement your own stacks or queues, define clear interfaces to abstract the underlying implementation details.

type Stacker interface {
    Push(element interface{})
    Pop() (interface{}, error)
    Peek() (interface{}, error)
    IsEmpty() bool
    Size() int
}

type Queuer interface {
    Enqueue(element interface{})
    Dequeue() (interface{}, error)
    Peek() (interface{}, error)
    IsEmpty() bool
    Size() int
}

Conclusion

Stacks (LIFO) and queues (FIFO) are essential data structures for managing ordered collections of elements. Understanding their principles, implementations, and performance characteristics allows you to choose the right structure for various programming tasks, from managing function calls and evaluating expressions to scheduling tasks and implementing graph traversals. Go provides flexible options for implementing stacks and queues using slices or linked lists, enabling efficient solutions for a wide range of problems.

In the next section, we will delve into trees, hierarchical data structures used for representing relationships and enabling efficient searching and sorting.