Creating Stack Data Structures in Golang

• Jason Ladd

So, basically a stack is a linear data structure that follows the principle of LIFO (Last in, First out). An easy way to think of this is having a stack of books on a desk. As you layer books on top of each other, you have to remove the ones at the top of the stack in order to get to the ones at the bottom. So keeping that real-world analogy in mind, stacks generally have some capacity, or limit to how many items can fit inside the stack. Let's look at how to implement stacks using Slices in Go.

Stacks need three main operations, push, pop, and peek. Pushing something onto the stack is just adding a new element to it, and popping is removing whatever element is on top of the stack. Peeking is just being able to see which element is on top of the stack without actually removing it. So how would we implement this data structure in Go?

Go doesn't have any built in methods like pop or peek. It technically does have append(), which can be used to push elements onto a slice, but we're not gonna use that in this example because it has a bit of extra overhead due to the fact that it handles re-sizing slices and for our demonstration, we don't need that.

Aside from those methods, the data that our stack needs to keep up with are the following: It's capacity (we'll call it size here), a pointer to it's topmost element, and a slice to hold the elements. So let's start out by creating a struct that holds all of this. I'm also going to use the "any" type for the slices values. Of course, depending on your use case, it might be better to restrict them to one type, or a group of specific types using generics, but "any" (or empty interfaces) offer the most flexibility since we can store whatever we want in there. I'm also gonna use a mutex on it because we're going to be mutating instances of this struct so we need them to be concurrency safe. As a recap, mutexes allow us to lock and unlock the instances so that we don't get race condintions when mutating variables. 


type Stack struct {
	Size  uint
	Top   int
	Slice []any
	mu    sync.Mutex
}

Now that we've defined our stack struct, let's start off by creating a function that will allow us to instantiate a stack of some specific size.


func CreateStack(size uint) *Stack {
	st := Stack{
		Size: size,
		Top:  -1,
	}

	st.Slice = make([]any, size)

	return &st
}

This function creates a stack and returns a pointer to it, so for example, if we wanted to create a stack that could hold 10 elements, we could now do this: 


var st *Stack = CreateStack(10)

Adding the Push, Pop, and Peek Methods

Now let's add the push, pop, and peek methods, starting with push. Like I mentioned before, we could use Go's built in append, but here's what it actually is doing:

  • Grows the capacity of the underlying array by doubling it or increasing the size by 25% each time if neccessary
  • Allocates new memory for the larger array
  • Copy's the data from the old array into the new one

But the cool thing about stacks, is we don't need any of that. We actually want our stack to adhere to it's capacity. If we try to push to it, and it's full, we'll want it to just let us know so that we can't push to it until the amount of elements has fallen below the capacity.

So to implement push, all we need to do is increment the index of our topmost element and add our our data to the slice at that index:


func (st *Stack) Push(data any) {
	st.mu.Lock()
	defer st.mu.Unlock()

	if st.IsFull() {
		return
	}

	st.Top++
	st.Slice[st.Top] = data
}

To describle a bit more of what's going on here, we're using Go's function receiver pattern to add this "Push" method onto a stack pointer. This pattern adds the method onto a stack pointer similiarly to if it were a class, so every stack pointer that we create will have the methods defined like this. It takes a parameter called "data" who's type is "any" (AKA an empty interface). We use the mutex to lock it at the beginning of execution and defer an unlock for after the function returns. Before actually incrementing the top element's index and setting the data there, we check if the stack is full or not. Remember that in our CreateStack function, we initialize our stack's top index to -1. So when we do the first increment, we're at element 0. We can also use this property of top being -1 to check if our stack is empty. Let's do that now:

One important thing to note! Go handles dereferencing pointers when you're accessing the property of some struct pointer, so we don't need to do that. We can just let it handle the dereferencing and access the .Top and .Slice as if it were the actual value instead of the pointer. 

func (st *Stack) IsEmpty() bool {
	return st.Top == -1
}

We're also using the receiver pattern to add the IsEmpty method to every stack pointer we create. It just returns a Boolean that lets us know if the top is -1. Note that we're only checking values here, not doing any mutation to the stack, so there's no need for the mutexes.

Of course, we need to also create a method to check if the stack is full:


func (st *Stack) IsFull() bool {
	return st.Top == int(st.Size-1)
}

Here, we're just checking to see if top is at the capacity. Note that in this case, we have to typecast the unsigned integer to a regular signed integer in order to do the comparision. We have to make sure we're comparing the same types.

Now, let's look at what our pop method needs to look like. We just want to be able to get the topmost element and remove it from the stack. So this method won't need any parameters, but it'll return the "popped off" element so it can be used.


func (st *Stack) Pop() any {
	st.mu.Lock()
	defer st.mu.Unlock()

	if st.IsEmpty() {
		return -1
	}

	st.Top--
	return st.Slice[st.Top+1]
}

Okay, so we've got the mutex locking and unlocking, then checking if the stack is empty, then we just decrement our top and return that new top index + 1, which gives us the position our top was just at. One big thing to notice, is that we didn't actually do any nulling out of the top element when we popped it off. It's still there, but since it's index has moved, it's not accessible by the stack (yeah technically, you could access it using the underlying slice but that's not the point!) The point is, we don't need to waste any CPU operations to actually remove it from memory because, as far as the stack is concerned, that space is available to be overwritten the next time we push to the stack. This way, we add and remove from the stack doing the least amount of work possible.

The last method we'll look at for our stack will be the "peek" method. This one is pretty easy since it's just like the "pop" method, but instead of decrementing the top element's index, we just return that element. So this:


func (st *Stack) Peek() any {
	if st.IsEmpty() {
		return -1
	}

	return st.Slice[st.Top]
}

Obviously, there's nothing to peek at if the stack is empty, so we check that first, then if it's not, we just return the top element of the slice.

So what's the point of a stack?

Why not just use an array or a slice? Because stacks are the most efficient ways to model things in the real world that need to follow that "last in, first out" principle. Think about something like browser history. As you navigate through a bunch of pages, you might want to go back... and keep going back to get to some page you were previously on. Stacks are perfect for this because as you naviagte, the pages you visited are pushed onto a stack, and when you go back, they're popped off of the stack. This is the same principle that undo/redo functionality uses in software. There are lots of other use cases too like traversing complex data structures like trees and graphs, but I'll save that topic for another post.

The Full Implementation

So, to put it all together, here's how it would look to create the stack data structure in Go. I've also added a print method so we can easily see what's contained in the stack.


package main

import (
	"fmt"
	"sync"
)

type Stack struct {
	Size  uint
	Top   int
	Slice []any
	mu    sync.Mutex
}

func CreateStack(size uint) *Stack {
	st := Stack{
		Size: size,
		Top:  -1,
	}

	st.Slice = make([]any, size)

	return &st
}

func (st *Stack) IsFull() bool {
	return st.Top == int(st.Size-1)
}

func (st *Stack) IsEmpty() bool {
	return st.Top == -1
}

func (st *Stack) Push(data any) {
	st.mu.Lock()
	defer st.mu.Unlock()

	if st.IsFull() {
		return
	}

	st.Top++
	st.Slice[st.Top] = data
}

func (st *Stack) Pop() any {
	st.mu.Lock()
	defer st.mu.Unlock()

	if st.IsEmpty() {
		return -1
	}

	st.Top--
	return st.Slice[st.Top+1]
}

func (st *Stack) Peek() any {
	if st.IsEmpty() {
		return -1
	}

	return st.Slice[st.Top]
}

func (st *Stack) Print() {
	for i := st.Top; i >= 0; i-- {
		fmt.Printf("%v, ", st.Slice[i])
	}
	fmt.Print("\n")
}
View all posts →