Implement Stack in Golang

14 Sep 2020
Implement Stack in Golang

In this article, you will learn how to implement stack data structure in Golang. In case you are not aware of what stack is, we’ll cover the basics as well. Then, we will dive into implementation of stack in Go.

Let’s begin!


What is a Stack?

Stack is a linear data structure which follows a particular order named LIFO (Last in First out).

Stacks is mainly used to perform following operations -

  • Push
  • Pop
  • Peek/Top
  • isEmpty

All the operations stated above takes O(1) time.

Stack is a useful data structure. Some applications include:

  • Conversion from one form of expression to another.
  • Used in Memory Management.
  • Expression evaluation
  • Previous/Next pages in browsers.

Stacks in Go

In Golang, Stacks can be easily implemented with help of slices.

We first declare Item interface which can contain any data type. We define Stack struct which contains list of Item and a mutex lock (for concurrency purposes). We don’t want data inconsistency which might result in failure of struct. NewEmptyStack() and NewStack() are functions to create new stack.

// Item interface to store any data type in stack
type Item interface{}

// Stack struct which contains a list of Items
type Stack struct {
    items []Item
    mutex sync.Mutex
}

// NewEmptyStack() returns a new instance of Stack with zero elements
func NewEmptyStack() *Stack {
    return &Stack{
        items: nil,
    }
}

// NewStack() returns a new instance of Stack with list of specified elements
func NewStack(items []Item) *Stack {
    return &Stack{
        items: items,
    }
}

Here we implement following functions. Let’s explore them one by one.

Push()

Adds item to stack. If stack if full, this returns overflow error. Here we don’t handle overflow, you can add custom check and handle the error.

We lock the mutex so that no other changes are made and consistency is maintained (in concurrent environment)

// Push() adds new item to top of existing/empty stack
func (stack *Stack) Push(item Item) {
    stack.mutex.Lock()
    defer stack.mutex.Unlock()

    stack.items = append(stack.items, item)
}

Pop()

Removes item from stack. If stack if empty, this returns nil.

// Pop() removes most recent item(top) from stack
func (stack *Stack) Pop() Item {
    stack.mutex.Lock()
    defer stack.mutex.Unlock()

    if len(stack.items) == 0 {
        return nil
    }

    lastItem := stack.items[len(stack.items)-1]
    stack.items = stack.items[:len(stack.items)-1]

    return lastItem
}

Top()

This function returns the last inserted item from stack. This doesn’t remove item from stack.

// Top() returns the last inserted item in stack without removing it.
func (stack *Stack) Top() Item {
    stack.mutex.Lock()
    defer stack.mutex.Unlock()

    if len(stack.items) == 0 {
        return nil
    }

    return stack.items[len(stack.items)-1]
}

IsEmpty()

This function checks whether the stack is empty or not. Returns boolean result based on the state of stack.

// IsEmpty() returns whether the stack is empty or not (boolean result)
func (stack *Stack) IsEmpty() bool {
    stack.mutex.Lock()
    defer stack.mutex.Unlock()

    return len(stack.items) == 0
}

Size()

This function returns number of elements currently in the stack.

// Size() returns the number of items currently in the stack
func (stack *Stack) Size() int {
    stack.mutex.Lock()
    defer stack.mutex.Unlock()

    return len(stack.items)
}

Clear()

This function removes all elements from stack. Basically empties the stack by setting it to empty object.

// Size() returns the number of items currently in the stack
func (stack *Stack) Size() int {
    stack.mutex.Lock()
    defer stack.mutex.Unlock()

    return len(stack.items)
}

Final Code

Here is the complete code for implementing stack in Go.

package stack

import “sync”

// Item interface to store any data type in stack
type Item interface{}

// Stack struct which contains a list of Items
type Stack struct {
    items []Item
    mutex sync.Mutex
}

// NewEmptyStack() returns a new instance of Stack with zero elements
func NewEmptyStack() *Stack {
    return &Stack{
        items: nil,
    }
}

// NewStack() returns a new instance of Stack with list of specified elements
func NewStack(items []Item) *Stack {
    return &Stack{
        items: items,
    }
}

// Push() adds new item to top of existing/empty stack
func (stack *Stack) Push(item Item) {
    stack.mutex.Lock()
    defer stack.mutex.Unlock()

    stack.items = append(stack.items, item)
}

// Pop() removes most recent item(top) from stack
func (stack *Stack) Pop() Item {
    stack.mutex.Lock()
    defer stack.mutex.Unlock()

    if len(stack.items) == 0 {
        return nil
    }

    lastItem := stack.items[len(stack.items)-1]
    stack.items = stack.items[:len(stack.items)-1]

    return lastItem
}

// IsEmpty() returns whether the stack is empty or not (boolean result)
func (stack *Stack) IsEmpty() bool {
    stack.mutex.Lock()
    defer stack.mutex.Unlock()

    return len(stack.items) == 0
}

// Top() returns the last inserted item in stack without removing it.
func (stack *Stack) Top() Item {
    stack.mutex.Lock()
    defer stack.mutex.Unlock()

    if len(stack.items) == 0 {
        return nil
    }

    return stack.items[len(stack.items)-1]
}

// Size() returns the number of items currently in the stack
func (stack *Stack) Size() int {
    stack.mutex.Lock()
    defer stack.mutex.Unlock()

    return len(stack.items)
}

// Clear() removes all items from the stack
func (stack *Stack) Clear() {
    stack.mutex.Lock()
    defer stack.mutex.Unlock()

    stack.items = nil
}

Tests Please !!

Ok ok, how can we end this post without testing the code here. Here is a complete test code for the functions we implemented before. We use

package stack

import (
    “testing”

    “github.com/stretchr/testify/assert”
)

func TestPush(t *testing.T) {
    stack := NewEmptyStack()
    t.Run(“when item is pushed”, func(t *testing.T) {
        expectedStack := NewStack([]Item{
            1,
            2,
            3,
        })
        t.Run(“stack should be updated”, func(t *testing.T) {
            stack.Push(1)
            stack.Push(2)
            stack.Push(3)
            assert.Equal(t, stack, expectedStack)
        })
    })
}

func TestPop(t *testing.T) {
    stack := NewEmptyStack()
    t.Run(“when stack is empty”, func(t *testing.T) {
        expectedStack := NewEmptyStack()
        t.Run(“it should return nil response”, func(t *testing.T) {
            // Pop 1
            poppedItem := stack.Pop()
            assert.Equal(t, poppedItem, nil)
            assert.Equal(t, stack, expectedStack)
        })
    })

    t.Run(“when stack is not empty”, func(t *testing.T) {
        expectedStack := NewStack([]Item{
            1,
        })
        t.Run(“it should return last inserted item and update the stack”, func(t *testing.T) {
            // Push two items
            stack.Push(1)
            stack.Push(2)

            // Pop 1
            poppedItem := stack.Pop()
            assert.Equal(t, poppedItem, 2)
            assert.Equal(t, stack, expectedStack)
        })
    })
}

func TestIsEmpty(t *testing.T) {
    stack := NewEmptyStack()
    t.Run(“when stack is not empty”, func(t *testing.T) {
        t.Run(“it should return false, func(t *testing.T) {
            // Push one item
            stack.Push(1)
            assert.Equal(t, stack.IsEmpty(), false)
            // Pop one item
            stack.Pop()
            assert.Equal(t, stack.IsEmpty(), true)
        })
    })

    t.Run(“when stack is empty”, func(t *testing.T) {
        t.Run(“it should return true, func(t *testing.T) {
            // Pop one item
            stack.Pop()
            assert.Equal(t, stack.IsEmpty(), true)
        })
    })
}

func TestTop(t *testing.T) {
    t.Run(“when stack is not empty”, func(t *testing.T) {
        stack := NewEmptyStack()
        expectedStack := NewStack([]Item{
            1,
            2,
        })
        t.Run(“it should return last inserted item and no change in stack”, func(t *testing.T) {
            // Push two items
            stack.Push(1)
            stack.Push(2)

            item := stack.Top()
            assert.Equal(t, item, 2)
            assert.Equal(t, stack, expectedStack)
        })
    })

    t.Run(“when stack is empty”, func(t *testing.T) {
        stack := NewEmptyStack()
        t.Run(“it should return nil, func(t *testing.T) {
            item := stack.Top()
            assert.Equal(t, item, nil)
        })
    })
}

func TestSize(t *testing.T) {
    stack := NewEmptyStack()
    t.Run(“when stack is provided”, func(t *testing.T) {
        t.Run(“it should return number of items in stack”, func(t *testing.T) {
            // Push one item
            stack.Push(1)
            assert.Equal(t, stack.Size(), 1)
            // Pop one item
            stack.Pop()
            assert.Equal(t, stack.Size(), 0)
        })
    })
}

func TestClear(t *testing.T) {
    stack := NewEmptyStack()
    t.Run(“when stack is provided”, func(t *testing.T) {
        expectedStack := NewEmptyStack()
        t.Run(“it should clear all items in stack”, func(t *testing.T) {
            // Push one item
            stack.Push(1)
            stack.Push(2)
            stack.Clear()
            assert.Equal(t, stack, expectedStack)
        })
    })
}

Awesome! You just learned how to implement stack in Go. Time to implement it on your own. Try some basic stack problem, for a start try this -

Liked the article? Consider supporting me ☕️


I hope you learned something new. Feel free to suggest improvements ✔️

I share regular updates and resources on Twitter. Let’s connect!

Keep exploring 🔎 Keep learning 🚀

Liked the content? Do support :)

Paypal - Mohit Khare
Buy me a coffee