Last active
May 1, 2023 19:02
-
-
Save moraes/2141121 to your computer and use it in GitHub Desktop.
LIFO Stack and FIFO Queue in golang
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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()) | |
} |
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
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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.