Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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())
}
@benhamill

This comment has been minimized.

Copy link

benhamill commented Nov 5, 2012

This was really helpful for me, a go newbie, to see. Thanks for the examples.

@brweber2

This comment has been minimized.

Copy link

brweber2 commented Nov 9, 2012

Isn't this unsafe once you start using goroutines? Nothing is synching the pushes and pops, not to mention the q.count incrementing and decrementing... Am I missing something here?

@moraes

This comment has been minimized.

Copy link
Owner Author

moraes commented Jan 13, 2013

@brweber2 You are not missing anything. This is not safe for concurrent use. Sometimes you don't need to care about concurrency.

@shuhaowu

This comment has been minimized.

Copy link

shuhaowu commented Apr 11, 2013

Is this an O(n) insertion?

@JakubOboza

This comment has been minimized.

Copy link

JakubOboza commented Jul 23, 2013

this insert is expensive like hell.

@hishboy

This comment has been minimized.

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

This comment has been minimized.

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

This comment has been minimized.

Copy link

soroushjp commented Jan 13, 2015

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

This comment has been minimized.

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

This comment has been minimized.

Copy link

erikdubbelboer commented Apr 25, 2015

@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

This comment has been minimized.

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

This comment has been minimized.

Copy link

haisum commented Jan 22, 2016

Or you could use built-in heap package

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

@JTarasovic

This comment has been minimized.

Copy link

JTarasovic commented Apr 13, 2016

@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

This comment has been minimized.

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

This comment has been minimized.

Copy link

wingerse commented Jun 25, 2017

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

This comment has been minimized.

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())
	}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.