Skip to content

Instantly share code, notes, and snippets.

@moraes
Last active May 1, 2023 19:02
Show Gist options
  • Save moraes/2141121 to your computer and use it in GitHub Desktop.
Save moraes/2141121 to your computer and use it in GitHub Desktop.
LIFO Stack and FIFO Queue in golang
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())
}
@masihtehrani
Copy link

Please remove poiter in Stringer:

func (n Node) String() string {
	return fmt.Sprint(n.Value)
}

@Philip-21
Copy link

Philip-21 commented Sep 29, 2022

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