Data Structure Series - Stacks

Last In, First Out

Data Structure Series - Stacks

This article gives a brief introduction of implementing stacks in Go language.

We will be doing the 3 basic operations related to stacks:

Push: Inserts an element to the top of the stack

Pop: Removes an element from the top of the stack, throws a runtime error in case of an empty stack

Top: Returns the top element of the stack, throws a runtime error in case of an empty stack

Utility functions:

IsEmpty: Returns a boolean to denote whether the stack is empty

After defining the operations, let's define the interface for a stack. Note: The example uses int data type.

type IStack interface {
    Push(val int)
    Pop()
    Top() int
    IsEmpty() bool
}

After defining the interface, the next step is to define a struct which implements the above interface and can be used as a stack in different functions.

type Stack struct {}

Now, we will decide on which field to add in the above struct. As this code uses int stack as example, we will use a slice of int.

type Stack struct {
    elems []int
}

Now that the struct is defined, we will define all the methods associated with it. First comes the Push method.

func (s *Stack) Push(val int) {
    s.elems = append(s.elems,val)
}

Next comes the Pop method.

func (s *Stack) Pop() {
    if s.IsEmpty() {
        //panics when there is no top element to pop
        panic("Cannot remove element from empty stack")
    }
    s.elems = s.elems[:len(s.elems)-1]
}

Following it with the Top method.

func (s *Stack) Top() int {
    if s.IsEmpty() {
        //panics when there is no top element to return
        panic("cannot reference top element of empty stack")
    }
    return s.elems[len(s.elems)-1]
}

And lastly, the IsEmpty method.

func (s *Stack) IsEmpty() bool {
    return len(s.elems) == 0
}

With this, all the methods are defined and our struct is an implementation of the stack interface. Now, let's start with a function that will take care of the initializations and return an implementation of the stack.

func NewStack() IStack {
    return &Stack{
        elems: make([]int,0) // creates an empty slice of integers
    }
}

Example:

func main(){
    s := NewStack()
    s.Push(1)
    fmt.Println(s.Top()) //prints 1
    s.Pop()
    fmt.Println(s.Top()) //panics
}

Feel free to try out this question on leetcode.com.