queue.go

package gds

// Queue is a FIFO (first-in, first-out) collection.
// It is not safe for concurrent use.
type Queue[T any] struct {
	items []T
	head  int
}

// NewQueue returns an empty Queue.
func NewQueue[T any]() *Queue[T] { return &Queue[T]{} }

// Enqueue adds one or more items at the back of the queue.
func (q *Queue[T]) Enqueue(items ...T) {
	q.items = append(q.items, items...)
}

// Dequeue removes and returns the front element.
// Returns the zero value and false if the queue is empty.
func (q *Queue[T]) Dequeue() (T, bool) {
	if q.head >= len(q.items) {
		var zero T
		return zero, false
	}
	item := q.items[q.head]
	q.items[q.head] = *new(T) // release reference for GC
	q.head++
	// compact when at least half the backing slice is wasted
	if q.head > 0 && q.head >= len(q.items)/2 {
		q.items = append([]T{}, q.items[q.head:]...)
		q.head = 0
	}
	return item, true
}

// Peek returns the front element without removing it.
// Returns the zero value and false if the queue is empty.
func (q *Queue[T]) Peek() (T, bool) {
	if q.head >= len(q.items) {
		var zero T
		return zero, false
	}
	return q.items[q.head], true
}

// Len returns the number of elements waiting in the queue.
func (q *Queue[T]) Len() int { return len(q.items) - q.head }

// IsEmpty reports whether the queue has no elements.
func (q *Queue[T]) IsEmpty() bool { return q.Len() == 0 }

// Clear removes all elements from the queue.
func (q *Queue[T]) Clear() { q.items = nil; q.head = 0 }