Various Methods for Implementing Queues in Go

Implementing a queue in Go can be approached in various ways, depending on your specific requirements. Go's standard library does not include a built-in queue data structure, but you can create one using slices or linked lists. Here are some common implementations:

Simple Queue Using Slices

A simple queue can be implemented using slices. This approach works well for basic use cases.

package main

import (
    "fmt"
)

// Queue structure
type Queue struct {
    items []int
}

// Enqueue adds an item to the end of the queue
func (q *Queue) Enqueue(item int) {
    q.items = append(q.items, item)
}

// Dequeue removes an item from the front of the queue and returns it
func (q *Queue) Dequeue() (int, bool) {
    if len(q.items) == 0 {
        return 0, false
    }
    item := q.items[0]
    q.items = q.items[1:]
    return item, true
}

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

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

// Peek returns the item at the front of the queue without removing it
func (q *Queue) Peek() (int, bool) {
    if len(q.items) == 0 {
        return 0, false
    }
    return q.items[0], true
}

func main() {
    queue := Queue{}

    queue.Enqueue(1)
    queue.Enqueue(2)
    queue.Enqueue(3)

    fmt.Println("Queue size:", queue.Size()) // Output: Queue size: 3

    item, _ := queue.Peek()
    fmt.Println("Front item:", item) // Output: Front item: 1

    for !queue.IsEmpty() {
        item, _ := queue.Dequeue()
        fmt.Println("Dequeued item:", item) // Output: Dequeued item: 1, 2, 3
    }

    fmt.Println("Queue is empty:", queue.IsEmpty()) // Output: Queue is empty: true
}

Circular Queue Using a Fixed-Size Array

For a fixed-size queue, you can implement a circular queue (also known as a ring buffer).

package main

import "fmt"

// CircularQueue structure
type CircularQueue struct {
    items    []int
    head     int
    tail     int
    capacity int
    size     int
}

// NewCircularQueue creates a new circular queue
func NewCircularQueue(capacity int) *CircularQueue {
    return &CircularQueue{
        items:    make([]int, capacity),
        capacity: capacity,
        head:     -1,
        tail:     -1,
    }
}

// Enqueue adds an item to the end of the queue
func (cq *CircularQueue) Enqueue(item int) bool {
    if cq.size == cq.capacity {
        return false // Queue is full
    }

    if cq.size == 0 {
        cq.head = 0
    }

    cq.tail = (cq.tail + 1) % cq.capacity
    cq.items[cq.tail] = item
    cq.size++

    return true
}

// Dequeue removes an item from the front of the queue and returns it
func (cq *CircularQueue) Dequeue() (int, bool) {
    if cq.size == 0 {
        return 0, false // Queue is empty
    }

    item := cq.items[cq.head]
    if cq.head == cq.tail {
        cq.head = -1
        cq.tail = -1
    } else {
        cq.head = (cq.head + 1) % cq.capacity
    }
    cq.size--

    return item, true
}

// IsEmpty checks if the queue is empty
func (cq *CircularQueue) IsEmpty() bool {
    return cq.size == 0
}

// IsFull checks if the queue is full
func (cq *CircularQueue) IsFull() bool {
    return cq.size == cq.capacity
}

// Size returns the number of items in the queue
func (cq *CircularQueue) Size() int {
    return cq.size
}

func main() {
    queue := NewCircularQueue(3)

    queue.Enqueue(1)
    queue.Enqueue(2)
    queue.Enqueue(3)
    fmt.Println("Queue is full:", queue.IsFull()) // Output: Queue is full: true

    item, _ := queue.Dequeue()
    fmt.Println("Dequeued item:", item) // Output: Dequeued item: 1

    queue.Enqueue(4)
    fmt.Println("Queue is full:", queue.IsFull()) // Output: Queue is full: true

    for !queue.IsEmpty() {
        item, _ := queue.Dequeue()
        fmt.Println("Dequeued item:", item) // Output: Dequeued item: 2, 3, 4
    }

    fmt.Println("Queue is empty:", queue.IsEmpty()) // Output: Queue is empty: true
}

Queue Using Linked Lists

A queue implemented using a linked list can be more efficient for dynamic-sized queues.

package main

import "fmt"

// Node structure
type Node struct {
    value int
    next  *Node
}

// LinkedQueue structure
type LinkedQueue struct {
    head *Node
    tail *Node
    size int
}

// Enqueue adds an item to the end of the queue
func (q *LinkedQueue) Enqueue(value int) {
    newNode := &Node{value: value}
    if q.tail != nil {
        q.tail.next = newNode
    }
    q.tail = newNode
    if q.head == nil {
        q.head = newNode
    }
    q.size++
}

// Dequeue removes an item from the front of the queue and returns it
func (q *LinkedQueue) Dequeue() (int, bool) {
    if q.size == 0 {
        return 0, false
    }
    value := q.head.value
    q.head = q.head.next
    if q.head == nil {
        q.tail = nil
    }
    q.size--
    return value, true
}

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

// Size returns the number of items in the queue
func (q *LinkedQueue) Size() int {
    return q.size
}

func main() {
    queue := &LinkedQueue{}

    queue.Enqueue(1)
    queue.Enqueue(2)
    queue.Enqueue(3)

    fmt.Println("Queue size:", queue.Size()) // Output: Queue size: 3

    for !queue.IsEmpty() {
        item, _ := queue.Dequeue()
        fmt.Println("Dequeued item:", item) // Output: Dequeued item: 1, 2, 3
    }

    fmt.Println("Queue is empty:", queue.IsEmpty()) // Output: Queue is empty: true
}

Conclusion

A queue can be implemented in different ways in Go, each suited to various use cases. You can use slices for simplicity, a circular queue for fixed-size operations, or linked lists for more efficient dynamic sizing. Each approach has its own advantages and trade-offs, and you should choose one based on your specific needs and constraints.