# Data Structures with Go - Part 4: Stacks

## Using Arrays in the backend.

Aahan Singh
·Jul 11, 2021·  Subscribe to my newsletter and never miss my upcoming articles

# 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 `make`function.

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

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. 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 `x`is empty we can now use `x.IsEmpty()` . The code above assigns the methods `isEmpty()` and `isFull()` to a pointer of struct `Stack` .

Methods`isEmpty()` and `isFull()` are called the method set of the type `*Stack`. Here `*Stack`is 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 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 `make`function 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` .

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 `append`method 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 }
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.

### 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.