Stack is one of the most basic data structures that are not native to Go. Being most basic, it's by far the easiest to implement however it will also introduce fundamental concepts that will help you down the road with other data structures so it is critical that you make sure to get really solid understanding of it as much as other concepts that will be discussed as part of this post.

What is stack and why is it useful?

Think of a stack as a stack of coins inside a tube, you can see whats at the top, if you want to add a new coin you always put it at the top, when you want to remove coins, you always take them from the top and only way to see the bottom coin is to go through the entire stack top to bottom first - this is called LIFO principle (Last In, First Out). One of the most common ways you interact with a stack in daily life is any (basic) implementation of in memory history, whether its your browser tracking previously visited pages to provide option for navigating to previous pages, or your computer directly with clipboard functionality / text editors etc*. - in a case of browser history, whenever you navigate to a new page we use Push to add new item to the top of the stack (current page / head) and if you navigate back we can Pop the top item.

Browser history implements two stack model, backwards stack and forward stack where if you navigate back item is popped from backwards stack and pushed to forward stack - just like other examples this is the simplest way to explain without adding too much complexity

Underlying data structure of a stack

From the native data structures to Go two might immediately come to mind that are Slice and Array - before we can decide which one to use we have to get a good understanding of how they work under the hood.

• Array: utilizes pre-allocated block of continuous memory, cannot grow past fixed size
• Slice: just like Array it utilizes pre-allocated block of continuous memory, but unlike array when capacity is reached, new array is created in memory with double the capacity, all items are copied and previous array is de-referenced leaving garbage collector to clean it up as no references to the original array remain. However as the underlying array grows, and you start removing elements from the stack, the new larger array will maintain it's memory allocation even if the amount of items in the stack / array has decreased and the memory is not cleaned up until the array is completely de-referenced.

Based on the two definitions above, we can do one better by utilizing variation of a linked list. It can either be singly or doubly linked list. Their structure is almost identical, both referencing Head, Value and Previous (pointer to previous node), however doubly linked list also adds Tail, and Next (pointer to next node).

Per the earlier definition of a stack, only way we traverse is is down, hence not needing Next value, and since we only read the top most item we only care for the Head, hence picking singly linked list in our case would be ideal.

What does it look like in memory using singly linked list?

When first node (value) is created it's allocated randomly on the heap and variable Head is set to it's pointer, whenever new node is pushed to the stack, Head is set to the new node, while new node references pointer to Previous node which ensures garbage collector will not clear the memory where it resides. Finally when an item is removed from the top of the stack, Previous becomes the new Head, removing pointer reference to the old Head, hence garbage collector will find orphaned block of memory and clean it up.

Take a note that implementation in Go can be drastically different to implementation in other languages, the performance considerations you'll get from implementation in Go might not be universally true in other languages such as JavaScript and neither will be the underlying structure definitions due to different behaviors depending on their language level implementation

Develop tests

Let's start building our first stack (well, tests actually)! We are going to utilize Go's "testing" library to write basic unit tests to validate our functionality even before we start implementing the stack to create a safety net.

package stack_todo

import (

	"testing"
)

func TestPushToStack(t *testing.T) {
	// initiate new stack of your preferred data type
	stack := NewStack[int8]()


	// push an item to ensure stack is not empty
	stack.Push(2)

	// peek to find last item
	got, err := stack.Peek()
	if err != nil {
		t.Errorf("Peek threw an unexpected error: %q", err)
	}
	want := 2
	if got != int8(want) {
		t.Errorf("Push failed: received %d, expected %d", got, want)
	}
}

func TestPop(t *testing.T) {
	stack := NewStack[int8]()

	stack.Push(3)
	stack.Push(5)
	// this element will be popped
	stack.Push(1)
	stack.Pop()

	got, err := stack.Peek()
	if err != nil {
		t.Errorf("Peek threw an unexpected error: %q", err)
	}
	want := 5
	if got != int8(want) {
		t.Errorf("Pop failed: received %d, expected %d", got, want)
	}
}

func TestPopEmpty(t *testing.T) {
	stack := NewStack[int8]()
	
	stack.Pop()
	// test the size is handled correctly
	got := stack.Size()
	want := 0

	if got != int32(want) {
		t.Errorf("Pop on empty failed: received size %d, expected size %d", got, want)
	}
}

func TestPeekEmpty(t *testing.T) {
	stack := NewStack[int8]()

	_, err := stack.Peek()
	if err == nil {
		t.Errorf("Failed to throw error when peeking an empty stack.")
	}

}

func TestSize(t *testing.T) {
	stack := NewStack[int8]()

	stack.Push(1)
	stack.Push(2)
	stack.Push(4)
	stack.Push(2)
	poppedValue, err := stack.Pop()
	if err != nil {
		t.Errorf("Pop threw unexpected error: %q", err)
	}
	if poppedValue != 2 {
		t.Errorf("Pop returned incorrect value: %q", poppedValue)
	}
	stack.Push(6)
	stack.Push(3)
	poppedValue, err = stack.Pop()
	if err != nil {
		t.Errorf("Pop threw unexpected error: %q", err)
	}
	if poppedValue != 3 {
		t.Errorf("Pop returned incorrect value: %q", poppedValue)
	}
	
	got := stack.Size()
	want := 4

	// have to use int32 as the size is defined stack level
	if got != int32(want) {
		t.Errorf("Size validation failed: received %d, expected %d", got, want)
	}
}

The most important parts to understand here is when writing tests, make sure you consider your edge cases, specifically functions TestPeekEmpty and TestPopEmpty are the edge cases for us with stack, if stack has no nodes, we are unable to Peek as the head is not set, we wouldn't be able to reference Value of the head. Pop is similar story, for two reasons, our Size of the stack is set to int32, hence we cannot use negative numbers, we have to ensure that when attempt is made to pop an element of an empty stack, size is not being decremented. We also established that Pop is looking at Previous of our stack to set the new Head but if Head is nil the application will panic to nil pointer dereference.

Now that you know how to test your stack, feel free to pull the example repository and try to implement stack yourself, if you get stuck run tests to figure out what is still missing or reference the examples folder.

Try implementing stack yourself: https://github.com/mdichtler/Go-DSA-behindthe.dev/blob/main/internal/todo/stack/stack_todo.go

Run tests to validate your implementation: go test ./internal/todo/stack

Implementing stack

Let's create a new file stack.go and create some boilerplate, start by defining the node shape, interface with list of all of our functions, stack struct and init function.

package stack_todo

type Node[T any] struct {
	Value T
	Previous *Node[T]
}

type Stack[T any] interface {
	Peek() (T, error)
	Push(value T)
	Pop() (T, error)
	Size() int32
}


type NodeStack[T any] struct {
	Head *Node[T]
	size int32
}


func (s *NodeStack[T]) Peek() (T, error) {
	
}

func (s *NodeStack[T]) Push(value T) {

}

func (s *NodeStack[T]) Pop() (T, error) {
	
}

func (s *NodeStack[T]) Size() int32 {

}

func NewStack[T any]() Stack[T] {

}

Peek & Size

By far the easiest two functions of a stack are Peek and Size - for implementation of Peek let's remember back to our original example of a stack of coins where you can only see the top coin, or no coin if there are no stacked coins:

func (s *NodeStack[T]) Peek() (T, error) {
	// if Head is not set (no items in the stack)
	// ensure case is properly handled, refer to TestPeekEmpty for success criteria
	if s.Head == nil {
		var zero T
		return zero, fmt.Errorf("head is not set")
	}
	return s.Head.Value, nil
}

Implementing Size is that much easier, since we want to have as low time complexity as possible best we can do is use a variable that we created with our NodeStack struct which is size with o(1) time complexity for reading / writing.

func (s *NodeStack[T]) Size() int32 {
	return s.size
}

Push & POP

We only have two more functions to implement, let's start with simpler one which is Push - all we need to do is:

1. Increment size
2. Define a new Node referencing current Head as it's Previous
3. Set Head to our new Node

func (s *NodeStack[T]) Push(value T) {

	s.size++;

	s.Head = &Node[T]{
		Value: value,
		Previous: s.Head,
	}
}

Truly the only place you might make a mistake is implementation of Pop - to satisfy our tests, first we have to check there is at least one element in our Stack, if there is let's handle removal:

1. Validate Head is not nil, if nil return an error
2. Decrement size
3. Take note of current head so we can return value that is being popped
4. Set Head to the Previous value of current Head
5. Return value of popped Head

func (s *NodeStack[T]) Pop() (T, error) {
	if s.Head == nil {
		var zero T
		return zero, fmt.Errorf("you cannot pop from an empty stack")
	}

	s.size--;
	previous := s.Head
	s.Head = s.Head.Previous
	return previous.Value, nil

}

Fully implemented stack: https://github.com/mdichtler/Go-DSA-behindthe.dev/blob/main/internal/examples/stack/stack.go