Slice Based Stack Implementation in Golang

Stack data structure using Golang

Photo by Fatos Bytyqi on Unsplash

A stack is a linearly ordered data structure in which the addition of new elements — or the deletion of an existing element — always takes place at the same end. This means that the last element inserted would be the first one treated before moving on to the next element. This specific order is called LIFO (Last in, First out). In relation to this definition, the term “linear” refers to data elements being traversed sequentially; and the term “ordered” refers to sequence counts being inserted.

In this article, I will show you how to implement a stack in Golang using slice. You can read more about slice in another article A Comprehensive Guide to Slices in Golang.

Image 1: Stack

A stack data structure has its own operations and properties as follows:

• Push operation: this adds a new element to the stack
• Pop operation: this removes the latest pushed element to the top of the stack.
• A peek or top property: this is the element at the top of the stack

This situation can be compared to a stack of plates in a cafeteria where every new plate added to the stack is added at the top. Similarly, every new plate taken off the stack is also taken from the top of the stack.

Push operation

Here is a graphical illustration of the push operation performed on the stack. It shows how the stack grows from left to right as items get pushed to it. Let’s try to insert few items one after another [10,20,30,40,50,60].

Image 2: Push operations

Pop operation

Here is the graphical illustration of the pop operation performed on the stack. It shows how the stack shrinks and the position of the top changes from left to right as items get popped from it.

Image 3: Pop operations

Please note: Before you go any further, I expect you all have a beginner level understanding of Golang syntax and primitive types to understand the source-code.

Implementation of the stack in Golang

Declaring a model

Code Listing 1.1

The model for the stack consists of the following properties:

1. items: The slice of type ItemType, (this holds items in the stack)
2. rwLock: For handling concurrent operations on the stack
3. The top property of the stack is directly not present in my implementation. I have maintained it through slice operations.

Implementing a push operation

Code Listing 1.2

The implementation of the push method is as described below:

1. From lines no. 4 to 6 it checks if slice for items is initialized or not. If not then the initialization is done.
2. At line no. 8 it acquires a write lock to avoid dirty reads by other threads.
3. At line no. 10 it pushes new items to the stack using the append function.
4. At line no. 12 the lock is released as the operation is completed successfully.

Implementing a pop operation

Code Listing 1.3

The implementation of the pop method is as described below:

1. From lines no. 4 to 6 it checks for the empty stack.
2. At line no. 8 it acquires a write lock to avoid dirty reads by other threads.
3. At line no.10 it gets top elements from items slice and stores it for returning purpose.
4. At line no.12 it removes the top element from the slice and adjusts its length.
5. At line no.14 the lock is released as the operation is completed successfully.
6. At line no.16 it returns the value of the last popped element.

Size of the stack

Code Listing 1.4

This is a simple operation that returns the number of items present in the stack.

Get all items present in the stack

Code Listing 1.5

The purpose of writing this method is to get all items present in the stack to see the current stack snapshot.

Check whether the stack is empty or not

Code Listing 1.6

The purpose of writing this method is to check if the stack is empty or not.

Click here to review & run the above code on the Golang playground.

Application of stack

Stacks are useful for any application requiring LIFO storage. There are many, many of these. Here are some examples:

• The stack can be used for evaluating an arithmetic expression.
• The stack can be used to check matching parentheses in an expression.
• The stack can be used for parsing context-free languages.
• The stack can be used for memory management.
• The stack can be used for function call management.
• The Stack data structures are used in backtracking problems.

Conclusion

The stack is a linear and ordered type of data structure that follows the LIFO (Last In, First Out) rule for its data items. As the stack plays a very important role in solving many of the computational problems that a programmer comes across, I highly recommend that people gain an understanding of the concept as well as how to employ it in their projects. I hope this article was a good introduction to the stack, please leave any feedback or questions in the comment section! Thanks for reading.