Stack Using Golang Generics

 


With the recent introduction of generics in Golang, they have proved themselves not only elegant and simple, but also very efficient, check out the performance characteristics here. Now it is time to demonstrate their power in creating flexible data structures in this post. As promised in a later post, we are going to implement a stack in this post. The rest of this post is organized as follows:

  1. what is a stack
  2. stack methods
  3. implementation in Golang
  4. testing our stack



What is a Stack

Stacks are simple data structures that powers a great deal of modern computational systems like function calls in compilers themselves, LRU policy of memory block replacements, bracket matching problems and many many more. Stacks were first introduced in 1964 by Alan M. Turing and they were gaining popularity ever since.






A stack acts as a first in last out data structure most commonly known as LIFO. In layman terms this means it is a data store where you can insert an element at a time, but you can retrieve these elements back in reverse order. For example, if we insert these integers in order to a stack (Push them) 1,2,3,4,5 we can retrieve (Pull) them in reverse order i.e. 5,4,3,2,1. In other words, a stack act as a pile of books, you can always add books to the top of this book stack, but you can access the most recent that you but in.  If you need to find more, click here.


Stack Methods

Stacks usually poses four methods, these methods are:
  1. Init
  2. Pop
  3. Push
  4. Peak

The "Init" method usually used to instantiate the stack i.e allocate memory to be used in the stack. In strongly typed languages like Golang, it is required to define the type of elements that goes into the stack. In addition to the memory allocations, it is required for the stack to be thread safe, if it is going to run in a multi-threading environment. 


The "Pop" method simply removes the last element of the stack and return it to its caller. Thus achieving the purpose of LIFO.

The "Push" method simply appends an item to the top of the stack, to be retrieved later using the "Pop" method. 

The "Peak" method acts very similarly to the "Pop" method but without actually removing an item from the stack. 

Stack Implementation in Golang

Here goes the interesting stuff. First we create a struct that will represent our stack. This struct will contain a slice that will represent our data, a locking mechanism for safe threading. It's required to keep these struct members private so no one miss with them from outside our package. These Items will be manipulated by our receiver functions only. So our struct will look something like this:


So in order to instantiate this struct and use it, we might provide a method to do that. This method will return a pointer to a stack so the caller can invoke the struct methods on them. The Other Three methods required by a stack to function probably are displayed below. Notice here that we do not allow simulations reads/writes to our data structure.


Testing our Stack

To test our stack, we first insert (Push) the items 0,1,2,3,4 and use the Pull method to retrieve them back. Here is the code snippet:

Happy Generic Stacks :)

Comments

Post a Comment

Popular posts from this blog

Golang Generics Performance Evaluation and Implications

Image
  Generics is the latest upcoming feature in Golang. Introducing high level elegant syntax along with infinite possibilities. If you need an introduction kindly visit our post on Golang generics . Unlike the previous post , This post is more concerned about evaluating the performance of Golang Generics and some future perspectives and implications. Any source code snippets used in this post can be found here . The rest of the post is organized as follows: Introduction to generics Benchmark experiments strategy Benchmark results Implications on Golang future Introduction to generics Generics has been around and used extensively (specially when writing libraries or frameworks) in many programming languages like c++, c#, java. However, generics are known to have some extra computational cost to explicitly typed code. With that in mind, it has been always a good idea to write in generics rather than explicit coding due to its huge advantages in readability, maintainability an...
Read more

Generics In Golang

Image
  Golang is an emerging technology that took the development world by storm. Introducing rapid software development that is consistent, strongly typed, insanely fast performance, and simple concurrency model; that is cheap, easy to learn and debug.  As promised by google on twitter, finally generics are introduced in Golang. This post will introduce the upcoming feature in Golang 1.18 called Generics. I'm going to assume basic familiarity with Golang. The rest of content is organized as follows: What are generics Why Golang? Golang before generics Generics in Golang Install Golang 1.18 Simple stack using generics Implementation in Golang. Kindly note that all code snippets used in this post are available here.  What are generics? Generics are programming concepts that applies to functions, classes, and methods. That allows the usage and declaration of strongly typed software artifacts with complete independence on the type/s of their parameters. This can be achieved in a ...
Read more