Data Structures with Go - Part 4: Stacks

Using Arrays in the backend.

Data Structures with Go - Part 4: Stacks

All code from this tutorial can be found here.

After completing this tutorial you should be able to:

  1. Create arrays and slices.

  2. Use the makefunction.

  3. Create methods for structs.

  4. Create statically allocated stacks.

  5. Create dynamically allocated stacks.


- Lets Talk about Stacks Babbyyy!!!!!

Stacks are abstract data types. The underlying data structure that we can use with stacks are:

  1. Arrays

  2. Linked Lists

In this tutorial, we will learn about implementing stacks using arrays.

The underlying array can either be:

  1. Statically allocated: Once created the size of the array cannot be changed.

  2. Dynamically allocated: After the creation of the array, its size can be expanded as needed.

The basic structure of Stacks

A stack is a Last In First Out (LIFO) structure. What this means is that the latest element added to the stack is at the top and will be the first to be removed from the stack. Think of it as a pile of books. The first book that you can remove from the pile is the one at the top of the pile. This is what stacks are all about.

The first book that can be removed from the pile is the one at the top.Figure 1: The first book that can be removed from the pile is the one at the top.

Our struct to create stacks will be as follows:

capacity is the maximum number of elements that can be stored in the stack. top is the index of the element at the top of the stack. data is an array that stores the elements in the stack.

Stack operations

We will define the following ops on the stack:

  1. Push: Adding elements to the stack.

  2. Pop: Removing elements from the stack.

  3. Peek: Look at the top of the stack without popping it.

  • Pushing to a stack at full capacity results in a stack overflow.
  • Popping from an empty stack results in a stack underflow.

We use the functions below to check if the stack is full or empty.

The syntax above may look a bit strange at first. Why is the (s *Stack) after the keyword func ?

This is how we create methods in Go. Methods can be called via the . operator. So to check if a stack xis empty we can now use x.IsEmpty() . The code above assigns the methods isEmpty() and isFull() to a pointer of struct Stack .

MethodsisEmpty() and isFull() are called the method set of the type *Stack. Here *Stackis called the method receiver in golang speak.

Method receivers are types assigned as receivers to functions. After associating receivers these functions become methods of that type.

Method sets are methods associated to a particular type.

Arrays & Slices in Go

An array is a numbered sequence of elements of a single type, called the element type. The number of elements is called the length of the array and is never negative. Arrays are zero indexed. Refer to https://golang.org/ref/spec#Array_types for more.

Eg — var x [10]int will create an integer array of size 10. Once created the size of the array cannot be changed.

Slices in Go are a way of creating dynamically allocated arrays. Slices are zero indexed. Learn more about slices here: https://golang.org/ref/spec#Slice_types

The makefunction helps allocate memory for a slice. The syntax of the make function is:

make([]T, length, capacity)

where T is a go type, length is the length of the slice and capacity is the amount of memory to allocate for this array.

Eg — x := make([]int,10,10) will create an integer slice of size 10 and capacity 10.

But how is this dynamically allocated you ask?

We can append elements to the slice via the append function. For example,

x := make([]int,10,10)
x = append(x,1234)

appends 1234 to the array x. On printing the slice, the output will be [0,0,0,0,0,0,0,0,0,0,1234] .

Use len(x) to find the length of the slice x.

Use cap(x) to find the capacity of the slice x.

After appending an element, the length of the slice increases by 1, and now the 11th element can be indexed by x[10] .

Once the current capacity of the slice is exceeded, it is increased by a factor of 2. So now if we now print cap(x) the output will be 20.

Statically allocated stacks

Creating the stack

The function above creates a stack of size stack_size using the make function and returns a pointer to that stack. We initialize the top of the stack to -1 to indicate that the stack is empty and initialize the capacity of the stack to stack_size .

Now let's create methods for the stacks ops:

Push

The method is self-explanatory. First check if the stack is full, if not increment the top index and assign the new data point at that index in the stack.

Pop

This method is self-explanatory as well. First, check if the stack is empty and if it isn’t, store the value popped in a temporary variable and decrement top.

Peek

This method is the same as the pop method, the only difference being that we don't decrement the top pointer.

Dynamically allocated stacks

The only way dynamic stacks are different from static stacks is in their creation and push methods.

To create the stack:

Note how we set the length of the slice to 0 and don't define the capacity. This is because we want to dynamically increase the size of the stack as and when needed.

Now let's see how the push method differs,

Push

Notice how we use the appendmethod to push new elements onto the stack. By doing this, the go runtime dynamically provisions memory for the slice data increasing its length by 1 whenever a new element is appended and it's capacity by 2 whenever the slice runs out of memory.

If we run this function a few times, the output would be:

                 STACK: {0 -1 []}
Pushing 10 to the stack.
        Stack Overflow. Increasing stack size to 1
                 STACK: {1 0 [10]}
Pushing 11 to the stack.
        Stack Overflow. Increasing stack size to 2
                 STACK: {2 1 [10 11]}
Pushing 12 to the stack.
        Stack Overflow. Increasing stack size to 4
                 STACK: {4 2 [10 11 12]}
Pushing 13 to the stack.
                 STACK: {4 3 [10 11 12 13]}
Pushing 14 to the stack.
        Stack Overflow. Increasing stack size to 8
                 STACK: {8 4 [10 11 12 13 14]}
Pushing 15 to the stack.
                 STACK: {8 5 [10 11 12 13 14 15]}
Pushing 16 to the stack.
                 STACK: {8 6 [10 11 12 13 14 15 16]}
Pushing 17 to the stack.
                 STACK: {8 7 [10 11 12 13 14 15 16 17]}
Pushing 18 to the stack.
        Stack Overflow. Increasing stack size to 16
                 STACK: {16 8 [10 11 12 13 14 15 16 17 18]}

Notice how the capacity of the stack starts at 0. When 10 is pushed, it is first increased to 1. Then when 11 is pushed, the capacity is increased to 2. But when 12 is pushed the capacity is now increased to 4 and so on. Towards the end, the capacity of the stack is at 16.

As the capacity of the current slice runs out, a new one with double the size is created and all the elements are copied from the old array to this new array of which is double the size of the original.

The sample function to test out pushing and popping in static and dynamic stacks can be found here.

As you can see, static and dynamically allocated stacks are the same but different. The only way they differ is how memory is provisioned for the data stored on the stack.

And that brings us to the end of this article.

You should now know:

  1. How to create methods in Go.

  2. How arrays and slices differ in Go.

  3. How to use make to create slices.

  4. How to append elements to arrays and slices.

  5. How to create static and dynamically allocated stacks in Go.


If you enjoyed reading this article or if it helped you in any way, a 👏 is appreciated. Do share this article with others who may be interested in the topic too.

Stay in touch with me on Linkedin and Twitter. Follow me on GitHub.