Documentation ¶
Overview ¶
Lane package provides queue, priority queue, stack and deque data structures implementations. Its was designed with simplicity, performance, and concurrent usage in mind.
Index ¶
- type Deque
- func (s *Deque) Append(item interface{}) bool
- func (s *Deque) Capacity() int
- func (s *Deque) Empty() bool
- func (s *Deque) First() interface{}
- func (s *Deque) Full() bool
- func (s *Deque) Last() interface{}
- func (s *Deque) Pop() interface{}
- func (s *Deque) Prepend(item interface{}) bool
- func (s *Deque) Shift() interface{}
- func (s *Deque) Size() int
- type PQType
- type PQueue
- type Queue
- type Stack
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Deque ¶
Deque is a head-tail linked list data structure implementation. It is based on a doubly linked list container, so that every operations time complexity is O(1).
every operations over an instiated Deque are synchronized and safe for concurrent usage.
Example ¶
// Let's create a new deque data structure var deque *Deque = NewDeque() // 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") // Now let's take a look at what are the first and // last element stored in the Deque firstValue := deque.First() lastValue := deque.Last() fmt.Println(firstValue) // "abc" fmt.Println(lastValue) // 1 // Okay now let's play with the Pop and Shift // methods to bring the song words together var jacksonFive []string = make([]string, deque.Size()) for i := 0; i < len(jacksonFive); i++ { value := deque.Shift() jacksonFive[i] = value.(string) } // abc 123 easy as do re mi fmt.Println(strings.Join(jacksonFive, " "))
Output:
func NewCappedDeque ¶
NewCappedDeque creates a Deque with the specified capacity limit.
func (*Deque) Append ¶
Append inserts element at the back of the Deque in a O(1) time complexity, returning true if successful or false if the deque is at capacity.
func (*Deque) First ¶
func (s *Deque) First() interface{}
First returns the first value stored in the deque in a O(1) time complexity
func (*Deque) Last ¶
func (s *Deque) Last() interface{}
Last returns the last value stored in the deque in a O(1) time complexity
func (*Deque) Pop ¶
func (s *Deque) Pop() interface{}
Pop removes the last element of the deque in a O(1) time complexity
func (*Deque) Prepend ¶
Prepend inserts element at the Deques front in a O(1) time complexity, returning true if successful or false if the deque is at capacity.
type PQType ¶
type PQType int
PQType represents a priority queue ordering kind (see MAXPQ and MINPQ)
type PQueue ¶
PQueue is a heap priority queue data structure implementation. It can be whether max or min ordered and it is synchronized and is safe for concurrent operations.
Example ¶
// Let's create a new max ordered priority queue var priorityQueue *PQueue = NewPQueue(MINPQ) // 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) // Now let's take a look at the min element in // the priority queue headValue, headPriority := priorityQueue.Head() fmt.Println(headValue) // "abc" fmt.Println(headPriority) // 1 // Okay the song order seems to be preserved, let's // roll var jacksonFive []string = make([]string, priorityQueue.Size()) for i := 0; i < len(jacksonFive); i++ { value, _ := priorityQueue.Pop() jacksonFive[i] = value.(string) } fmt.Println(strings.Join(jacksonFive, " "))
Output:
func (*PQueue) Head ¶
Head returns the highest/lowest priority item (depending on whether you're using a MINPQ or MAXPQ) from the priority queue
func (*PQueue) Pop ¶
Pop and returns the highest/lowest priority item (depending on whether you're using a MINPQ or MAXPQ) from the priority queue
type Queue ¶
type Queue struct {
*Deque
}
Queue is a FIFO (First in first out) data structure implementation. It is based on a deque container and focuses its API on core functionalities: Enqueue, Dequeue, Head, Size, Empty. Every operations time complexity is O(1).
As it is implemented using a Deque container, every operations over an instiated Queue are synchronized and safe for concurrent usage.
Example ¶
// Create a new queue and pretend we're handling starbucks // clients var queue *Queue = NewQueue() // Let's add the incoming clients to the queue queue.Enqueue("grumpyClient") queue.Enqueue("happyClient") queue.Enqueue("ecstaticClient") fmt.Println(queue.Head) // grumpyClient // Let's handle the clients asynchronously for client := queue.Dequeue(); client != nil; { go fmt.Println(client) }
Output:
func (*Queue) Dequeue ¶
func (q *Queue) Dequeue() interface{}
Dequeue removes and returns the front queue item
type Stack ¶
type Stack struct {
*Deque
}
Stack is a LIFO (Last in first out) data structure implementation. It is based on a deque container and focuses its API on core functionalities: Push, Pop, Head, Size, Empty. Every operations time complexity is O(1).
As it is implemented using a Deque container, every operations over an instiated Stack are synchronized and safe for concurrent usage.
Example ¶
// Create a new stack and put some plates over it var stack *Stack = NewStack() // Let's put some plates on the stack stack.Push("redPlate") stack.Push("bluePlate") stack.Push("greenPlate") fmt.Println(stack.Head) // greenPlate // What's on top of the stack? value := stack.Pop() fmt.Println(value.(string)) // greenPlate stack.Push("yellowPlate") value = stack.Pop() fmt.Println(value.(string)) // yellowPlate // What's on top of the stack? value = stack.Pop() fmt.Println(value.(string)) // bluePlate // What's on top of the stack? value = stack.Pop() fmt.Println(value.(string)) // redPlate
Output:
func (*Stack) Head ¶
func (s *Stack) Head() interface{}
Head returns the item on the top of the stack