LIFO Stack and FIFO Queue in golang

gistfile1.go

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

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

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?

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

Is this an O(n) insertion?

this insert is expensive like hell.

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

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

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 :)

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

@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

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

Or you could use built-in heap package

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

@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