Learn Algorithms & Data Structures with GO | Part 1 | Stacks and Queues

Motivation

Golang is a relatively new programming language, created at Google in 2009. It is a fantastic language for both beginners and experienced programmers. It is a statically typed language (like C++ or Java) with extremely readable syntax ( think Python) and some very special ways of error handling. I want to explore with Golang in this new series. In this tutorial, I have decided to start with some basic data structures, namely Stacks and Queues. You can find the code here.

What Will I Learn?

By the end of this tutorial, you you should be able to:

• Explain what Stacks and Queues are
• Implement them in Go

Requirements

• Install Go on your machine (Go)
• Plain text editor, or a more powerful IDE (I use Goland)
• Very basic knowledge of Go syntax

Difficulty

• This tutorial has a basic level of difficulty.

Tutorial Contents

I will explain what a Stack and a Queue are, and than follow up with the implementation. I have prepared some drawings, made by me, in order to visualize the concepts. For the implementations, I have followed, for the most part, the instructions in found in the book Introduction to Algorithms, by Corman.

Workspace Setup

Install Go on your system. Download the Code and run the main file, or try and write the code while reading this tutorial. I use this errors third party package for error handling, I would strongly encourage you to use it as well. Run go get github.com/pkg/error for installation.

What is a Stack?

A stack is a dynamic set of items where insertion and removal takes place at the same end, usually at the top. Thus, the stack implements a last-in, first-out principle (LIFO). Newer items are at the top of the stack, while older ones are at the bottom.

The Insert operation is called a push and the Delete operation is often referred as pop. These are allusion to physical stacks, such as the spring-loaded stack of plates you would find in some cafeterias. There are plenty of use cases for stacks in computer science. Think for example the back button in your browser. As you navigate from page to page, those are placed on a stack, and when you press the back button, the most recent one is "popped" and than showed to you.

Go Implementation of a Stack

We implement our stack, using an array of integers, an element top, that keeps a record of the index of the last inserted element and size, which is represents a cap for the number of element we can push into the stack. Here is my implementation:

package data_structures

import (
    "github.com/pkg/errors"
)

type Stack struct {
    items []int
    top int
    size int
}
// NewStack initializes the stack data structure with the given size
func NewStack(size int) *Stack {
    return &Stack{make([]int, size), -1, size}
}

func (s *Stack) isEmpty() bool {
    return s.top == -1
}

func (s *Stack) isFull() bool {
    return s.top-1 == s.size
}

func (s *Stack) push(item int) error {
    if s.isFull() {
        return errors.New("Cannot push into a full Stack")
    }
    s.top ++
    s.items[s.top] = item
    return nil
}

func (s *Stack) pop() (int, error) {
    if s.isEmpty() {
        return 0, errors.New("Cannot pop empty stack")
    }
    s.top --
    return s.items[s.top + 1], nil
}

It's very important to implement the stack such that pop and push have both O(1) complexity. When we push a new item, we check to see if the stack is not full. We increment the top index and add our new item at the new index. Conversely, when we pop an element, we first check whether our stack is empty. We subtract 1 from the top index and return the element on top.
I could have implemented a more generic stack, so that we could fill it with generic types, but for the purposes of this tutorial, I believe that type int is ok.

What is a Queue?

A queue is an ordered collection of items, where new elements are inserted on one end, called a rear, or tail and removal happens at the other end, called front, or head. The same principles of a normal queue apply. For example. think of a supermarket queue. When a new customer arrives, he takes his place at the end of the line and the customer at the head gets served. Hence, this data structure operates on a FIFO principle (first in, first out).

Go Implementation of a Queue

For the implementation, we will use an array of fixed size. We keep track of the array limit (cap), array size, and indexes for the head and tail. Again, we must pay attention to the complexity for the queue operations, enqueue and dequeue. They are both O(1). We insert (enqueue) elements at the tail. We increment the index for the tail. Conversely, when we dequeue an item, we look at the head. We return the item located at the head, and increment the head.

package data_structures

import (
    "github.com/pkg/errors"
    "fmt"
)

type Queue struct {
    items []int
    cap int
    length int
    head int
    tail int
}

func NewQueue(cap int) *Queue {
    return &Queue{items:make([]int, cap), cap:cap, length:0, head:0, tail: 0}
}

func (q *Queue) IsEmpty() bool {
    return q.length == 0
}

func (q *Queue) IsFull() bool {
    return q.length == q.cap
}

func (q *Queue) Enqueue(item int) error {
    if q.IsFull()  {
        return errors.New("Queue is already at full capacity")
    }
    q.items[q.tail] = item
    q.tail ++
    q.length ++
    return nil
}

// return the front of the queue, mutating the queue
func (q *Queue) Dequeue() (int, error) {
    if q.IsEmpty() {
        return 0, errors.New("Cannot dequeue an empty queue")
    }
    result := q.items[q.head]
    q.head ++
    q.length --
    return result, nil
}

func (q *Queue) Len() int {
    return q.length
}

// Returns the value at the front, without mutation
func (q *Queue) Poll() int {
    return q.items[q.head]
}

// Returns the oldest value in the queue, without mutation
func (q *Queue) Peek() int {
    return q.items[q.tail]
}

func (q *Queue) Print() {
    for i := q.head; i < q.tail; i++ {
        fmt.Println(q.items[i])
    }
}

Queue Example

Let's try our newly implemented queue. We create a main function and important the queue. We will perform 5 enqueues, with items 10, 11, 12, 13, 14. Than we wil perform 2 dequeue operations and then one enqueue operation, with item 15. Here is a picture for what our queue looks like after each operation:

Here is the implementation:

func main() {
    fmt.Println("hello world")
    q := data_structures.NewQueue(17)

    for i := 10; i < 15; i++ {
        q.Enqueue(i)
    }

    q.Print()

    fmt.Println("********")

    q.Dequeue()
    q.Dequeue()

    q.Print()
    fmt.Println("********")

    q.Enqueue(15)

    q.Print()
    fmt.Println("********")
}

The queue has the expected beheviour. We add items at the tail and dequeue from the head. Of course, we could try more robust implementations, one where we don't use a fixed array, but that is a topic for another day.

Conclusion, what will I learn next time?

I hope you enjoyed this tutorial. I am just getting started with Golang, I am by no means an expert and I look forward to learning with you guys! These data structures may seem trivial, especially to the more experienced programmers out there, but it's always important to go back to the basics, especially when learning a new language. I plan on covering Linked Lists next, so stay tuned!

Sources

• Introduction to Algorithms, Cormen, Leirson, Rivest and Stein, Chapter III, Data Structures
• Geeks for Geeks
• Thumbnail

---

Posted on Utopian.io - Rewarding Open Source Contributors

---