README
¶
deque: a high-performance slice-backed double-ended queue inspired by Rust's VecDeque
Compared to other popular slice-backed deque implementations, this one
- is only 32 bytes;
- uses append to get an optimial growth factor;
- supports iterating using Go 1.23 iterators;
- and steals Rust's clever strategy for minimizing the amount of data copied on reallocation.
Documentation
¶
Overview ¶
Package deque implements a double-ended queue (deque) implemented with a slice-backed ring buffer.
This queue has O(1) amortized inserts and removals from both ends of the container. It also has O(1) indexing like a vector.
The "default" usage of this type as a queue is to use Deque.PushBack to add to the queue, and Deque.PopFront to remove from the queue. Iterating over Deque goes front to back.
The core implementation is "ported" (stolen) from Rust's VecDeque.
Index ¶
- type Deque
- func (q *Deque[T]) All() iter.Seq2[int, T]
- func (q *Deque[T]) At(i int) T
- func (q *Deque[T]) Cap() int
- func (q *Deque[T]) Grow(n int)
- func (q *Deque[T]) Len() int
- func (q *Deque[T]) PopAll() iter.Seq[T]
- func (q *Deque[T]) PopBack() (T, bool)
- func (q *Deque[T]) PopFront() (T, bool)
- func (q *Deque[T]) PushBack(values ...T)
- func (q *Deque[T]) PushFront(values ...T)
- func (q *Deque[T]) Reset()
- func (q *Deque[T]) String() string
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Deque ¶
type Deque[T any] struct { // contains filtered or unexported fields }
Deque is a double-ended queue. The zero value is ready for use.
Example ¶
package main
import (
"fmt"
"roseh.moe/pkg/deque"
)
func main() {
q := new(deque.Deque[int])
for i := range 10 {
q.PushBack(i)
}
for range 3 {
q.PopFront()
}
fmt.Println(q)
}
Output: [3 4 5 6 7 8 9]
func From ¶
From creates a new queue using the given slice as the backing buffer.
Example ¶
package main
import (
"fmt"
"roseh.moe/pkg/deque"
)
func main() {
q := deque.From([]int{1, 2, 3, 4, 5})
fmt.Println(q.PopFront())
}
Output: 1 true
func WithCapacity ¶
WithCapacity allocates a deque with the given capacity.
Example ¶
package main
import (
"fmt"
"roseh.moe/pkg/deque"
)
func main() {
q := deque.WithCapacity[int](10)
for i := range 100 {
if q.Len() == q.Cap() {
q.PopFront()
}
q.PushBack(i)
}
fmt.Println(q)
}
Output: [90 91 92 93 94 95 96 97 98 99]
func (*Deque[T]) All ¶
All returns an iterator over the elements in the deque. It does not pop any elements.
Example ¶
package main
import (
"fmt"
"roseh.moe/pkg/deque"
)
func main() {
q := new(deque.Deque[int])
q.PushBack(1, 2, 3, 4, 5)
q.PopFront()
for _, x := range q.All() {
fmt.Println(x)
}
}
Output: 2 3 4 5
func (*Deque[T]) At ¶
At returns the item at position i. At panics if i < 0 or i >= q.Len().
Example ¶
package main
import (
"fmt"
"roseh.moe/pkg/deque"
)
func main() {
q := deque.From([]int{1, 2, 3, 4, 5})
fmt.Println(q.At(3))
}
Output: 4
func (*Deque[T]) Cap ¶
Cap returns the number of elements the deque can hold without reallocating.
Example ¶
package main
import (
"fmt"
"roseh.moe/pkg/deque"
)
func main() {
q := deque.WithCapacity[int](10)
q.PushBack(1, 2, 3, 4, 5)
fmt.Println(q.Cap())
}
Output: 10
func (*Deque[T]) Grow ¶
Grow makes space for at least n more elements to be inserted in the given deque without reallocation.
Example ¶
package main
import (
"roseh.moe/pkg/deque"
)
func main() {
q := new(deque.Deque[int])
q.Grow(5)
// PushBack will not allocate:
q.PushBack(1, 2, 3, 4, 5)
}
func (*Deque[T]) Len ¶
Len returns the number of elements in the deque.
Example ¶
package main
import (
"fmt"
"roseh.moe/pkg/deque"
)
func main() {
q := new(deque.Deque[int])
q.PushBack(1, 2, 3, 4, 5)
fmt.Println(q.Len())
}
Output: 5
func (*Deque[T]) PopAll ¶
PopAll empties the deque and returns an iterator over the popped elements. It's not safe to modify the deque while iterating using PopAll.
Example ¶
package main
import (
"fmt"
"roseh.moe/pkg/deque"
)
func main() {
q := deque.From([]int{1, 2, 3, 4, 5})
for x := range q.PopAll() {
fmt.Println(x)
}
fmt.Println(q)
}
Output: 1 2 3 4 5 []
func (*Deque[T]) PopBack ¶
PopBack removes and returns the last item in the deque if it is non-empty.
Example ¶
package main
import (
"fmt"
"roseh.moe/pkg/deque"
)
func main() {
q := deque.From([]int{1, 2, 3, 4, 5})
for range 3 {
q.PopBack()
}
fmt.Println(q)
}
Output: [1 2]
func (*Deque[T]) PopFront ¶
PopFront removes and returns the item at index 0 if the deque is non-empty.
Example ¶
package main
import (
"fmt"
"roseh.moe/pkg/deque"
)
func main() {
q := deque.From([]int{1, 2, 3, 4, 5})
for range 3 {
q.PopFront()
}
fmt.Println(q)
}
Output: [4 5]
func (*Deque[T]) PushBack ¶
func (q *Deque[T]) PushBack(values ...T)
PushBack appends the given items to the back of the deque.
Example ¶
package main
import (
"fmt"
"roseh.moe/pkg/deque"
)
func main() {
q := deque.From([]int{1, 2, 3, 4, 5})
q.PushBack(6, 7, 8, 9, 10)
fmt.Println(q)
}
Output: [1 2 3 4 5 6 7 8 9 10]
func (*Deque[T]) PushFront ¶
func (q *Deque[T]) PushFront(values ...T)
PushFront prepends the given items to the front of the deque.
Example ¶
package main
import (
"fmt"
"roseh.moe/pkg/deque"
)
func main() {
q := deque.From([]int{6, 7, 8, 9, 10})
q.PushFront(1, 2, 3, 4, 5)
fmt.Println(q)
}
Output: [1 2 3 4 5 6 7 8 9 10]
Source Files