-
Star
(125)
You must be signed in to star a gist -
Fork
(29)
You must be signed in to fork a gist
-
-
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()) | |
| } |
@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.
30 type Interface interface {
31 sort.Interface
32 Push(x interface{}) // add x as element Len()
33 Pop() interface{} // remove and return element Len() - 1.
34 }And that up, down, and fix all re-sort the heap.
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
Or you could use built-in heap package
https://golang.org/pkg/container/heap/#pkg-overview