deque

package
v0.0.0-...-6f48322 Latest Latest
Warning

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

Go to latest
Published: Aug 10, 2015 License: LGPL-3.0 Imports: 1 Imported by: 0

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

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

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 NewWithMaxLen

func NewWithMaxLen(maxLen int) *Deque

New returns a new Deque instance which is limited to a certain length. Pushes which cause the length to exceed the specified size will cause an item to be dropped from the opposing side.

A maxLen of 0 means that there is no maximum length limit in place.

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.

Jump to

Keyboard shortcuts

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