queue

README

Queue

Introduction

Queue is a implementation of the queue ADT in Go. This implementation comes with two notable features:

1. Pluggable queue backends;
2. Optional (abeit simple) general thread-safety.

Install

go get -v bitbucket.org/jvulic/queue

Usage

Creating a queue; both safe and non-safe varients.

queue.New() // default non-safe queue
queue.New(queue.Backend(queue.NewDQ())) // non-safe queue with queue backend

queue.New(queue.Safe()) // default thread-safe queue
queue.New(queue.Safe(), queue.Backend(queue.NewDQ())) // thread-safe queue with queue backend

General use -- follows from how one might expect a queue to behave.

// Create a queue.
q := queue.New()

// Put some content into the queue using PushBack() and PushFront() methods.
q.Push(1)
q.Push(2)
q.Push(3)

// Lets see what element is at the front of the queue.
first := q.Front() // 1
fmt.Printf("%v is the first element")

// Lets print out the contents of the queue.
for d.Length() > 0 {
  fmt.Println(d.Front())
  d.Pop()
}

Backends

Currently supports the following backend:

Deque

Implements a queue using a queue as the backend provider.

Tests

Tests can be run by executing make test.

Benchmarks

Benchmarks can be run by executing make bench.

Below is an example of the benchmarking output:

PASS
BenchmarkListQueue-8      10000000         138 ns/op        28 B/op        1 allocs/op
BenchmarkListQueueSafe-8   5000000         378 ns/op        28 B/op        1 allocs/op
BenchmarkRingQueue-8      20000000          61.9 ns/op         4 B/op        0 allocs/op
BenchmarkRingQueueSafe-8   5000000         279 ns/op         4 B/op        0 allocs/op
BenchmarkSliceQueue-8     20000000          93.7 ns/op        30 B/op        0 allocs/op
BenchmarkSliceQueueSafe-8  5000000         331 ns/op        24 B/op        0 allocs/op
ok    bitbucket.org/jvulic/queue  10.743s

License

MIT License

Documentation

Overview

Package queue provides a flexible implemenation of the queue ADT.

Index

• type Option
  • func Backend(queue Queue) Option
  • func Safe() Option
• type Queue
  • func New(opt ...Option) Queue
  • func NewDQ() Queue
  • func NewDQSelect(deq deque.Deque) Queue

Types

type Option

type Option func(*options)

Option configures aspects of the queue.

func Backend

func Backend(queue Queue) Option

Backend returns an Option that sets the implemenation of the underlying queue.

func Safe

func Safe() Option

Safe returns an Option that synchronizes access to the underlying deque implementation.

type Queue

type Queue interface {
	// Returns the current length of the queue.
	Length() int

	// Returns the current capacity of the queue. Returns -1 for inf capacity.
	Capacity() int

	// Returns the element at the head of the queue; does NOT remove it. Panics
	// if the queue is empty.
	Front() interface{}

	// Adds an element to the head of the queue.
	Push(elem interface{})

	// Removes the element at the head of the queue. Panics if the queue is empty.
	Pop()
}

Queue defines the queue ADT.

func New

func New(opt ...Option) Queue

New creates a new queue.

func NewDQ

func NewDQ() Queue

NewDQ creates the default deque-based queue.

func NewDQSelect

func NewDQSelect(deq deque.Deque) Queue

NewDQSelect creates a new queue with the given deque as the backend.