The highest tagged major version is
README
¶
Deque
This package implements a double ended queue using circular doubly linked list. It provides means for efficient insertion and retrieval at both the ends. It can be used as a stack as well as a queue.
Both LIFO (last in first out) operations and FIFO (first in first out)
operations are supported on the generic type Deque.
Performance
Deque is a data structure that allows to add and remove items at both ends in constant time. Thus, it is optimized for that purpose. Other operations like access or modification to items present somewhere in the middle of the list takes time linear the number of items in the deque.
Doubly linked list allows items to be appended dynamically (unlike array or
ring buffer implementation). Since it is coded in go, all operations are
memory safe. nil deque is readonly. It means that methods like Len, Clear,
Front, Back, PopFront and PopBack handle nil deques the same as empty
deque. But write or modify operations return ErrInit.
Examples
package main
import (
"fmt"
"log"
"github.com/bingxueshuang/deque"
)
func main() {
q := deque.New[string]()
deque.Must(q.PushBack("foo")) // { "foo" }
deque.Must(q.PushBack("bar")) // { "foo", "bar" }
deque.Must(q.PushFront("baz")) // { "baz", "foo", "bar" }
fmt.Println("Length:", q.Len()) // 3
fmt.Println("Front:", deque.Must1(q.Front())) // baz
fmt.Println("Back:", deque.Must1(q.Back())) // bar
fmt.Println("Pop:", deque.Must1(q.PopBack())) // bar
fmt.Println("Pop:", deque.Must1(q.PopBack())) // foo
fmt.Println("Pop:", deque.Must1(q.PopBack())) // baz
}
Documentation
¶
Overview ¶
Package deque implements deque data structure for fast append and pop at both ends of the queue.
Methods on type Deque are of the form:
d.{op}{loc}
where `op` is 'Push', 'Pop' or empty; and `loc` is 'Front' or 'Back'
The type *Deque implements Interface and internally uses a circular doubly linked list for storing items.
Index ¶
- Variables
- func Must(err error)
- func Must1[T any](value T, err error) T
- type Deque
- func (d *Deque[T]) At(index int) (item T, err error)
- func (d *Deque[T]) Back() (item T, err error)
- func (d *Deque[T]) Clear()
- func (d *Deque[T]) Front() (item T, err error)
- func (d *Deque[T]) Len() int
- func (d *Deque[T]) PopBack() (item T, err error)
- func (d *Deque[T]) PopFront() (item T, err error)
- func (d *Deque[T]) PushBack(item T) error
- func (d *Deque[T]) PushFront(item T) error
- type Interface
Constants ¶
This section is empty.
Variables ¶
var ( // ErrUnderflow is returned when an empty deque is queried for // an item. ErrUnderflow = errors.New("deque underflow") // ErrIndexBounds is returned when requested index exceeds // the length of the deque. ErrIndexBounds = errors.New("deque index out of bounds") // ErrInit is returned when the deque is either nil or // in an invalid state. This would not be needed if the // deque is always properly initialised. ErrInit = errors.New("deque is not properly initialised") )
Functions ¶
Types ¶
type Deque ¶
type Deque[T any] struct { // contains filtered or unexported fields }
Deque is double ended queue data structure implemented using circular doubly linked list. *Deque satisfies Interface.
func (*Deque[T]) At ¶
At returns the element at the specified index. If the index is negative, it refers to ith element from the back of the deque. If index exceeds the length of the deque, returns ErrIndexBounds.
func (*Deque[T]) Back ¶
Back returns the item at the back of the deque. If it is called on an empty deque, it returns ErrUnderflow.
func (*Deque[T]) Front ¶
Front returns the item at the front of the deque. It returns ErrUnderflow if called on an empty deque.
func (*Deque[T]) PopBack ¶
PopBack removes and returns the item at the back of the deque. It returns ErrUnderflow if called on an empty deque.
func (*Deque[T]) PopFront ¶
PopFront removes and returns the item at the front of the deque. It returns ErrUnderflow if called on an empty deque.
type Interface ¶
type Interface[T any] interface { Back() (T, error) // item at the back of the deque Clear() // reset the deque Front() (T, error) // item at the front of the deque Len() int // length of the deque PopBack() (T, error) // remove and return last item PopFront() (T, error) // remove and return first item PushBack(x T) error // insert at the back of the deque PushFront(x T) error // insert at the front of the deque At(index int) (T, error) // access i-th element }
Interface represents abstract data type (ADT) for deque data structure. It provides basic methods insert, delete and access elements from the deque. The type Deque implements Interface.
Source Files