README
¶
deque
Fast ring-buffer deque (double-ended queue) implementation.
For a pictorial description, see the Deque diagram
Installation
$ go get github.com/gammazero/deque
Deque data structure
Deque generalizes a queue and a stack, to efficiently add and remove items at either end with O(1) performance. Queue (FIFO) operations are supported using PushBack() and PopFront(). Stack (LIFO) operations are supported using PushBack() and PopBack().
Ring-buffer Performance
This deque implementation is optimized for CPU and GC performance. The circular buffer automatically re-sizes by powers of two, growing when additional capacity is needed and shrinking when only a quarter of the capacity is used, and uses bitwise arithmetic for all calculations. Since growth is by powers of two, adding elements will only cause O(log n) allocations.
The ring-buffer implementation improves memory and time performance with fewer GC pauses, compared to implementations based on slices and linked lists. By wrapping around the buffer, previously used space is reused, making allocation unnecessary until all buffer capacity is used. This is particularly efficient when data going into the dequeue is relatively balanced against data coming out. However, if size changes are very large and only fill and then empty then deque, the ring structure offers little benefit for memory reuse. For that usage pattern a different implementation may be preferable.
For maximum speed, this deque implementation leaves concurrency safety up to the application to provide, however the application chooses, if needed at all.
Reading Empty Deque
Since it is OK for the deque to contain a nil value, it is necessary to either panic or return a second boolean value to indicate the deque is empty, when reading or removing an element. This deque panics when reading from an empty deque. This is a run-time check to help catch programming errors, which may be missed if a second return value is ignored. Simply check Deque.Len() before reading from the deque.
Example
package main
import (
"fmt"
"github.com/gammazero/deque"
)
func main() {
var q deque.Deque
q.PushBack("foo")
q.PushBack("bar")
q.PushBack("baz")
fmt.Println(q.Len()) // Prints: 3
fmt.Println(q.Front()) // Prints: foo
fmt.Println(q.Back()) // Prints: baz
q.PopFront() // remove "foo"
q.PopBack() // remove "baz"
q.PushFront("hello")
q.PushBack("world")
// Consume deque and print elements.
for q.Len() != 0 {
fmt.Println(q.PopFront())
}
}
Uses
Deque can be used as both a:
Documentation
¶
Overview ¶
Package deque provides a fast ring-buffer deque (double-ended queue) implementation.
Deque generalizes a queue and a stack, to efficiently add and remove items at either end with O(1) performance. Queue (FIFO) operations are supported using PushBack() and PopFront(). Stack (LIFO) operations are supported using PushBack() and PopBack().
Ring-buffer Performance ¶
The ring-buffer automatically resizes by powers of two, growing when additional capacity is needed and shrinking when only a quarter of the capacity is used, and uses bitwise arithmetic for all calculations.
The ring-buffer implementation significantly improves memory and time performance with fewer GC pauses, compared to implementations based on slices and linked lists.
For maximum speed, this deque implementation leaves concurrency safety up to the application to provide, however the application chooses, if needed at all.
Reading Empty Deque ¶
Since it is OK for the deque to contain a nil value, it is necessary to either panic or return a second boolean value to indicate the deque is empty, when reading or removing an element. This deque panics when reading from an empty deque. This is a run-time check to help catch programming errors, which may be missed if a second return value is ignored. Simply check Deque.Len() before reading from the deque.
Index ¶
- type Deque
- func (q *Deque) At(i int) interface{}
- func (q *Deque) Back() interface{}
- func (q *Deque) Clear()
- func (q *Deque) Front() interface{}
- func (q *Deque) Len() int
- func (q *Deque) PopBack() interface{}
- func (q *Deque) PopFront() interface{}
- func (q *Deque) PushBack(elem interface{})
- func (q *Deque) PushFront(elem interface{})
- func (q *Deque) Rotate(n int)
- func (q *Deque) Set(i int, elem interface{})
- func (q *Deque) SetMinCapacity(minCapacityExp uint)
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Deque ¶
type Deque struct {
// contains filtered or unexported fields
}
Deque represents a single instance of the deque data structure.
func (*Deque) At ¶
At returns the element at index i in the queue without removing the element from the queue. This method accepts only non-negative index values. At(0) refers to the first element and is the same as Front(). At(Len()-1) refers to the last element and is the same as Back(). If the index is invalid, the call panics.
The purpose of At is to allow Deque to serve as a more general purpose circular buffer, where items are only added to and removed from the ends of the deque, but may be read from any place within the deque. Consider the case of a fixed-size circular log buffer: A new entry is pushed onto one end and when full the oldest is popped from the other end. All the log entries in the buffer must be readable without altering the buffer contents.
func (*Deque) Back ¶
func (q *Deque) Back() interface{}
Back returns the element at the back of the queue. This is the element that would be returned by PopBack(). This call panics if the queue is empty.
func (*Deque) Clear ¶
func (q *Deque) Clear()
Clear removes all elements from the queue, but retains the current capacity. This is useful when repeatedly reusing the queue at high frequency to avoid GC during reuse. The queue will not be resized smaller as long as items are only added. Only when items are removed is the queue subject to getting resized smaller.
func (*Deque) Front ¶
func (q *Deque) Front() interface{}
Front returns the element at the front of the queue. This is the element that would be returned by PopFront(). This call panics if the queue is empty.
func (*Deque) PopBack ¶
func (q *Deque) PopBack() interface{}
PopBack removes and returns the element from the back of the queue. Implements LIFO when used with PushBack(). If the queue is empty, the call panics.
func (*Deque) PopFront ¶
func (q *Deque) PopFront() interface{}
PopFront removes and returns the element from the front of the queue. Implements FIFO when used with PushBack(). If the queue is empty, the call panics.
func (*Deque) PushBack ¶
func (q *Deque) PushBack(elem interface{})
PushBack appends an element to the back of the queue. Implements FIFO when elements are removed with PopFront(), and LIFO when elements are removed with PopBack().
func (*Deque) PushFront ¶
func (q *Deque) PushFront(elem interface{})
PushFront prepends an element to the front of the queue.
func (*Deque) Rotate ¶
Rotate rotates the deque n steps front-to-back. If n is negative, rotates back-to-front. Having Deque provide Rotate() avoids resizing that could happen if implementing rotation using only Pop and Push methods.
func (*Deque) Set ¶
Set puts the element at index i in the queue. Set shares the same purpose than At() but perform the opposite operation. The index i is the same index defined by At(). If the index is invalid, the call panics.
func (*Deque) SetMinCapacity ¶
SetMinCapacity sets a minimum capacity of 2^minCapacityExp. If the value of the minimum capacity is less than or equal to the minimum allowed, then capacity is set to the minimum allowed. This may be called at anytime to set a new minimum capacity.
Setting a larger minimum capacity may be used to prevent resizing when the number of stored items changes frequently across a wide range.
Source Files