-
-
Save moraes/2141121 to your computer and use it in GitHub Desktop.
package main | |
import ( | |
"fmt" | |
) | |
type Node struct { | |
Value int | |
} | |
func (n *Node) String() string { | |
return fmt.Sprint(n.Value) | |
} | |
// NewStack returns a new stack. | |
func NewStack() *Stack { | |
return &Stack{} | |
} | |
// Stack is a basic LIFO stack that resizes as needed. | |
type Stack struct { | |
nodes []*Node | |
count int | |
} | |
// Push adds a node to the stack. | |
func (s *Stack) Push(n *Node) { | |
s.nodes = append(s.nodes[:s.count], n) | |
s.count++ | |
} | |
// Pop removes and returns a node from the stack in last to first order. | |
func (s *Stack) Pop() *Node { | |
if s.count == 0 { | |
return nil | |
} | |
s.count-- | |
return s.nodes[s.count] | |
} | |
// NewQueue returns a new queue with the given initial size. | |
func NewQueue(size int) *Queue { | |
return &Queue{ | |
nodes: make([]*Node, size), | |
size: size, | |
} | |
} | |
// Queue is a basic FIFO queue based on a circular list that resizes as needed. | |
type Queue struct { | |
nodes []*Node | |
size int | |
head int | |
tail int | |
count int | |
} | |
// Push adds a node to the queue. | |
func (q *Queue) Push(n *Node) { | |
if q.head == q.tail && q.count > 0 { | |
nodes := make([]*Node, len(q.nodes)+q.size) | |
copy(nodes, q.nodes[q.head:]) | |
copy(nodes[len(q.nodes)-q.head:], q.nodes[:q.head]) | |
q.head = 0 | |
q.tail = len(q.nodes) | |
q.nodes = nodes | |
} | |
q.nodes[q.tail] = n | |
q.tail = (q.tail + 1) % len(q.nodes) | |
q.count++ | |
} | |
// Pop removes and returns a node from the queue in first to last order. | |
func (q *Queue) Pop() *Node { | |
if q.count == 0 { | |
return nil | |
} | |
node := q.nodes[q.head] | |
q.head = (q.head + 1) % len(q.nodes) | |
q.count-- | |
return node | |
} | |
func main() { | |
s := NewStack() | |
s.Push(&Node{1}) | |
s.Push(&Node{2}) | |
s.Push(&Node{3}) | |
fmt.Println(s.Pop(), s.Pop(), s.Pop()) | |
q := NewQueue(1) | |
q.Push(&Node{4}) | |
q.Push(&Node{5}) | |
q.Push(&Node{6}) | |
fmt.Println(q.Pop(), q.Pop(), q.Pop()) | |
} |
I made a thread safe, fixed size, blocking or dropping version FIFO queue here.
https://gist.github.com/edhemphill/314a10f44d361627ef940d96659fff79
I'd also point out that if you are doing a lot of in/outs in your containers, using interfaces may not be a great idea: https://www.limitlessfx.com/golang-using-interface-vs-specific-type.html
Using some generics tool (I just use m4), you can build fast, purpose built, static typed containers just like you can in C++. Meta-programming has been around for almost 3 decades, and there is a good reason for that.
Yeah @edhemphill Meta-programming has been around for quite a long time but apparently Go does not think it's important enough to implement it in the compiler.
Go standard lib has implement container/list,which is simple to use as queue or stack,queue and stack are subset of list.
package main
import (
"container/list"
"fmt"
)
func main(){
//last in first out, Stack use list
stack := list.New()
for i:=0;i<100;i++ {
stack.PushBack(i)
}
//
for stack.Back()!=nil {
fmt.Println(stack.Back().Value)
stack.Remove(stack.Back())
}
//Fist In Fist Out,queue use list
queue := list.New()
for i:=0;i<100;i++ {
queue.PushBack(i)
}
for queue.Front()!=nil {
fmt.Println(queue.Front().Value)
queue.Remove(queue.Front())
}
}
Simple FIFO queue in golang using "container/list"
package main
import (
"container/list"
"fmt"
)
func NewQueue() *Queue{
return &Queue{
l: list.New(),
}
}
type Queue struct {
l *list.List
}
func (q *Queue) Len() int{
return q.l.Len()
}
func (q *Queue) IsEmpty() bool{
return q.l.Len() == 0
}
func (q *Queue) Push(item interface{}){
q.l.PushBack(item)
}
func (q *Queue) Pop() interface{}{
return q.l.Remove(q.l.Back())
}
func main() {
myQueue := NewQueue()
myQueue.Push("Hello")
myQueue.Push("World")
myQueue.Push("!")
myQueue.Push("From")
myQueue.Push("Sudesh")
for !myQueue.IsEmpty() {
fmt.Println(myQueue.Pop())
}
}
Simple FIFO fixed length (size restricted) queue in golang using "container/list"
package main
import (
"container/list"
"fmt"
)
func NewQueue(len int) *Queue{ // constraint : length > 0
return &Queue{
l: list.New(),
len: len,
}
}
type Queue struct {
l *list.List
len int
}
func (q *Queue) Len() int{
return q.l.Len()
}
func (q *Queue) IsEmpty() bool{
return q.l.Len() == 0
}
func (q *Queue) Push(item interface{}){
for q.l.Len() >= q.len {
q.l.Remove(q.l.Front())
}
q.l.PushBack(item)
}
func (q *Queue) Pop() interface{}{
return q.l.Remove(q.l.Back())
}
func main() {
myQueue := NewQueue(5)
myQueue.Push("Hello")
myQueue.Push("World")
myQueue.Push("!")
myQueue.Push("From")
myQueue.Push("Sudesh")
myQueue.Push("Shetty")
myQueue.Push("Toronto")
for !myQueue.IsEmpty() {
fmt.Println(myQueue.Pop())
}
}
Please remove poiter in Stringer:
func (n Node) String() string {
return fmt.Sprint(n.Value)
}
i like @rasky method it seems more clearer it defines O(1) insertion well
@haisum I think
container/heap
is sorted which wouldn't be appropriate.https://golang.org/src/container/heap/heap.go
Note that you have to implement the
sort
interface.And that
up
,down
, andfix
all re-sort the heap.