How to Build a Stack (not overflow!) using Go in less than 10 minutes

Published in

Oh my cod!

8 min readAug 22, 2022

There is an old saying in computer science: “There is no problem that cannot be solved by the proper application of data structures.” This is true for many problems, from sorting a list of numbers to searching for a specific piece of information in a large database.

You might not think that a simple data structure could be powerful, but the stack is notoriously good at solving computer science problems. In fact, the stack is so powerful that it is often used in complex algorithms.

But what is a stack actually? How is it used? Why should I use it? Follow me in this tutorial and answer yourself these questions.

What is a stack?

A stack is a linear data structure that allows two operations: push and pop. Push adds an element to the top of the stack, and pop removes an element from the top of the stack. The order in which elements are added to the stack (pushed) and removed from the stack (popped) is Last In First Out (LIFO).

A stack is a type of data structure that allows for data to be added or removed in a last-in, first-out (LIFO) manner. That is, the most recently added element is the first one to be removed.

Push is adding an element to the stack. Pop is removing it.

How might it be used?

You might be thinking, “why would anyone want to use a data structure that doesn’t allow for data to be added or removed in a first-in, first-out manner?” Well, there are actually a few situations where a stack can be useful

Balancing symbols in code

When writing code, it is important to make sure that every opening symbol has a corresponding closing symbol. For instance, every time you open a parentheses, you should close it later on. You can use a stack to keep track of symbols.

Whenever you encounter an opening symbol, you push it onto the stack. When you encounter a closing symbol, you check to see if there is a corresponding opening symbol on the top of the stack. If there is, you pop the opening symbol off the stack. If there is not, then there is an error in the code.

Managing function calls.

In order for a computer program to keep track of where it is in its execution, it needs to maintain a stack of all the function calls that have been made. This way, when a function returns, the program can pop the last function call off the stack and continue execution from that point.

Undoing/Redoing Operations

Stacks can also be used to implement Undo functionality in text editors and other applications. When an action is performed, its details are pushed onto a stack. If the user wants to undo that action, the details are popped off the stack and the inverse action is performed. This allows the user to undo their recent actions, one at a time.

Keeping track of most Recent Operations

The stack pattern is also used to keep track of the ‘most recently used’ feature. I am sure you have come across the most recently seen files, items, tools etc.. across different applications. Your browser uses the stack pattern to maintain the recently closed tabs, and reopen them.

Why to use it?

There are many advantages of using a stack data structure. Some of the main advantages are:

Very quick access to data: This is because the data is stored in a linear fashion, which means that it can be accessed quickly and easily.
Very easy to implement: This is because the data structure is simple and there are only a few operations that need to be performed on it.
Very versatile: This is because they can be used to store data of any type, including strings, integers, floats, and objects.

Why not to use it?

There are several disadvantages of using stack data structure:

Stack size is fixed: This means that we need to know the maximum number of elements that will be stored in the stack in advance. And if the stack size is exceeded, the stack will overflow. This can vary depending on the language we are using. Some languages like Python and JavaScript allow to create dynamic arrays.
Limited operations: We can only perform two operations on a stack, i.e. push and pop. We cannot randomly access any element in the stack.
Not suitable for large data sets: Since the stack size is fixed, it is not suitable for storing large data sets.
Not efficient: Stacks are not very efficient when it comes to storage as we need to reserve space for the stack even if we are not using all of it.

Implementing a Stack in Go

There are several reasons to use Golang when building a stack data structure.

Golang is a statically typed language, which means that types are checked at compile time, making it more difficult to introduce errors into your program.
Additionally, Golang’s syntax is clean and concise, making it easy to read and understand.
Finally, Golang is a very fast and efficient language, which is important when working with data structures.

Why pointers?

There are a few reasons why you might want to use Golang’s pointers to build a stack data structure

Pointers allow you to dynamically allocate memory for your stack, which means that you can grow or shrink the stack as needed. This can be more efficient than using an array, which requires you to pre-allocate a fixed amount of memory.
Pointers also give you more flexibility in terms of the operations you can perform on your stack. For example, you can easily implement a “pop” operation by simply decrementing the pointer, rather than having to shift all of the other elements down in an array.
Finally, pointers can make it easier to keep track of your stack’s size, since you can simply increment or decrement the pointer as elements are added or removed.

Creating our data structure

Structs are a way to structure and use data. It allows us to group data. To use a struct we declare the type of struct we are going to use.

In our case we’ll create a stack for storing pointers to any type of data

type item struct {
    value interface{} // hold any data type
    next  *item
}

type Stack struct {
    top  *item
    size int
}

Adding the push capability

Structs consist of data, but apart from this, structs also tell about the behavior in the form of methods. Methods attached to structs is very much similar to the definition of normal functions, the only variation is that you need to additionally specify its type.

By push we mean inserting an element to the stack.

func (stack *Stack) Push(v interface{}) {
  stack.top = &item{
  value: v,
  next:  stack.top,
 }
 stack.size++
}

Adding the pop capability

By pop we mean removing an element from the stack. Before performing a pop operation we should be aware of the length of the stack and if is empty so let’s implement all these funtions.

func (stack *Stack) Len() int {
 return stack.size
}func (stack *Stack) isEmpty() bool {
  return stack.Len() == 0
}func (stack *Stack) Pop() interface{} {
  if stack.isEmpty() { // to avoid overflow.
    return nil
  }
  
  valueToPop := stack.top.value
  stack.top = stack.top.next
  stack.size := stack.size - 1  return valueToPop
}

Adding the peek capability

It allows us to get the value of the item we would drop if we apply a pop operation without removing it from the stack.

func (stack *Stack) Peek() interface{} {
  if stack.isEmpty() {
    return nil
  }
  return stack.top.value
}

Check how we return nil in case the stack is empty and how we still use interface to not to couple our stack to any specific type.

Putting it all together

package mainimport "fmt"type item struct {
    value interface{} // hold any data type
    next  *item
}type Stack struct {
    top  *item
    size int
}func (stack *Stack) Push(v interface{}) {
  stack.top = &item{
  value: v,
  next:  stack.top,
 }
 stack.size++
}func (stack *Stack) Len() int {
 return stack.size
}func (stack *Stack) isEmpty() bool {
  return stack.Len() == 0
}func (stack *Stack) Pop() interface{} {
  if stack.isEmpty() {
    return nil
  }
  
  valueToPop := stack.top.value
  stack.top = stack.top.next
  stack.size --
  return valueToPop
}func (stack *Stack) Peek() interface{} {
  if stack.isEmpty() {
    return nil
  }
  return stack.top.value
}func main() {
  var integerStack Stack = Stack{};
  integerStack.Push(100) // 100 is the new stack
  integerStack.Push(200) // 100 - 200 is the new stack
  fmt.Println(integerStack.Peek()) // 200
  integerStack.Pop() // Pops 200 | 100 is the new stack
  integerStack.Push(300) // 100 - 300 is the new stack
  fmt.Println(integerStack.Peek()) // 300 is the new peek
}

Wrapping up

Stacks are a great data structure for many applications and can be very helpful in solving problems. However, they have their own set of pros and cons that you should be aware of before using them. Do you have any experience with using stacks? Did you use them in some novel way? Please share it in the comments.

If you found this article helpful, please share it and if you have any questions about stacks leave a comment below!

Thanks for reading!