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

in #utopian-io6 years ago (edited)

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.

GO.png

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.

Stack (2).jpg

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

Queue (3).png

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:

QueueImpl (1).png

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



Posted on Utopian.io - Rewarding Open Source Contributors

Sort:  

Thank you for the contribution. It has been approved.

You can contact us on Discord.
[utopian-moderator]

Hey @sakibarifin, I just gave you a tip for your hard work on moderation. Upvote this comment to support the utopian moderators and increase your future rewards!

Thank you, that was very fast!

went to a few Go meetings in our local area, and it was fun meeting with others excited about Go. But that was like two years ago, now sorta obsessed with the idea of Swift. REALLY cool for beginners too, they are pushing it into schools and normally that'd be creepy but it actually makes sense due to their "Playgrounds" setup. Was always thinking this is how a language should be, and Apple kinda combined the best of two differing types of programming languages into one. have you explored Swift at all?

Nope, I have not tried Swift, at all. I have heard great things about it though, and with a company as powerful as Apple behind it, I am sure it's going to have a bright future. My recent experiments have been with Go and Typescript. Typescript for some front-end web work.

great content! and thanks again for following!

@prometheus21, No matter approved or not, I upvote and support you.

This post has received a 2.95 % upvote from @speedvoter thanks to: @prometheus21.

Can you add a closing bracket in the second line of requirements section please?

(I use Goland

Your Post Has Been Featured on @Resteemable!
Feature any Steemit post using resteemit.com!
How It Works:
1. Take Any Steemit URL
2. Erase https://
3. Type re
Get Featured Instantly � Featured Posts are voted every 2.4hrs
Join the Curation Team Here | Vote Resteemable for Witness

You got a 0.81% upvote from @postpromoter courtesy of @prometheus21!

Want to promote your posts too? Check out the Steem Bot Tracker website for more info. If you would like to support the development of @postpromoter and the bot tracker please vote for @yabapmatt for witness!

Hey @prometheus21 I am @utopian-io. I have just upvoted you!

Achievements

  • You have less than 500 followers. Just gave you a gift to help you succeed!
  • Seems like you contribute quite often. AMAZING!

Suggestions

  • Contribute more often to get higher and higher rewards. I wish to see you often!
  • Work on your followers to increase the votes/rewards. I follow what humans do and my vote is mainly based on that. Good luck!

Get Noticed!

  • Did you know project owners can manually vote with their own voting power or by voting power delegated to their projects? Ask the project owner to review your contributions!

Community-Driven Witness!

I am the first and only Steem Community-Driven Witness. Participate on Discord. Lets GROW TOGETHER!

mooncryption-utopian-witness-gif

Up-vote this comment to grow my power and help Open Source contributions like this one. Want to chat? Join me on Discord https://discord.gg/Pc8HG9x

Coin Marketplace

STEEM 0.36
TRX 0.12
JST 0.039
BTC 69965.85
ETH 3540.49
USDT 1.00
SBD 4.71