README
¶
Queue that can return Min() value in O(1).
Queue that can return the minimum element in O(1) time where no operation is worse than O(1) amortized.
The name 'quack' is a smash up of 'queue' and 'stack', because the queue is implemented using two stacks.
Example usage:
package main
import (
"fmt"
"github.com/kevinms/quack-go"
"math/rand"
)
func lessInt(a, b interface{}) bool {
return a.(int) < b.(int)
}
func main() {
q := quack.NewQuack(lessInt)
n := 1000000
for i := 0; i < n; i++ {
q.Push(rand.Int())
}
fmt.Printf("Len: %v, Min: %v\n", q.Len(), q.Min())
for q.Len() > n/2 {
q.Pop()
}
fmt.Printf("Len: %v, Min: %v\n", q.Len(), q.Min())
}
Documentation
¶
Overview ¶
Package quack implements a FIFO Queue that can return the minimum value in the queue in O(1) time. The name 'quack' is a smash up of 'queue' and 'stack', because the queue is implemented using two stacks.
A Quack's worst case runtime of every public method is O(1) except Pop(), which is amortized O(1).
func lessInt(a, b interface{}) bool {
return a.(int) < b.(int)
}
func main() {
q := quack.NewQuack(lessInt)
n := 1000000
for i := 0; i < n; i++ {
q.Push(rand.Int())
}
fmt.Printf("Len: %v, Min: %v\n", q.Len(), q.Min())
for q.Len() > n/2 {
q.Pop()
}
fmt.Printf("Len: %v, Min: %v\n", q.Len(), q.Min())
}
Stack is a LIFO stack that can return the minimum value in the stack in O(1) time.
A Stack's worst case runtime of every public method is O(1).
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type LessFunc ¶
type LessFunc func(a, b interface{}) bool
LessFunc is used to compare items stored in the Quack and determine which is the smallest.
type Quack ¶
type Quack struct {
// contains filtered or unexported fields
}
Quack is a FIFO Queue that can return the minimum value in the queue in O(1) time.
A Quack's worst case runtime of every public method is O(1) except Pop(), which is amortized O(1).
Example ¶
q := NewQuack(lessInt)
a := []int{2, 0, 8, 3, 4}
for _, n := range a {
q.Push(n)
}
for q.Len() > 0 {
fmt.Println(q.Min())
q.Pop()
}
Output: 0 0 3 3 4
func (*Quack) Min ¶
func (q *Quack) Min() interface{}
Min returns the smallest value in the quack in O(1).
type Stack ¶
type Stack struct {
// contains filtered or unexported fields
}
Stack is a LIFO stack that can return the minimum value in the stack in O(1) time.
A Stack's worst case runtime of every public method is O(1).
Example ¶
s := NewStack(lessInt)
a := []int{4, 3, 8, 0, 2}
for _, n := range a {
s.Push(n)
}
for s.Len() > 0 {
fmt.Println(s.Min())
s.Pop()
}
Output: 0 0 3 3 4
func (*Stack) Min ¶
func (s *Stack) Min() interface{}
Min returns the smallest value in the stack in O(1).
Source Files