Implementation of stack data structure in golang (without using builtin len)

Implementation of stack data structure in go. 

Stack data structure follows LIFO order which is LastInFirstOut, which means element entered last will be out first.

Examples of stack in real life:

Stack of pancakes which are piled up.

The last pancake which is at the top is the first one to be taken out.

Stack data structures consists of two fields to maintain the data: 

Top element of the stack,
List of elements in the stack.

To make use of this data structure we need a way to push any new element to the stack, remove an element from existing stack, update the top values accoridngly.

Two more useful functions that helps when we are working with stack is to know what is the current top element and wherther stack is empty or not.

From the above discussion we need four different functions on Stack.

Push() ---> To push data to the stack and update the top value.

Pop()--> To remove the top element and update the top value.

Peek()--> To return the top value, this doesn't change the current stack.

isEmpty()--> Check if stack is empty or not.

Implementation of stack in golang:

To start with create a struct with the name with two fields top and list of elements which is slice in go.

type Stack struct{
   top int
   slice []int
}

Initialize the struct, writing function for the same:

func (s *Stack) NewStack(){
   s.top = -1
   s.slice = make([]int,0)
}

Let's proceed with pushing an element to the stack, our slice is list of integer types, so we will push only integers to this stack.

PUSH():

func (s *Stack) Push(x int){
      s.slice = append(s.slice, x)
      s.top++
   
}

All that we want to do in push is append the element to the list, if it's a new one slice will be of size 0, so appending this will add it as the first element. Increment the top value.

Each element gets stored in a memory location and given finite memory locations we can't keep pushing infinite elements to stack. We need a cap on the top value and throw an error if we are out of memory.

Consider we have unsigned int get the max value of unsigned int as below:

const MaxUint = ^uint(0)
const MAX_SIZE = int(MaxUint >> 1)

Now while we push the data we need to check if top value is with in the MAX_SIZE.

Updating the push function:

func (s *Stack) Push(x int){
   if s.top > MAX_SIZE - 1 {
      fmt.Println("Stack overflow")
   } else{
      s.slice = append(s.slice, x)
      s.top++
   }
}

This throws error incase top exceeds MAX_SIZE.

Pop():

func (s *Stack) Pop(){
      s.slice = s.slice[:s.top]
      s.top--
      fmt.Printf("slice %+v, top %d", s.slice,s.top)
}

Update the slice by removing the last inserted element and decrement the top by 1.

We can return the element that has  been removed so let's update the pop function.

func (s *Stack) Pop() int{
      x = s.slice[s.top]
      s.slice = s.slice[:s.top]
      s.top--
      fmt.Printf("slice %+v, top %d", s.slice,s.top)
   
   return x
}

We need a way to know that stack doesn;t have any more elements to pop, update the pop function with this check.

If top value is less than 0 then throw error where we can no longer pop any elements from the stack.

func (s *Stack) Pop() int{
   var x int
   if s.top < 0{
      fmt.Println("Stack underflow")
      return -1
   } else{
      x = s.slice[s.top]
      s.slice = s.slice[:s.top]
      s.top--
      fmt.Printf("slice %+v, top %d", s.slice,s.top)
   }
   return x
}

Peek():

We need to return the top element in the stack, the difference between Peek and Pop is ,

In Pop we update the stack by removing the top element,
In peek we just read the data from the stack.

Implementation is same as Pop except updating the stack.

func (s *Stack) Peek() int{
   var x int
   if s.top < 0 {
      fmt.Println("Stack underflow")
      return 0
   } else{
      x = s.slice[s.top]
   }
   return x
}

isEmpty():

Check if the stack is empty based on the top value, if it's less than 0 stack is empty.

func (s *Stack) isEmpty() bool{
   return s.top < 0
}

Complete code is available here: