deque

package module
Version: v1.0.3 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Aug 31, 2022 License: BSD-3-Clause Imports: 3 Imported by: 11

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

Examples

Constants

This section is empty.

Variables

This section is empty.

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{}

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL