deque

README

Please use the generic version, if you have golang 1.18 or above.

Overview

Deque is a highly optimized double-ended queue, which is much efficient compared with list.List when adding or removing elements from the beginning or the end.

Benchmark

PushBack/Deque<harden>       100000000       12.0 ns/op       8 B/op      0 allocs/op
PushBack/Deque                20000000       55.5 ns/op      24 B/op      1 allocs/op
PushBack/list.List             5000000      158.7 ns/op      56 B/op      1 allocs/op

PushFront/Deque<harden>      195840157        9.2 ns/op       8 B/op      0 allocs/op
PushFront/Deque               30000000       49.2 ns/op      24 B/op      1 allocs/op
PushFront/list.List            5000000      159.2 ns/op      56 B/op      1 allocs/op

Random/Deque<harden>          65623633       15.1 ns/op       0 B/op      0 allocs/op
Random/Deque                  50000000       24.7 ns/op       4 B/op      0 allocs/op
Random/list.List              30000000       46.9 ns/op      28 B/op      1 allocs/op

Getting Started

go get -u github.com/edwingeng/deque

Usage

dq := deque.NewDeque()
dq.PushBack(100)
dq.PushBack(200)
dq.PushBack(300)
for !dq.Empty() {
    fmt.Println(dq.PopFront())
}

dq.PushFront(100)
dq.PushFront(200)
dq.PushFront(300)
for i, n := 0, dq.Len(); i < n; i++ {
    fmt.Println(dq.PopFront())
}

// Output:
// 100
// 200
// 300
// 300
// 200
// 100

Harden the element data type

./harden.sh <outputDir> <packageName> [elemType]

Documentation

Overview

Package deque implements a highly optimized double-ended queue, which is much efficient compared with list.List when adding or removing elements from the beginning or the end.

Example

dq := NewDeque()
dq.PushBack(100)
dq.PushBack(200)
dq.PushBack(300)
for !dq.Empty() {
	fmt.Println(dq.PopFront())
}

dq.PushFront(100)
dq.PushFront(200)
dq.PushFront(300)
for i, n := 0, dq.Len(); i < n; i++ {
	fmt.Println(dq.PopFront())
}

Output:

100
200
300
300
200
100

Index

• func NumChunksAllocated() int64
• type Deque
  • func NewDeque() Deque
• type Elem

Examples

• Package

Functions

func NumChunksAllocated

func NumChunksAllocated() int64

NumChunksAllocated returns the number of chunks allocated by now.

Types

type Deque

type Deque interface {
	// PushBack adds a new value v at the back of Deque.
	PushBack(v Elem)
	// PushFront adds a new value v at the front of Deque.
	PushFront(v Elem)
	// PopBack removes a value from the back of Deque and returns
	// the removed value or nil if the Deque is empty.
	PopBack() Elem
	// PopFront removes a value from the front of Deque and returns
	// the removed value or nil if the Deque is empty.
	PopFront() Elem
	// Back returns the last value of Deque or nil if the Deque is empty.
	Back() Elem
	// Front returns the first value of Deque or nil if the Deque is empty.
	Front() Elem
	// Empty returns whether Deque is empty.
	Empty() bool
	// Len returns the number of values in Deque.
	Len() int

	// Enqueue is an alias of PushBack.
	Enqueue(v Elem)
	// Dequeue is an alias of PopFront.
	Dequeue() Elem
	// DequeueMany removes a number of values from the front of Deque and
	// returns the removed values or nil if the Deque is empty.
	// If max <= 0, DequeueMany removes and returns all the values in Deque.
	DequeueMany(max int) []Elem
	// DequeueManyWithBuffer is similar to DequeueMany except that it uses
	// buf to store the removed values as long as it has enough space.
	DequeueManyWithBuffer(max int, buf []Elem) []Elem

	// Range iterates all the values in Deque.
	Range(f func(i int, v Elem) bool)

	// Peek returns the value at idx.
	Peek(idx int) Elem
	// Replace replaces the value at idx.
	Replace(idx int, v Elem)
}

Deque is a highly optimized double-ended queue.

func NewDeque

func NewDeque() Deque

NewDeque creates a new Deque instance.

type Elem

type Elem = interface{}