Slices as Queues and Stacks in Go: Implementation Examples

In Go, slices are a versatile built-in data type that allows you to create and manage collections of elements effectively. They can be used for various data structures, such as queues and stacks, due to their dynamic nature. In this article, we'll explore how to implement slices as queues and stacks with several examples, ranging from basic to advanced implementations.

Basic Queue Implementation

A queue is a data structure that follows the First-In-First-Out (FIFO) principle. To create a queue using a slice, you'll typically use append to enqueue and slice operations to dequeue elements.

package main

import "fmt"

func main() {
    var queue []int

    // Enqueue
    queue = append(queue, 1)
    queue = append(queue, 2)
    queue = append(queue, 3)
    fmt.Println("Queue after adding elements:", queue)

    // Dequeue
    var firstElement int
    firstElement, queue = queue[0], queue[1:]
    fmt.Println("Dequeued element:", firstElement)
    fmt.Println("Queue after removing element:", queue)
}

Basic Stack Implementation

A stack is a Last-In-First-Out (LIFO) data structure. You can implement a stack by using slice append operations to push and slice length operations to pop elements.

package main

import "fmt"

func main() {
    var stack []int

    // Push onto stack
    stack = append(stack, 1)
    stack = append(stack, 2)
    stack = append(stack, 3)
    fmt.Println("Stack after pushing elements:", stack)

    // Pop from stack
    var lastElement int
    lastElement, stack = stack[len(stack)-1], stack[:len(stack)-1]
    fmt.Println("Popped element:", lastElement)
    fmt.Println("Stack after popping element:", stack)
}

Intermediate: Queue with a Struct

To encapsulate queue operations, you might design a struct that holds the slice and provide methods for adding and removing elements.

package main

import "fmt"

type Queue struct {
    elements []int
}

func (q *Queue) Enqueue(value int) {
    q.elements = append(q.elements, value)
}

func (q *Queue) Dequeue() (int, bool) {
    if len(q.elements) == 0 {
        return 0, false
    }
    firstElement := q.elements[0]
    q.elements = q.elements[1:]
    return firstElement, true
}

func main() {
    q := &Queue{}
    q.Enqueue(1)
    q.Enqueue(2)
    fmt.Println("Queue after enqueueing:", q.elements)
    value, _ := q.Dequeue()
    fmt.Println("Dequeued:", value)
}

Intermediate: Stack with a Struct

Similarly, a stack can be created using a struct and methods to ensure a more organized approach.

package main

import "fmt"

type Stack struct {
    elements []int
}

func (s *Stack) Push(value int) {
    s.elements = append(s.elements, value)
}

func (s *Stack) Pop() (int, bool) {
    if len(s.elements) == 0 { 
        return 0, false 
    }
    lastElement := s.elements[len(s.elements)-1]
    s.elements = s.elements[:len(s.elements)-1]
    return lastElement, true
}

func main() {
    s := &Stack{}
    s.Push(1)
    s.Push(2)
    fmt.Println("Stack after pushing:", s.elements)
    value, _ := s.Pop()
    fmt.Println("Popped:", value)
}

Advanced: Slices with Circular Queue

A circular queue uses a circular buffer approach for bounded queues for better performance and memory efficiency.

package main

import "fmt"

const Size = 5

type CircularQueue struct {
    elements          [Size]int
    head, tail, count int
}

func (cq *CircularQueue) Enqueue(value int) bool {
    if cq.count == Size {
        return false
    }
    cq.elements[cq.tail] = value
    cq.tail = (cq.tail + 1) % Size
    cq.count++
    return true
}

func (cq *CircularQueue) Dequeue() (int, bool) {
    if cq.count == 0 {
        return 0, false
    }
    value := cq.elements[cq.head]
    cq.head = (cq.head + 1) % Size
    cq.count--
    return value, true
}

func main() {
    cq := &CircularQueue{}
    cq.Enqueue(1)
    cq.Enqueue(2)
    cq.Enqueue(3)
    cq.Enqueue(4)
    fmt.Println("Attempt to enqueue another element (expected false):", cq.Enqueue(5))
    fmt.Println(cq.Dequeue())
}

Conclusion

Using slices as queues and stacks in Go is efficient and simple to implement for both basic applications and more complex use cases such as managing state with concurrent processes. Slices provide flexibility for these structures to grow and shrink as needed during runtime. Understanding and using these implementations help in exploiting native Go functionalities without the overhead of third-party libraries.