deque

Documentation

Overview

The deque package implements an efficient double-ended queue data structure called Deque.

Usage:

d := deque.New()
d.PushFront("foo")
d.PushBack("bar")
d.PushBack("123")
l := d.Len()          // l == 3
v, ok := d.PopFront() // v.(string) == "foo", ok == true
v, ok = d.PopFront()  // v.(string) == "bar", ok == true
v, ok = d.PopBack()   // v.(string) == "123", ok == true
v, ok = d.PopBack()   // v == nil, ok == false
v, ok = d.PopFront()  // v == nil, ok == false
l = d.Len()           // l == 0

A discussion of the internals can be found at the top of deque.go.

Index

• type Deque
  • func New() *Deque
  • func (d *Deque) Len() int
  • func (d *Deque) PopBack() (interface{}, bool)
  • func (d *Deque) PopFront() (interface{}, bool)
  • func (d *Deque) PushBack(item interface{})
  • func (d *Deque) PushFront(item interface{})

Types

type Deque

type Deque struct {
	// contains filtered or unexported fields
}

Deque implements an efficient double-ended queue.

Internally it is composed of a doubly-linked list (list.List) of blocks. Each block is a slice that holds 0 to blockLen items. The Deque starts with one block. Blocks are added to the front and back when the edge blocks fill up as items are pushed onto the deque. Edge blocks are removed when blocks become empty as items are popped off the Deque.

Only the front and back blocks may contain less than blockLen items. The first element in the Deque is d.blocks.Front().Value[d.frontIdx]. The last element in the Deque is d.blocks.Back().Value[d.backIdx].

This approach is more efficient than using a standard doubly-linked list for a queue because memory allocation is only required every blockLen items, instead of for each pushed item. Conversely, fewer memory deallocations are required when popping items. Bookkeeping overhead per item is also reduced.

func New

func New() *Deque

New returns a new Deque instance.

func (*Deque) Len

func (d *Deque) Len() int

Len returns the number of items stored in the queue.

func (*Deque) PopBack

func (d *Deque) PopBack() (interface{}, bool)

PopBack removes an item from the back of the queue and returns it. The returned flag is true unless there were no items left in the queue.

func (*Deque) PopFront

func (d *Deque) PopFront() (interface{}, bool)

PopFront removes an item from the front of the queue and returns it. The returned flag is true unless there were no items left in the queue.

func (*Deque) PushBack

func (d *Deque) PushBack(item interface{})

PushBack adds an item to the back of the queue.

func (*Deque) PushFront

func (d *Deque) PushFront(item interface{})

PushFront adds an item to the front of the queue.