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())
}
@JakubOboza
Copy link

this insert is expensive like hell.

@hishboy
Copy link

hishboy commented Sep 22, 2013

Here's a link to thread-safe queue and stack with O(1) for push, pop, and poll

https://github.com/hishboy/gocommons/tree/master/lang

@rasky
Copy link

rasky commented Dec 24, 2014

Both can be simplified by using the built-in slice type, which has amortized O(1) insertion because of exponential growth:

type Queue []*Node

func (q *Queue) Push(n *Node) {
    *q = append(*q, n)
}

func (q *Queue) Pop() (n *Node) {
    n = (*q)[0]
    *q = (*q)[1:]
    return
}

func (q *Queue) Len() int {
    return len(*q)
}

type Stack []*Node

func (q *Stack) Push(n *Node) {
    *q = append(*q, n)
}

func (q *Stack) Pop() (n *Node) {
    x := q.Len() - 1
    n = (*q)[x]
    *q = (*q)[:x]
    return
}
func (q *Stack) Len() int {
    return len(*q)
}

(change *Node to whatever data type you want to store there).

@soroushjp
Copy link

To answer @shuhaowu:

OP's implementation of stacks is amortized O(1) insert, since it uses Go's amortized O(1) built-in append function. Worst case insert is O(n), when we have to reallocate new slice and copy into it.

OP's implementation of queues is O(n) since it grows its underlying array by a fixed step q.size while the number of elements that need copying continues to grow by n.

@rasky, that's a very elegant implementation of stacks and queues with Go slices :)

@akosela
Copy link

akosela commented Jan 14, 2015

@rasky implementation is superior here. In Go always try to use the built-in types first and slices are perfect to build stacks and queues with very good efficiency.

@erikdubbelboer
Copy link

@rasky's implementation might be cleaner but @moraes's version is more than twice as fast as I tested: http://blog.dubbelboer.com/2015/04/25/go-faster-queue.html

My version is a bit different as it also shrinks the queue when elements get removed: https://github.com/ErikDubbelboer/ringqueue/blob/master/ringqueue.go#L49

@pushrax
Copy link

pushrax commented Dec 4, 2015

@rasky's implementation causes unbounded memory growth even if the queue only ever contains a fixed number of elements, as Pop() never shrinks the underlying array. The GC does not understand slice offsets.

@haisum
Copy link

haisum commented Jan 22, 2016

Or you could use built-in heap package

https://golang.org/pkg/container/heap/#pkg-overview

@JTarasovic
Copy link

@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.

@edhemphill
Copy link

edhemphill commented Feb 28, 2017

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.

@wingerse
Copy link

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.

@JinAirsOs
Copy link

JinAirsOs commented Jun 3, 2019

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())
	}
}

@sudeshrshetty
Copy link

sudeshrshetty commented Nov 13, 2021

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())
	}
}

@sudeshrshetty
Copy link

sudeshrshetty commented Nov 13, 2021

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())
	}
}

@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