README
¶
queue
The queue package provides thread-safe generic implementations in Go for the following data structures: BlockingQueue, PriorityQueue, CircularQueue and Linked Queue.
A queue is a sequence of entities that is open at both ends where the elements are added (enqueued) to the tail (back) of the queue and removed (dequeued) from the head (front) of the queue.
The implementations are designed to be easy-to-use and provide a consistent API, satisfying the Queue interface provided by this package. .
Benchmarks and Example tests can be found in this package.
Installation
To add this package as a dependency to your project, run:
go get -u github.com/adrianbrad/queue
Import
To use this package in your project, you can import it as follows:
import "github.com/adrianbrad/queue"
Usage
Queue Interface
// Queue is a generic queue interface, defining the methods that all queues must implement.
type Queue[T comparable] interface {
// Get retrieves and removes the head of the queue.
Get() (T, error)
// Offer inserts the element to the tail of the queue.
Offer(T) error
// Reset sets the queue to its initial state.
Reset()
// Contains returns true if the queue contains the element.
Contains(T) bool
// Peek retrieves but does not remove the head of the queue.
Peek() (T, error)
// Size returns the number of elements in the queue.
Size() int
// IsEmpty returns true if the queue is empty.
IsEmpty() bool
// Iterator returns a channel that will be filled with the elements
Iterator() <-chan T
// Clear removes all elements from the queue.
Clear() []T
}
Blocking Queue
Blocking queue is a FIFO ordered data structure. Both blocking and non-blocking methods are implemented. Blocking methods wait for the queue to have available items when dequeuing, and wait for a slot to become available in case the queue is full when enqueuing. The non-blocking methods return an error if an element cannot be added or removed. Implemented using sync.Cond from the standard library.
package main
import (
"fmt"
"github.com/adrianbrad/queue"
)
func main() {
elems := []int{2, 3}
blockingQueue := queue.NewBlocking(elems, queue.WithCapacity(3))
containsTwo := blockingQueue.Contains(2)
fmt.Println(containsTwo) // true
size := blockingQueue.Size()
fmt.Println(size) // 2
empty := blockingQueue.IsEmpty()
fmt.Println(empty) // false
if err := blockingQueue.Offer(1); err != nil {
// handle err
}
elem, err := blockingQueue.Get()
if err != nil {
// handle err
}
fmt.Println("elem: ", elem) // elem: 2
}
Priority Queue
Priority Queue is a data structure where the order of the elements is given by a comparator function provided at construction. Implemented using container/heap standard library package.
package main
import (
"fmt"
"github.com/adrianbrad/queue"
)
func main() {
elems := []int{2, 3, 4}
priorityQueue := queue.NewPriority(
elems,
func(elem, otherElem int) bool { return elem < otherElem },
)
containsTwo := priorityQueue.Contains(2)
fmt.Println(containsTwo) // true
size := priorityQueue.Size()
fmt.Println(size) // 3
empty := priorityQueue.IsEmpty()
fmt.Println(empty) // false
if err := priorityQueue.Offer(1); err != nil {
// handle err
}
elem, err := priorityQueue.Get()
if err != nil {
// handle err
}
fmt.Printf("elem: %d\n", elem) // elem: 1
}
Circular Queue
Circular Queue is a fixed size FIFO ordered data structure. When the queue is full, adding a new element to the queue overwrites the oldest element.
Example:
We have the following queue with a capacity of 3 elements: [1, 2, 3].
If the tail of the queue is set to 0, as if we just added the element 3,
the next element to be added to the queue will overwrite the element at index 0.
So, if we add the element 4, the queue will look like this: [4, 2, 3].
If the head of the queue is set to 0, as if we never removed an element yet,
then the next element to be removed from the queue will be the element at index 0, which is 4.
package main
import (
"fmt"
"github.com/adrianbrad/queue"
)
func main() {
elems := []int{2, 3, 4}
circularQueue := queue.NewCircular(elems, 3)
containsTwo := circularQueue.Contains(2)
fmt.Println(containsTwo) // true
size := circularQueue.Size()
fmt.Println(size) // 3
empty := circularQueue.IsEmpty()
fmt.Println(empty) // false
if err := circularQueue.Offer(1); err != nil {
// handle err
}
elem, err := circularQueue.Get()
if err != nil {
// handle err
}
fmt.Printf("elem: %d\n", elem) // elem: 1
}
Linked Queue
A linked queue, implemented as a singly linked list, offering O(1) time complexity for enqueue and dequeue operations. The queue maintains pointers to both the head (front) and tail (end) of the list for efficient operations without the need for traversal.
package main
import (
"fmt"
"github.com/adrianbrad/queue"
)
func main() {
elems := []int{2, 3, 4}
circularQueue := queue.NewLinked(elems)
containsTwo := circularQueue.Contains(2)
fmt.Println(containsTwo) // true
size := circularQueue.Size()
fmt.Println(size) // 3
empty := circularQueue.IsEmpty()
fmt.Println(empty) // false
if err := circularQueue.Offer(1); err != nil {
// handle err
}
elem, err := circularQueue.Get()
if err != nil {
// handle err
}
fmt.Printf("elem: %d\n", elem) // elem: 2
}
Benchmarks
Results as of October 2023.
BenchmarkBlockingQueue/Peek-8 84873882 13.98 ns/op 0 B/op 0 allocs/op
BenchmarkBlockingQueue/Get_Offer-8 27135865 47.00 ns/op 44 B/op 0 allocs/op
BenchmarkBlockingQueue/Offer-8 53750395 25.40 ns/op 43 B/op 0 allocs/op
BenchmarkCircularQueue/Peek-8 86001980 13.76 ns/op 0 B/op 0 allocs/op
BenchmarkCircularQueue/Get_Offer-8 32379159 36.83 ns/op 0 B/op 0 allocs/op
BenchmarkCircularQueue/Offer-8 63956366 18.77 ns/op 0 B/op 0 allocs/op
BenchmarkLinkedQueue/Peek-8 1000000000 0.4179 ns/op 0 B/op 0 allocs/op
BenchmarkLinkedQueue/Get_Offer-8 61257436 18.48 ns/op 16 B/op 1 allocs/op
BenchmarkLinkedQueue/Offer-8 38975062 30.74 ns/op 16 B/op 1 allocs/op
BenchmarkPriorityQueue/Peek-8 86633734 14.02 ns/op 0 B/op 0 allocs/op
BenchmarkPriorityQueue/Get_Offer-8 29347177 39.88 ns/op 0 B/op 0 allocs/op
BenchmarkPriorityQueue/Offer-8 40117958 31.37 ns/op 54 B/op 0 allocs/op
Documentation
¶
Overview ¶
Package queue provides multiple thread-safe generic queue implementations. Currently, there are 2 available implementations:
A blocking queue, which provides methods that wait for the queue to have available elements when attempting to retrieve an element, and waits for a free slot when attempting to insert an element.
A priority queue based on a container.Heap. The elements in the queue must implement the Lesser interface, and are ordered based on the Less method. The head of the queue is always the highest priority element.
A circular queue, which is a queue that uses a fixed-size slice as if it were connected end-to-end. When the queue is full, adding a new element to the queue overwrites the oldest element.
A linked queue, implemented as a singly linked list, offering O(1) time complexity for enqueue and dequeue operations. The queue maintains pointers to both the head (front) and tail (end) of the list for efficient operations without the need for traversal.
Index ¶
- Variables
- type Blocking
- func (bq *Blocking[T]) Clear() []T
- func (bq *Blocking[T]) Contains(elem T) bool
- func (bq *Blocking[T]) Get() (v T, _ error)
- func (bq *Blocking[T]) GetWait() (v T)
- func (bq *Blocking[T]) IsEmpty() bool
- func (bq *Blocking[T]) Iterator() <-chan T
- func (bq *Blocking[T]) Offer(elem T) error
- func (bq *Blocking[T]) OfferWait(elem T)
- func (bq *Blocking[T]) Peek() (v T, _ error)
- func (bq *Blocking[T]) PeekWait() T
- func (bq *Blocking[T]) Reset()
- func (bq *Blocking[T]) Size() int
- type Circular
- func (q *Circular[T]) Clear() []T
- func (q *Circular[T]) Contains(elem T) bool
- func (q *Circular[T]) Get() (v T, _ error)
- func (q *Circular[T]) IsEmpty() bool
- func (q *Circular[T]) Iterator() <-chan T
- func (q *Circular[T]) Offer(item T) error
- func (q *Circular[T]) Peek() (v T, _ error)
- func (q *Circular[T]) Reset()
- func (q *Circular[T]) Size() int
- type Linked
- func (lq *Linked[T]) Clear() []T
- func (lq *Linked[T]) Contains(value T) bool
- func (lq *Linked[T]) Get() (elem T, _ error)
- func (lq *Linked[T]) IsEmpty() bool
- func (lq *Linked[T]) Iterator() <-chan T
- func (lq *Linked[T]) Offer(value T) error
- func (lq *Linked[T]) Peek() (elem T, _ error)
- func (lq *Linked[T]) Reset()
- func (lq *Linked[T]) Size() int
- type Option
- type Priority
- func (pq *Priority[T]) Clear() []T
- func (pq *Priority[T]) Contains(a T) bool
- func (pq *Priority[T]) Get() (elem T, _ error)
- func (pq *Priority[T]) IsEmpty() bool
- func (pq *Priority[T]) Iterator() <-chan T
- func (pq *Priority[T]) Offer(elem T) error
- func (pq *Priority[T]) Peek() (elem T, _ error)
- func (pq *Priority[T]) Reset()
- func (pq *Priority[T]) Size() int
- type Queue
Examples ¶
Constants ¶
This section is empty.
Variables ¶
var ( // ErrNoElementsAvailable is an error returned whenever there are no // elements available to be extracted from a queue. ErrNoElementsAvailable = errors.New("no elements available in the queue") // ErrQueueIsFull is an error returned whenever the queue is full and there // is an attempt to add an element to it. ErrQueueIsFull = errors.New("queue is full") )
Functions ¶
This section is empty.
Types ¶
type Blocking ¶
type Blocking[T comparable] struct { // contains filtered or unexported fields }
Blocking is a Queue implementation that additionally supports operations that wait for the queue to have available items, and wait for a slot to become available in case the queue is full. ! The Blocking Queue shares most functionality with channels. If you do not make use of Peek, Reset and Contains methods you are safe to use channels instead.
It supports operations for retrieving and adding elements to a FIFO queue. If there are no elements available the retrieve operations wait until elements are added to the queue.
Example ¶
package main
import (
"fmt"
"time"
"github.com/adrianbrad/queue"
)
func main() {
elems := []int{1, 2, 3}
blockingQueue := queue.NewBlocking(elems, queue.WithCapacity(4))
containsThree := blockingQueue.Contains(3)
fmt.Println("Contains 3:", containsThree)
size := blockingQueue.Size()
fmt.Println("Size:", size)
empty := blockingQueue.IsEmpty()
fmt.Println("Empty before clear:", empty)
clearElems := blockingQueue.Clear()
fmt.Println("Clear:", clearElems)
empty = blockingQueue.IsEmpty()
fmt.Println("Empty after clear:", empty)
var (
elem int
after time.Duration
)
done := make(chan struct{})
start := time.Now()
// this function waits for a new element to be available in the queue.
go func() {
defer close(done)
elem = blockingQueue.GetWait()
after = time.Since(start)
}()
time.Sleep(time.Millisecond)
// insert a new element into the queue.
if err := blockingQueue.Offer(4); err != nil {
fmt.Println("Offer err:", err)
return
}
nextElem, err := blockingQueue.Peek()
if err != nil {
fmt.Println("Peek err:", err)
return
}
fmt.Println("Peeked elem:", nextElem)
<-done
fmt.Printf(
"Elem %d received after %s",
elem,
after.Round(time.Millisecond),
)
}
Output: Contains 3: true Size: 3 Empty before clear: false Clear: [1 2 3] Empty after clear: true Peeked elem: 4 Elem 4 received after 1ms
func NewBlocking ¶
func NewBlocking[T comparable]( elems []T, opts ...Option, ) *Blocking[T]
NewBlocking returns a new Blocking Queue containing the given elements.
func (*Blocking[T]) Clear ¶ added in v1.1.0
func (bq *Blocking[T]) Clear() []T
Clear removes and returns all elements from the queue.
func (*Blocking[T]) Contains ¶ added in v1.1.0
Contains returns true if the queue contains the given element.
func (*Blocking[T]) Get ¶ added in v0.6.0
Get removes and returns the head of the elements queue. If no element is available it returns an ErrNoElementsAvailable error.
It does not actually remove elements from the elements slice, but it's incrementing the underlying index.
func (*Blocking[T]) GetWait ¶ added in v0.8.0
func (bq *Blocking[T]) GetWait() (v T)
GetWait removes and returns the head of the elements queue. If no element is available it waits until the queue has an element available.
It does not actually remove elements from the elements slice, but it's incrementing the underlying index.
func (*Blocking[T]) Iterator ¶ added in v1.1.0
func (bq *Blocking[T]) Iterator() <-chan T
Iterator returns an iterator over the elements in this queue. Iterator returns an iterator over the elements in the queue. It removes the elements from the queue.
func (*Blocking[T]) Offer ¶ added in v0.7.0
Offer inserts the element to the tail the queue. If the queue is full it returns the ErrQueueIsFull error.
func (*Blocking[T]) OfferWait ¶ added in v0.8.0
func (bq *Blocking[T]) OfferWait(elem T)
OfferWait inserts the element to the tail the queue. It waits for necessary space to become available.
func (*Blocking[T]) Peek ¶ added in v0.3.0
Peek retrieves but does not return the head of the queue. If no element is available it returns an ErrNoElementsAvailable error.
func (*Blocking[T]) PeekWait ¶ added in v0.8.0
func (bq *Blocking[T]) PeekWait() T
PeekWait retrieves but does not return the head of the queue. If no element is available it waits until the queue has an element available.
type Circular ¶ added in v1.2.0
type Circular[T comparable] struct { // contains filtered or unexported fields }
Circular is a Queue implementation. A circular queue is a queue that uses a fixed-size slice as if it were connected end-to-end. When the queue is full, adding a new element to the queue overwrites the oldest element.
Example: We have the following queue with a capacity of 3 elements: [1, 2, 3]. If the tail of the queue is set to 0, as if we just added the element `3`, then the next element to be added to the queue will overwrite the element at index 0. So, if we add the element `4`, the queue will look like this: [4, 2, 3]. If the head of the queue is set to 0, as if we never removed an element yet, then the next element to be removed from the queue will be the element at index 0, which is `4`.
Example ¶
package main
import (
"fmt"
"github.com/adrianbrad/queue"
)
func main() {
elems := []int{1, 2, 3}
const capacity = 4
priorityQueue := queue.NewCircular(
elems,
capacity,
)
containsTwo := priorityQueue.Contains(2)
fmt.Println("Contains 2:", containsTwo)
size := priorityQueue.Size()
fmt.Println("Size:", size)
if err := priorityQueue.Offer(4); err != nil {
fmt.Println("Offer err: ", err)
return
}
nextElem, err := priorityQueue.Peek()
if err != nil {
fmt.Println("Peek err: ", err)
return
}
fmt.Println("Peek:", nextElem)
if err := priorityQueue.Offer(5); err != nil {
fmt.Println("Offer err: ", err)
return
}
fmt.Println("Offered 5")
if err := priorityQueue.Offer(6); err != nil {
fmt.Println("Offer err: ", err)
return
}
fmt.Println("Offered 6")
clearElems := priorityQueue.Clear()
fmt.Println("Clear:", clearElems)
fmt.Println("Offered 7")
if err := priorityQueue.Offer(7); err != nil {
fmt.Println("Offer err: ", err)
return
}
elem, err := priorityQueue.Get()
if err != nil {
fmt.Println("Get err: ", err)
return
}
fmt.Println("Get:", elem)
}
Output: Contains 2: true Size: 3 Peek: 1 Offered 5 Offered 6 Clear: [5 6 3 4] Offered 7 Get: 7
func NewCircular ¶ added in v1.2.0
func NewCircular[T comparable]( givenElems []T, capacity int, opts ...Option, ) *Circular[T]
NewCircular creates a new Circular Queue containing the given elements.
func (*Circular[T]) Clear ¶ added in v1.2.0
func (q *Circular[T]) Clear() []T
Clear removes all elements from the queue.
func (*Circular[T]) Contains ¶ added in v1.2.0
Contains returns true if the queue contains the given element.
func (*Circular[T]) Iterator ¶ added in v1.2.0
func (q *Circular[T]) Iterator() <-chan T
Iterator returns an iterator over the elements in the queue. It removes the elements from the queue.
func (*Circular[T]) Offer ¶ added in v1.2.0
Offer adds an element into the queue. If the queue is full then the oldest item is overwritten.
type Linked ¶ added in v1.3.0
type Linked[T comparable] struct { // contains filtered or unexported fields }
Linked represents a data structure representing a queue that uses a linked list for its internal storage.
Example ¶
package main
import (
"fmt"
"github.com/adrianbrad/queue"
)
func main() {
elems := []int{2, 4, 1}
priorityQueue := queue.NewLinked(
elems,
)
containsTwo := priorityQueue.Contains(2)
fmt.Println("Contains 2:", containsTwo)
size := priorityQueue.Size()
fmt.Println("Size:", size)
if err := priorityQueue.Offer(3); err != nil {
fmt.Println("Offer err: ", err)
return
}
empty := priorityQueue.IsEmpty()
fmt.Println("Empty before clear:", empty)
clearElems := priorityQueue.Clear()
fmt.Println("Clear:", clearElems)
empty = priorityQueue.IsEmpty()
fmt.Println("Empty after clear:", empty)
if err := priorityQueue.Offer(5); err != nil {
fmt.Println("Offer err: ", err)
return
}
elem, err := priorityQueue.Get()
if err != nil {
fmt.Println("Get err: ", err)
return
}
fmt.Println("Get:", elem)
}
Output: Contains 2: true Size: 3 Empty before clear: false Clear: [2 4 1 3] Empty after clear: true Get: 5
func NewLinked ¶ added in v1.3.0
func NewLinked[T comparable](elements []T) *Linked[T]
NewLinked creates a new Linked containing the given elements.
func (*Linked[T]) Clear ¶ added in v1.3.0
func (lq *Linked[T]) Clear() []T
Clear removes and returns all elements from the queue.
func (*Linked[T]) Contains ¶ added in v1.3.0
Contains returns true if the queue contains the element.
func (*Linked[T]) IsEmpty ¶ added in v1.3.0
IsEmpty returns true if the queue is empty, false otherwise.
func (*Linked[T]) Iterator ¶ added in v1.3.0
func (lq *Linked[T]) Iterator() <-chan T
Iterator returns a channel that will be filled with the elements. It removes the elements from the queue.
type Option ¶ added in v0.6.0
type Option interface {
// contains filtered or unexported methods
}
An Option configures a Queue using the functional options paradigm.
func WithCapacity ¶ added in v0.6.0
WithCapacity specifies a fixed capacity for a queue.
type Priority ¶ added in v0.8.0
type Priority[T comparable] struct { // contains filtered or unexported fields }
Priority is a Queue implementation.
The ordering is given by the lessFunc. The head of the queue is always the highest priority element.
! If capacity is provided and is less than the number of elements provided, the elements slice is sorted and trimmed to fit the capacity.
For ordered types (types that support the operators < <= >= >), the order can be defined by using the following operators: > - for ascending order < - for descending order.
Example ¶
package main
import (
"fmt"
"github.com/adrianbrad/queue"
)
func main() {
elems := []int{2, 4, 1}
priorityQueue := queue.NewPriority(
elems,
func(elem, otherElem int) bool {
return elem < otherElem
},
queue.WithCapacity(4),
)
containsTwo := priorityQueue.Contains(2)
fmt.Println("Contains 2:", containsTwo)
size := priorityQueue.Size()
fmt.Println("Size:", size)
if err := priorityQueue.Offer(3); err != nil {
fmt.Println("Offer err: ", err)
return
}
empty := priorityQueue.IsEmpty()
fmt.Println("Empty before clear:", empty)
clearElems := priorityQueue.Clear()
fmt.Println("Clear:", clearElems)
empty = priorityQueue.IsEmpty()
fmt.Println("Empty after clear:", empty)
if err := priorityQueue.Offer(5); err != nil {
fmt.Println("Offer err: ", err)
return
}
elem, err := priorityQueue.Get()
if err != nil {
fmt.Println("Get err: ", err)
return
}
fmt.Println("Get:", elem)
}
Output: Contains 2: true Size: 3 Empty before clear: false Clear: [1 2 3 4] Empty after clear: true Get: 5
func NewPriority ¶ added in v0.8.0
func NewPriority[T comparable]( elems []T, lessFunc func(elem, otherElem T) bool, opts ...Option, ) *Priority[T]
NewPriority creates a new Priority Queue containing the given elements. It panics if lessFunc is nil.
func (*Priority[T]) Clear ¶ added in v1.1.0
func (pq *Priority[T]) Clear() []T
Clear removes all elements from the queue.
func (*Priority[T]) Contains ¶ added in v1.1.0
Contains returns true if the queue contains the element, false otherwise.
func (*Priority[T]) Get ¶ added in v0.8.0
Get removes and returns the head of the queue. If no element is available it returns an ErrNoElementsAvailable error.
func (*Priority[T]) IsEmpty ¶ added in v1.1.0
IsEmpty returns true if the queue is empty, false otherwise.
func (*Priority[T]) Iterator ¶ added in v1.1.0
func (pq *Priority[T]) Iterator() <-chan T
Iterator returns an iterator over the elements in the queue. It removes the elements from the queue.
func (*Priority[T]) Offer ¶ added in v0.8.0
Offer inserts the element into the queue. If the queue is full it returns the ErrQueueIsFull error.
func (*Priority[T]) Peek ¶ added in v0.8.0
Peek retrieves but does not return the head of the queue.
type Queue ¶ added in v0.6.0
type Queue[T comparable] interface { // Get retrieves and removes the head of the queue. Get() (T, error) // Offer inserts the element to the tail of the queue. Offer(T) error // Reset sets the queue to its initial state. Reset() // Contains returns true if the queue contains the element. Contains(T) bool // Peek retrieves but does not remove the head of the queue. Peek() (T, error) // Size returns the number of elements in the queue. Size() int // IsEmpty returns true if the queue is empty. IsEmpty() bool // Iterator returns a channel that will be filled with the elements Iterator() <-chan T // Clear removes all elements from the queue. Clear() []T }
A Queue is an ordered sequence of items, the order is usually first in first out. New items are added to the back of the queue and existing items are removed from the front of the queue.
This interface provides basic methods for adding and extracting elements from the queue. Items are extracted from the head of the queue and added to the tail of the queue.
Source Files