Implementing Stack in Go

What is Stack? Stack is last-in-first-out (LIFO) data structure, which means that it it returns the most recently added item on pop.

Use cases

Stack has pretty wide spectre of use cases, for example stack is being used in programming languages in order to keep track of instruction calls (i.e. method call recursion), another example could be implementation of mathematical calculator based on stack, where stack keeps track of operations and operands.

Requirements

Ok, hence we’ve discovered some use case, let’s see what are the operations we want from Stack to perform?

1. Stack should be able to store items ( > push )
2. Stack should be able to retrieve items ( > pop ) 

This is it, these two are the major ones, we would also need to be able to know if Stack is empty and its size, but this is more for convenience.

type Stack interface {
    Push(item Item)
    Pop() Item
    IsEmpty() bool
    Size() int
}

Linked list

Today we implement Stack based on the linked list data structure. 

Why use linked list and not array as a base? I find these two reasons quite compelling:

• Space required for linked list is always proportional to the size of the Stack.
• Time per operation in linked list is always independent of the size of the Stack.

Here is how linked list node might look like in Go:

type node struct {
    value Item
    next *node
}

where value is the item to be stored and next is the next element in the list.

For simplicity, we can define interface Item to represent arbitrary object stored in Stack.

type Item interface {
    GetInt() int
}

Implementation

In order to store and retrieve  element from the Stack in constant time O(1), we need to keep track of the head (first element in the Stack).

type Stack struct {
    first *node
    size  int
}

Now let’s implement Push method, when item is being added to Stack, we need to replace head with provided new item and point this new item to the previous head:

func (s *Stack) Push(item Item) {
    s.first = &node{
        value: item,
        next: s.first,
    }
    s.size++
}

Opposite action is to retrieve item from Stack, which involves changing head to the next element in the Stack and returning head to the client, there is a little snag to it, we need to first remember old head (current first) before changing it to the next element:

func (s *Stack) Pop() Item {
    if s.IsEmpty() {
        return nil
    }
    oldFirst := s.first
    s.first = s.first.next
    s.size--
    return oldFirst.value
}

Ignore IsEmpty method for now it is very simple, I promise.

This is pretty much it. The rest is just a quality of life improvements. Clients might want to know size of the Stack:

func (s *Stack) Size() int {
    return s.size
}

And also if Stack is empty or not:

func (s *Stack) IsEmpty() bool {
    return s.first == nil
}

Simple, told ya! Full example can be found in algorithms-go project here.