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

@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