Introduction #

Unlike map and array/slice, Go doesn't have a built in Stack data structure, so let's try to write our own Stack implementation in Go.

The stack that we implement should have the following functions.

 
go
 // Push an item on the stack.
func Push(int)

// Pop an element from stack.
// If stack is empty the second return value if `false`.
func Pop() (int, bool)

Simple Stack #

A very simple approach using slices would be as follows.

 
go
 package main

type Stack struct {
	data []int
}

func (s *Stack) Push(v int) {
	s.data = append(s.data, v)
}

func (s *Stack) Pop() (int, bool) {
	if len(s.data) == 0 {
		return 0, false
	}

	v := s.data[len(s.data)-1]
	s.data = s.data[:len(s.data)-1]

	return v, true
}
stack.go

And you can use it as follows.

 
go
 package main

import "fmt"

func main() {
	s := Stack{}

	s.Push(1)
	s.Push(2)
	s.Push(3)

	fmt.Println(s.Pop()) // 3 true
	fmt.Println(s.Pop()) // 2 true
	fmt.Println(s.Pop()) // 1 true
	fmt.Println(s.Pop()) // 0 false
}
main.go

A Generic Stack #

The above approach is good but it only works with int, we want the stack to work with any data type. Let's make it generic!

 
go
 package main

type Stack[T any] struct {
	data []T
}

func (s *Stack[T]) Push(v T) {
	s.data = append(s.data, v)
}

func (s *Stack[T]) Pop() (T, bool) {
    var v T
	if len(s.data) == 0 {
		return v, false
	}

	v = s.data[len(s.data)-1]
	s.data = s.data[:len(s.data)-1]

	return v, true
}
stack.go

Everything is pretty much the same, you just added generic type T everywhere.

Below is the usage, but a string stack this time.

 
go
 package main

import "fmt"

func main() {
	s := Stack[string]{}

	s.Push("one")
	s.Push("two")
	s.Push("three")

	fmt.Println(s.Pop()) // one true
	fmt.Println(s.Pop()) // two true
	fmt.Println(s.Pop()) // three true
	fmt.Println(s.Pop()) //  true
}
main.go

Better, but not enough!

A Stack with Pointers #

The current stack implementation uses slices underneath, and we just append to the slice as we Push items.

If you know anything about Go's slices, you will notice that as we Pop items, the underlying array size remains the same.

As items get popped from the stack you can downsize the slice, but this requires extra work of copying elements from old slice to the new one. We need something else.

Implement the underlying stack as a Linked List.

 
go
 package main

// 👇 a node type to represent the linked list node
type StructNode[T any] struct {
	Value T
	Next  *StructNode[T]
}

type Stack[T any] struct {
	top *StructNode[T]
}

func (s *Stack[T]) Push(v T) {
	node := &StructNode[T]{
		Value: v,
		Next:  s.top,
	}

	s.top = node
}

func (s *Stack[T]) Pop() (T, bool) {
    var v T
	if s.top == nil {
		return v, false
	}

	v = s.top.Value
	s.top = s.top.Next

	return v, true
}
stack.go

Usage remains exactly the same, but with this implementation you don't need to worry about memory being wasted as you pop elements.

Good? No, not enough.

Goroutine Safe #

Protect your stack from race conditions, throw in a mutex.

 
go
 package main

import "sync"

type StructNode[T any] struct {
	Value T
	Next  *StructNode[T]
}

type Stack[T any] struct {
	top *StructNode[T]
	mut *sync.Mutex
}

func (s *Stack[T]) Push(v T) {
	s.mut.Lock()
	defer s.mut.Unlock()

	node := &StructNode[T]{
		Value: v,
		Next:  s.top,
	}

	s.top = node
}

func (s *Stack[T]) Pop() (T, bool) {
	s.mut.Lock()
	defer s.mut.Unlock()

    var v T
	if s.top == nil {
		return v, false
	}

	v = s.top.Value
	s.top = s.top.Next

	return v, true
}
stack.go