chequeue

README

chequeue - Generic Queue Implementation

A production-ready, generic Queue (FIFO) implementation for Go with zero dependencies and near-100% test coverage.

Features

• ✅ Fully Generic - Works with any type
• ✅ Zero Dependencies - Pure Go standard library
• ✅ O(1) Amortized Performance - Constant time for Enqueue and Dequeue
• ✅ Automatic Resizing - Grows and shrinks as needed
• ✅ 100% Test Coverage - Comprehensive test suite
• ✅ Circular Buffer - Efficient memory usage

Installation

go get github.com/comfortablynumb/che/pkg/chequeue

Quick Start

package main

import (
    "fmt"
    "github.com/comfortablynumb/che/pkg/chequeue"
)

func main() {
    // Create a new queue
    queue := chequeue.New[int]()

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

    // Dequeue elements (FIFO order)
    value, ok := queue.Dequeue() // 1, true
    fmt.Println(value)

    // Peek at front without removing
    front, ok := queue.Peek() // 2, true

    // Check size
    fmt.Println(queue.Size()) // 2
}

Core Operations

Creating Queues

// Create empty queue
queue := chequeue.New[string]()

// Create with initial capacity
queue := chequeue.NewWithCapacity[string](100)

// Create from slice
queue := chequeue.NewFromSlice([]string{"a", "b", "c"})

Basic Operations

queue := chequeue.New[int]()

// Enqueue (add to back)
queue.Enqueue(1)
queue.Enqueue(2)

// Enqueue multiple elements
queue.EnqueueMultiple(3, 4, 5)

// Dequeue (remove from front)
value, ok := queue.Dequeue() // 1, true

// Peek at front element
front, ok := queue.Peek() // 2, true

// Check size
size := queue.Size() // 4

// Check if empty
empty := queue.IsEmpty() // false

// Clear all elements
queue.Clear()

Advanced Features

Iteration

queue := chequeue.NewFromSlice([]int{1, 2, 3, 4, 5})

// Iterate over all elements (FIFO order)
queue.ForEach(func(item int) bool {
    fmt.Println(item)
    return true // return false to stop iteration
})

Cloning

original := chequeue.NewFromSlice([]int{1, 2, 3})
clone := original.Clone()

// Modifications to clone don't affect original
clone.Enqueue(4)

Conversion

queue := chequeue.NewFromSlice([]int{1, 2, 3})

// Convert to slice (FIFO order)
slice := queue.ToSlice() // [1, 2, 3]

Contains (with custom equality)

queue := chequeue.NewFromSlice([]int{1, 2, 3})

equals := func(a, b int) bool { return a == b }
exists := queue.Contains(2, equals) // true

Use Cases

1. Task Queue

type Task struct {
    ID   int
    Name string
}

taskQueue := chequeue.New[Task]()

// Producer adds tasks
taskQueue.Enqueue(Task{ID: 1, Name: "Process data"})
taskQueue.Enqueue(Task{ID: 2, Name: "Send email"})

// Consumer processes tasks
for !taskQueue.IsEmpty() {
    task, _ := taskQueue.Dequeue()
    processTask(task)
}

2. BFS (Breadth-First Search)

type Node struct {
    Value int
    Children []*Node
}

func BFS(root *Node) {
    queue := chequeue.New[*Node]()
    queue.Enqueue(root)

    for !queue.IsEmpty() {
        node, _ := queue.Dequeue()
        fmt.Println(node.Value)

        for _, child := range node.Children {
            queue.Enqueue(child)
        }
    }
}

3. Request Buffer

type Request struct {
    ID      string
    Payload []byte
}

requestBuffer := chequeue.NewWithCapacity[Request](1000)

// Buffer incoming requests
func handleRequest(req Request) {
    requestBuffer.Enqueue(req)
}

// Process buffered requests
func processRequests() {
    for !requestBuffer.IsEmpty() {
        req, _ := requestBuffer.Dequeue()
        handleRequestLogic(req)
    }
}

4. Event Queue

type Event struct {
    Type      string
    Timestamp int64
    Data      interface{}
}

eventQueue := chequeue.New[Event]()

// Enqueue events as they occur
eventQueue.Enqueue(Event{Type: "click", Timestamp: time.Now().Unix()})

// Process events in order
for !eventQueue.IsEmpty() {
    event, _ := eventQueue.Dequeue()
    dispatchEvent(event)
}

5. Round-Robin Scheduler

type Worker struct {
    ID   int
    Load int
}

workers := chequeue.NewFromSlice([]Worker{
    {ID: 1, Load: 0},
    {ID: 2, Load: 0},
    {ID: 3, Load: 0},
})

func assignTask() Worker {
    // Get next worker
    worker, _ := workers.Dequeue()

    // Assign task to worker
    worker.Load++

    // Put worker back at end of queue
    workers.Enqueue(worker)

    return worker
}

Performance Characteristics

Operation	Time Complexity	Notes
Enqueue	O(1) amortized	May resize occasionally
Dequeue	O(1) amortized	May shrink occasionally
Peek	O(1)
Size	O(1)
IsEmpty	O(1)
Clear	O(1)
ToSlice	O(n)
Clone	O(n)
ForEach	O(n)
Contains	O(n)	Linear search

Space Complexity: O(n) where n is the number of elements

Memory Management

• Initial capacity: 8 elements
• Growth: Doubles when full
• Shrink: Halves when less than 25% full (minimum capacity: 8)
• Circular buffer implementation for efficient memory usage

Thread Safety

Queue is not thread-safe. For concurrent use, provide external synchronization:

import "sync"

var (
    queue = chequeue.New[int]()
    mu    sync.Mutex
)

// For writes
mu.Lock()
queue.Enqueue(1)
mu.Unlock()

// For reads
mu.Lock()
value, ok := queue.Dequeue()
mu.Unlock()

Comparison with Alternatives

vs. Slice

Queue advantages:

• ✅ O(1) dequeue (slice requires O(n) for removing first element)
• ✅ Automatic memory management
• ✅ Circular buffer efficiency
• ✅ Clear FIFO semantics

vs. container/list

Queue advantages:

• ✅ Better cache locality (contiguous memory)
• ✅ Simpler, more intuitive API
• ✅ Fully generic (not interface{})
• ✅ Better performance for typical use cases

vs. Channel

Queue advantages:

• ✅ Non-blocking operations
• ✅ Can inspect size without blocking
• ✅ Can peek without removing
• ✅ No goroutine required

Channel advantages:

• ✅ Thread-safe by default
• ✅ Blocking/buffered semantics
• ✅ Select statement support

FIFO Guarantee

Queue strictly maintains First-In-First-Out order:

queue := chequeue.New[int]()
queue.EnqueueMultiple(1, 2, 3, 4, 5)

// Elements come out in exact order they went in
val1, _ := queue.Dequeue() // 1
val2, _ := queue.Dequeue() // 2
val3, _ := queue.Dequeue() // 3
// ...

Contributing

Contributions are welcome! Please ensure:

• All tests pass
• Coverage remains high
• Code follows Go best practices

Related Packages

• chestack - Stack (LIFO) implementation
• cheset - Set implementations (HashSet, OrderedSet)
• cheslice - Slice utility functions

Documentation

Overview

Package chequeue provides a generic Queue implementation for Go.

Queue is a FIFO (First-In-First-Out) data structure that provides O(1) amortized performance for Enqueue and Dequeue operations.

Basic Usage

queue := chequeue.New[int]()
queue.Enqueue(1)
queue.Enqueue(2)
value, ok := queue.Dequeue() // 1, true
fmt.Println(queue.Size())    // 1

Thread Safety

Queue is not thread-safe. For concurrent use, external synchronization is required (e.g., using sync.Mutex).

Performance

Enqueue and Dequeue operations have O(1) amortized time complexity. The implementation uses a dynamic slice with automatic resizing.

Example

Example demonstrates basic Queue operations

package main

import (
	"fmt"

	"github.com/comfortablynumb/che/pkg/chequeue"
)

func main() {
	queue := chequeue.New[int]()

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

	// FIFO order
	val, _ := queue.Dequeue()
	fmt.Println("First out:", val)

	val, _ = queue.Dequeue()
	fmt.Println("Second out:", val)

	fmt.Println("Size:", queue.Size())

}

Output:
First out: 1
Second out: 2
Size: 1

Index

• type Queue
  • func New[T any]() *Queue[T]
  • func NewFromSlice[T any](slice []T) *Queue[T]
  • func NewWithCapacity[T any](capacity int) *Queue[T]
  • func (q *Queue[T]) Clear()
  • func (q *Queue[T]) Clone() *Queue[T]
  • func (q *Queue[T]) Contains(item T, equals func(a, b T) bool) bool
  • func (q *Queue[T]) Dequeue() (T, bool)
  • func (q *Queue[T]) Enqueue(item T)
  • func (q *Queue[T]) EnqueueMultiple(items ...T)
  • func (q *Queue[T]) ForEach(fn func(item T) bool)
  • func (q *Queue[T]) IsEmpty() bool
  • func (q *Queue[T]) Peek() (T, bool)
  • func (q *Queue[T]) Size() int
  • func (q *Queue[T]) String() string
  • func (q *Queue[T]) ToSlice() []T

Examples

• Package
• New
• NewFromSlice
• Queue (Bfs)
• Queue (TaskQueue)
• Queue.Clone
• Queue.Dequeue
• Queue.Enqueue
• Queue.ForEach
• Queue.Peek
• Queue.ToSlice

Types

type Queue

type Queue[T any] struct {
	// contains filtered or unexported fields
}

Queue is a generic FIFO (First-In-First-Out) queue implementation. It provides O(1) amortized time complexity for Enqueue and Dequeue operations. Queue is not thread-safe. For concurrent use, external synchronization is required.

Example (Bfs)

ExampleQueue_bfs demonstrates using Queue for breadth-first search

package main

import (
	"fmt"

	"github.com/comfortablynumb/che/pkg/chequeue"
)

func main() {
	type Node struct {
		Value    int
		Children []int
	}

	// Simple tree: 1 -> [2, 3], 2 -> [4, 5]
	nodes := map[int]Node{
		1: {Value: 1, Children: []int{2, 3}},
		2: {Value: 2, Children: []int{4, 5}},
		3: {Value: 3, Children: []int{}},
		4: {Value: 4, Children: []int{}},
		5: {Value: 5, Children: []int{}},
	}

	queue := chequeue.New[int]()
	queue.Enqueue(1) // Start with root

	for !queue.IsEmpty() {
		nodeID, _ := queue.Dequeue()
		node := nodes[nodeID]
		fmt.Println(node.Value)

		for _, childID := range node.Children {
			queue.Enqueue(childID)
		}
	}

}

Output:
1
2
3
4
5

Example (TaskQueue)

ExampleQueue_taskQueue demonstrates using Queue for task processing

package main

import (
	"fmt"

	"github.com/comfortablynumb/che/pkg/chequeue"
)

func main() {
	type Task struct {
		ID   int
		Name string
	}

	taskQueue := chequeue.New[Task]()

	// Add tasks
	taskQueue.Enqueue(Task{ID: 1, Name: "Process data"})
	taskQueue.Enqueue(Task{ID: 2, Name: "Send email"})
	taskQueue.Enqueue(Task{ID: 3, Name: "Update database"})

	// Process tasks in FIFO order
	for !taskQueue.IsEmpty() {
		task, _ := taskQueue.Dequeue()
		fmt.Printf("Processing task %d: %s\n", task.ID, task.Name)
	}

}

Output:
Processing task 1: Process data
Processing task 2: Send email
Processing task 3: Update database

func New

func New[T any]() *Queue[T]

New creates and returns a new empty Queue.

Example

ExampleNew demonstrates creating a new queue

package main

import (
	"fmt"

	"github.com/comfortablynumb/che/pkg/chequeue"
)

func main() {
	queue := chequeue.New[string]()
	queue.Enqueue("hello")
	queue.Enqueue("world")

	fmt.Println("Size:", queue.Size())

}

Output:
Size: 2

func NewFromSlice

func NewFromSlice[T any](slice []T) *Queue[T]

NewFromSlice creates and returns a new Queue containing all elements from the given slice. Elements are enqueued in the order they appear in the slice.

Example

ExampleNewFromSlice demonstrates creating a queue from a slice

package main

import (
	"fmt"

	"github.com/comfortablynumb/che/pkg/chequeue"
)

func main() {
	slice := []int{1, 2, 3, 4, 5}
	queue := chequeue.NewFromSlice(slice)

	// First element from slice is at front
	val, _ := queue.Dequeue()
	fmt.Println("First:", val)

}

Output:
First: 1

func NewWithCapacity

func NewWithCapacity[T any](capacity int) *Queue[T]

NewWithCapacity creates and returns a new empty Queue with the specified initial capacity. This can improve performance when the expected size is known in advance.

func (*Queue[T]) Clear

func (q *Queue[T]) Clear()

Clear removes all elements from the queue.

func (*Queue[T]) Clone

func (q *Queue[T]) Clone() *Queue[T]

Clone returns a shallow copy of the queue.

Example

ExampleQueue_Clone demonstrates cloning a queue

package main

import (
	"fmt"

	"github.com/comfortablynumb/che/pkg/chequeue"
)

func main() {
	original := chequeue.NewFromSlice([]int{1, 2, 3})
	clone := original.Clone()

	clone.Enqueue(4)

	fmt.Println("Original size:", original.Size())
	fmt.Println("Clone size:", clone.Size())

}

Output:
Original size: 3
Clone size: 4

func (*Queue[T]) Contains

func (q *Queue[T]) Contains(item T, equals func(a, b T) bool) bool

Contains checks if an element exists in the queue. This operation is O(n) as it requires scanning all elements.

func (*Queue[T]) Dequeue

func (q *Queue[T]) Dequeue() (T, bool)

Dequeue removes and returns the element at the front of the queue. Returns the element and true if successful, or zero value and false if the queue is empty.

Example

ExampleQueue_Dequeue demonstrates removing elements

package main

import (
	"fmt"

	"github.com/comfortablynumb/che/pkg/chequeue"
)

func main() {
	queue := chequeue.NewFromSlice([]int{1, 2, 3})

	val, ok := queue.Dequeue()
	fmt.Println("Value:", val, "Success:", ok)

	val, _ = queue.Dequeue()
	fmt.Println("Next:", val)

}

Output:
Value: 1 Success: true
Next: 2

func (*Queue[T]) Enqueue

func (q *Queue[T]) Enqueue(item T)

Enqueue adds an element to the back of the queue.

Example

ExampleQueue_Enqueue demonstrates adding elements

package main

import (
	"fmt"

	"github.com/comfortablynumb/che/pkg/chequeue"
)

func main() {
	queue := chequeue.New[int]()

	queue.Enqueue(10)
	queue.Enqueue(20)
	queue.Enqueue(30)

	fmt.Println("Size:", queue.Size())

}

Output:
Size: 3

func (*Queue[T]) EnqueueMultiple

func (q *Queue[T]) EnqueueMultiple(items ...T)

EnqueueMultiple adds multiple elements to the back of the queue.

func (*Queue[T]) ForEach

func (q *Queue[T]) ForEach(fn func(item T) bool)

ForEach executes a function for each element in the queue in FIFO order. If the function returns false, iteration stops.

Example

ExampleQueue_ForEach demonstrates iterating over elements

package main

import (
	"fmt"

	"github.com/comfortablynumb/che/pkg/chequeue"
)

func main() {
	queue := chequeue.NewFromSlice([]string{"a", "b", "c"})

	queue.ForEach(func(item string) bool {
		fmt.Println(item)
		return true
	})

}

Output:
a
b
c

func (*Queue[T]) IsEmpty

func (q *Queue[T]) IsEmpty() bool

IsEmpty returns true if the queue contains no elements.

func (*Queue[T]) Peek

func (q *Queue[T]) Peek() (T, bool)

Peek returns the element at the front of the queue without removing it. Returns the element and true if successful, or zero value and false if the queue is empty.

Example

ExampleQueue_Peek demonstrates peeking at the front

package main

import (
	"fmt"

	"github.com/comfortablynumb/che/pkg/chequeue"
)

func main() {
	queue := chequeue.NewFromSlice([]int{100, 200, 300})

	// Peek doesn't remove the element
	val, ok := queue.Peek()
	fmt.Println("Front:", val, "Success:", ok)
	fmt.Println("Size still:", queue.Size())

}

Output:
Front: 100 Success: true
Size still: 3

func (*Queue[T]) Size

func (q *Queue[T]) Size() int

Size returns the number of elements in the queue.

func (*Queue[T]) String

func (q *Queue[T]) String() string

String returns a string representation of the queue.

func (*Queue[T]) ToSlice

func (q *Queue[T]) ToSlice() []T

ToSlice returns a slice containing all elements in FIFO order.

Example

ExampleQueue_ToSlice demonstrates converting queue to slice

package main

import (
	"fmt"

	"github.com/comfortablynumb/che/pkg/chequeue"
)

func main() {
	queue := chequeue.NewFromSlice([]int{10, 20, 30})

	slice := queue.ToSlice()
	fmt.Println("Slice:", slice)

}

Output:
Slice: [10 20 30]