slice_queue.go

package misc

// Queue is an implementation of the list data structure,
// it is a FIFO (first in, first out) data structure over a slice.
type Queue[T any] struct {
	l   []T
	idx int
}

// NewQueue returns a new Queue.
func NewQueue[T any](capacity int) *Queue[T] {
	return &Queue[T]{l: make([]T, 0, capacity)}
}

// Len returns the length of the queue.
func (q *Queue[T]) Len() int { return len(q.l) - q.idx }

// PushBack adds an element to the end of the queue.
func (q *Queue[T]) PushBack(e T) { q.l = append(q.l, e) }

// PopFront removes the first element from the queue and returns it.
func (q *Queue[T]) PopFront() T {
	if q.idx >= len(q.l) {
		panic("pop from empty queue")
	}
	e := q.l[q.idx]
	q.idx++

	// if the index is too far from the beginning of the slice
	// (more than half of the slice), then we need to copy the
	// remaining elements to the beginning of the slice and reset
	// the index, to avoid memory leaks.
	if q.idx > len(q.l)/2 {
		q.l = append([]T(nil), q.l[q.idx:]...)
		q.idx = 0
	}

	return e
}