queue

package
v0.17.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Oct 14, 2026 License: MIT Imports: 3 Imported by: 0

README

package queue

A double-ended queue using a resizable ring buffer as its store

Data structure

  • Generalize queue and stack
  • Efficiently add and/or remove items at either end of the with O(1) performance
  • Support queue operations (FIFO) with enqueue add to the back and dequeue to remove from the front.
  • Support stack operations (LIFO) with push and pop. push and enqueue are the same action.
  • Optimize implementation for CPU and GC performance.
  • Resize the circular buffer automatically by powers of two
  • Grow when additional capacity is needed
  • Shrink when only a quarter of the capacity is used
  • Use bitwise arithmetic for all calculations. Since growth is by powers of two, adding elements will only cause O(log n) allocations.
  • Wrap around the buffer to reuse previously used space making allocation unnecessary until all buffer capacity is used.
  • Support concurrent use. Use the fastest sync primitives possible.
  • Use only stdlib in the construction of this package.
  • Require the user to specify the type upon creating the queue.
  • Use generics to make sure that all code is type safe.

General Build

  • Make sure that all code provide will build properly before sharing it
  • Include tests to make sure that all code paths in all functions are tested.

Documentation

Overview

Package queue provides a generic, thread-safe, dynamically resizing double-ended queue (deque). It offers efficient O(1) time complexity for adding and removing items from both ends, making it suitable for both queue (FIFO) and stack (LIFO) operations.

The queue automatically resizes its internal buffer by powers of two to optimize for CPU and garbage collection performance, growing when capacity is needed and shrinking when the buffer is less than a quarter full. It uses bitwise arithmetic for efficient index calculations and supports concurrent use through internal locking.

Index

Constants

This section is empty.

Variables

View Source 
var (
	// ErrEmptyQueue is returned when attempting to remove or peek from an empty queue.
	ErrEmptyQueue = errors.New("queue is empty")
	// ErrClosedQueue is returned when operating on a closed queue.
	ErrClosedQueue = errors.New("queue is closed")
	// ErrQueueFull is returned when attempting to Enqueue or AddFront on a queue
	// that has reached its maximum capacity.
	ErrQueueFull = errors.New("queue is full")
)

Functions

This section is empty.

Types

type Dequeuer 

type Dequeuer[T any] interface {
	// Dequeue removes and returns the item at the front.
	// Returns ErrEmptyQueue if empty, ErrClosedQueue if closed.
	Dequeue() (T, error)

	// Len returns the current number of items.
	Len() int

	// IsEmpty returns true if the queue has no items.
	IsEmpty() bool
}

Dequeuer abstracts read operations on a queue. Used by consumers that only need to pull items.

type Enqueuer 

type Enqueuer[T any] interface {
	// Enqueue adds an item to the back of the queue.
	// Returns ErrClosedQueue if closed.
	// Returns ErrQueueFull if the queue has reached its maximum capacity.
	Enqueue(item T) error

	// Len returns the current number of items.
	Len() int
}

Enqueuer abstracts write operations on a queue. Used by producers that only need to push items.

type Queue 

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

Queue is a generic, thread-safe, dynamically resizing double-ended queue (deque). Use NewQueue or NewBoundedQueue to create a queue. All methods are safe for concurrent use.

func NewBoundedQueue added in v0.9.0 

func NewBoundedQueue[T any](initialCap int, maxCap int) *Queue[T]

NewBoundedQueue creates a new queue with at least initialCap capacity and a maximum capacity of maxCap. Once the queue reaches maxCap items, Enqueue/AddBack and AddFront return ErrQueueFull. A maxCap of 0 (or less than initialCap) means the queue is unbounded.

func NewQueue 

func NewQueue[T any](initialCap int) *Queue[T]

NewQueue creates a new queue with at least initialCap capacity. The actual capacity will be the next power of two greater than or equal to initialCap. The queue is unbounded (no maximum capacity).

func (*Queue[T]) AddBack 

func (q *Queue[T]) AddBack(item T) error

AddBack adds an item to the back of the queue. Returns ErrClosedQueue if the queue is closed. Returns ErrQueueFull if the queue has reached its maximum capacity.

func (*Queue[T]) AddFront 

func (q *Queue[T]) AddFront(item T) error

AddFront adds an item to the front of the queue. Returns ErrClosedQueue if the queue is closed. Returns ErrQueueFull if the queue has reached its maximum capacity.

func (*Queue[T]) BroadcastWaiters added in v0.16.0 

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

BroadcastWaiters wakes all goroutines blocked in DequeueWait without enqueueing. Waiters that find the queue still empty return ErrEmptyQueue (see wakeEpoch).

func (*Queue[T]) Cap 

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

Cap returns the current capacity of the queue (internal buffer size).

func (*Queue[T]) Clear 

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

Clear removes all items from the queue and resets its capacity.

func (*Queue[T]) Close 

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

Close marks the queue as closed. Further operations will return ErrClosedQueue.

func (*Queue[T]) Dequeue 

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

Dequeue removes and returns the item at the front of the queue. Returns ErrEmptyQueue if the queue is empty, or ErrClosedQueue if closed.

func (*Queue[T]) DequeueWait added in v0.16.0 

func (q *Queue[T]) DequeueWait(ctx context.Context) (T, error)

DequeueWait removes and returns the front item, blocking while the queue is empty. It returns ctx.Err() if the context is canceled while waiting, or ErrClosedQueue if the queue is closed while empty. Non-blocking Dequeue behavior is unchanged.

func (*Queue[T]) Enqueue 

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

Enqueue adds an item to the back of the queue. Returns ErrClosedQueue if the queue is closed.

func (*Queue[T]) IsEmpty 

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

IsEmpty returns true if the queue is empty.

func (*Queue[T]) Len 

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

Len returns the number of items in the queue.

func (*Queue[T]) MaxCap added in v0.9.0 

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

MaxCap returns the maximum capacity of the queue. Returns 0 if the queue is unbounded.

func (*Queue[T]) PeekBack 

func (q *Queue[T]) PeekBack() (T, error)

PeekBack returns the item at the back of the queue without removing it. Returns ErrEmptyQueue if the queue is empty, or ErrClosedQueue if closed.

func (*Queue[T]) PeekFront 

func (q *Queue[T]) PeekFront() (T, error)

PeekFront returns the item at the front of the queue without removing it. Returns ErrEmptyQueue if the queue is empty, or ErrClosedQueue if closed.

func (*Queue[T]) Pop 

func (q *Queue[T]) Pop() (T, error)

Pop removes and returns the item at the back of the queue. Returns ErrEmptyQueue if the queue is empty, or ErrClosedQueue if closed.

func (*Queue[T]) Push 

func (q *Queue[T]) Push(item T) error

Push adds an item to the back of the queue. Returns ErrClosedQueue if the queue is closed.

func (*Queue[T]) RemoveBack 

func (q *Queue[T]) RemoveBack() (T, error)

RemoveBack removes and returns the item at the back of the queue. Returns ErrEmptyQueue if the queue is empty, or ErrClosedQueue if closed.

func (*Queue[T]) RemoveFront 

func (q *Queue[T]) RemoveFront() (T, error)

RemoveFront removes and returns the item at the front of the queue. Returns ErrEmptyQueue if the queue is empty, or ErrClosedQueue if closed.

func (*Queue[T]) Slice 

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

Slice returns a copy of the queue's contents as a slice.

func (*Queue[T]) Stats 

func (q *Queue[T]) Stats() QueueStats

Stats returns statistics about the queue.

type QueueStats 

type QueueStats struct {
	CtAddBack     int  // Total number of AddBack operations.
	CtAddFront    int  // Total number of AddFront operations.
	CtRemoveBack  int  // Total number of RemoveBack operations.
	CtRemoveFront int  // Total number of RemoveFront operations.
	Size          int  // Current number of items in the queue.
	Capacity      int  // Current capacity of the queue's internal buffer.
	MaxCapacity   int  // Maximum capacity (0 = unlimited).
	HeadIndex     int  // Current head index of the internal buffer.
	TailIndex     int  // Current tail index of the internal buffer.
	IsClosed      bool // Whether the queue is closed.
}

QueueStats holds various statistics about the queue's current state.

type Queuer 

type Queuer[T any] interface {
	Dequeuer[T]
	Enqueuer[T]
	Close()
}

Queuer combines read and write operations. Used when both operations are needed.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.