Lane

The Lane package provides textbook implementations of generic Queue, PriorityQueue, Stack, and Deque data structures. Its design focuses on simplicity, performance, and concurrent usage.

• Lane
  • Installation
    • Using v2 releases
    • Using v1 releases
  • Usage/Examples
    • Priority queue
      • Example
    • Deque
      • Deque example
    • Queue
      • Queue example
    • Stack
      • Stack example
  • Performance
  • Documentation
  • License

Installation

Using this package requires a working Go environment. See the install instructions for Go.

This package requires a modern version of Go supporting modules: see the go blog guide on using Go Modules.

Using v2 releases

go get github.com/oleiade/lane/v2

...
import (
 "github.com/oleiade/lane/v2"
)
...

Using v1 releases

go get github.com/oleiade/lane

...
import (
 "github.com/oleiade/lane"
)
...

Usage/Examples

Priority queue

PriorityQueue implements a heap priority queue data structure. It can be either max (descending) or min (ascending) ordered. Every operation on a PriorityQueue is goroutine-safe. It performs Push and Pop operations in O(log N) time.

Example

// Create a new max ordered priority queue
priorityQueue := NewMaxPriorityQueue[string, int]()

// And push some prioritized content into it
priorityQueue.Push("easy as", 3)
priorityQueue.Push("123", 2)
priorityQueue.Push("do re mi", 4)
priorityQueue.Push("abc", 1)

// Take a look at the min element in
// the priority queue
headValue, headPriority, ok := priorityQueue.Head()
if ok {
    fmt.Println(headValue)    // "abc"
    fmt.Println(headPriority) // 1
}

// The operations seem to preserve the song order
jacksonFive := make([]string, priorityQueue.Size())

for i := 0; i < len(jacksonFive); i++ {
    value, _, _ := priorityQueue.Pop()
    jacksonFive[i] = value
}

fmt.Println(strings.Join(jacksonFive, " "))

Deque

Deque implements a head-tail linked list data structure. Built upon a doubly linked list container, every operation performed on a Deque happen in O(1) time complexity. Every operation on a Deque are goroutine-safe.

Users have the option to instantiate Deques with a limited capacity using the dedicated NewBoundDeque constructor. When a bound Deque is full, the Append and Prepend operations fail.

Deque example

// Create a new Deque data structure
deque := NewDeque[string]()

// And push some content into it using the Append
// and Prepend methods
deque.Append("easy as")
deque.Prepend("123")
deque.Append("do re mi")
deque.Prepend("abc")

// Take a look at what the first and
// last element stored in the Deque are.
firstValue, ok := deque.First()
if ok {
    fmt.Println(firstValue) // "abc"
}

lastValue, ok := deque.Last()
if ok {
    fmt.Println(lastValue) // 1
}

// Use the `Pop` and `Shift`
// methods to bring the song words together
jacksonFive := make([]string, deque.Size())

for i := 0; i < len(jacksonFive); i++ {
    value, ok := deque.Shift()
    if ok {
        jacksonFive[i] = value
    }
}

// abc 123 easy as do re mi
fmt.Println(strings.Join(jacksonFive, " "))

Queue

Queue is a FIFO (First In First Out) data structure implementation. Built upon a Deque container, it focuses its API on the following core functionalities: Enqueue, Dequeue, Head. Every operation on a Queue has a time complexity of O(1). Every operation on a Queue is goroutine-safe.

Queue example

// Create a new queue and pretend to handle Starbucks clients
queue := NewQueue[string]()

// Add the incoming clients to the queue
queue.Enqueue("grumpyClient")
queue.Enqueue("happyClient")
queue.Enqueue("ecstaticClient")

fmt.Println(queue.Head()) // grumpyClient

// Handle the clients asynchronously
for {
    client, ok := queue.Dequeue()
    if !ok {
        break
    }

    fmt.Println(client)
}

Stack

Stack implements a Last In First Out data structure. Built upon a Deque container, its API focuses on the following core functionalities: Push, Pop, Head. Every operation on a Stack has a time complexity of O(1). Every operation on a Stack is goroutine-safe.

Stack example

// Create a new stack and put some plates over it
stack := NewStack[string]()

// Put some plates on the stack
stack.Push("redPlate")
stack.Push("bluePlate")
stack.Push("greenPlate")

fmt.Println(stack.Head()) // greenPlate

// Check the top of the stack
value, ok := stack.Pop()
if ok {
    fmt.Println(value) // greenPlate
}

stack.Push("yellowPlate")

value, ok = stack.Pop()
if ok {
    fmt.Println(value) // yellowPlate
}

// Check the top of the stack
value, ok = stack.Pop()
if ok {
    fmt.Println(value) // bluePlate
}

// Check the top of the stack
value, ok = stack.Pop()
if ok {
    fmt.Println(value) // redPlate
}

Performance

go test -bench=.
goos: darwin
goarch: arm64
pkg: github.com/oleiade/lane/v2
BenchmarkDequeAppend-8          22954384        54.44 ns/op      32 B/op       1 allocs/op
BenchmarkDequePrepend-8         25097098        44.59 ns/op      32 B/op       1 allocs/op
BenchmarkDequePop-8             63403720        18.99 ns/op       0 B/op       0 allocs/op
BenchmarkDequeShift-8           63390186        20.88 ns/op       0 B/op       0 allocs/op
BenchmarkDequeFirst-8           86662152        13.76 ns/op       0 B/op       0 allocs/op
BenchmarkDequeLast-8            85955014        13.76 ns/op       0 B/op       0 allocs/op
BenchmarkDequeSize-8            86614975        13.77 ns/op       0 B/op       0 allocs/op
BenchmarkDequeEmpty-8           86893297        14.22 ns/op       0 B/op       0 allocs/op
BenchmarkBoundDequeFull-8       590152324         2.039 ns/op       0 B/op       0 allocs/op
BenchmarkBoundDequeAppend-8     64457216        18.50 ns/op       0 B/op       0 allocs/op
BenchmarkBoundDeque-8           64631377        18.48 ns/op       0 B/op       0 allocs/op
BenchmarkPriorityQueuePush-8    19994029        65.67 ns/op      72 B/op       1 allocs/op
BenchmarkPriorityQueuePop-8     62751249        18.52 ns/op       0 B/op       0 allocs/op
BenchmarkPriorityQueueHead-8    86090420        13.77 ns/op       0 B/op       0 allocs/op
BenchmarkPriorityQueueSize-8    86768415        13.77 ns/op       0 B/op       0 allocs/op
BenchmarkPriorityQueueEmpty-8   87036146        13.76 ns/op       0 B/op       0 allocs/op
BenchmarkNewQueue-8             19570003        60.36 ns/op
BenchmarkQueueEnqueue-8         25482283        46.63 ns/op      32 B/op       1 allocs/op
BenchmarkQueueDequeue-8         63715965        18.50 ns/op       0 B/op       0 allocs/op
BenchmarkQueueHead-8            85664312        13.79 ns/op       0 B/op       0 allocs/op
BenchmarkNewStack-8             19925473        59.57 ns/op
BenchmarkStackPop-8             64704993        18.80 ns/op       0 B/op       0 allocs/op
BenchmarkStackHead-8            86119761        13.76 ns/op       0 B/op       0 allocs/op

Documentation

For a more detailed overview of lane, please refer to Documentation

License

MIT