Using stack in Go

The stack is a basic structure of computer science. You may not even have encountered stacks, but we can tell you that all computers, smartphones, watches, and other gadgets use stacks! Today you see how the stack works; how to create a stack with Golang; and how to use stacks to create other important data structures in computer science.

Before we start

Today we will create a Golang module. It helps us separate code into files. Let's take a few preparatory steps. Create a folder for today's topic. Go to a folder, and create a Go module:

go mod init CommonStack

Create 3 files (main.go, stack.go and queue.go). You can do it in your common way or use console commands:

# Linux & MacOS     | Windows Powershell
# ------------------+---------------------
$ touch main.go     | > ni main.go 
$ touch stack.go    | > ni stack.go
$ touch queue.go    | > ni queue.go

A folder structure must look like this:

$ tree
.
├── go.mod
├── main.go
├── queue.go
└── stack.go

0 directories, 4 files

Add a line to each file: package main.

// main.go
package main

// stack.go
package main

// queue.go
package main

Simple stack structure

Now, let's remember which structure is called a stack. A stack is a structure that has a special order of access to elements: we work only with the end of the structure. We can add a new element to the end or get the last element. Recall that the order is called LIFO (Last In, First Out).

Golang has no special types for the stack, but we can get another structure and try to use it like a stack. Which structure is most similar? Of course, it's a slice. It will be a slice of positive integers (within the topic, we will consider negative numbers as a kind of error). What is missing in the slice so that we can use it as a stack? The special order is represented by two methods:

• a method to add an element to the end of the slice (Push);

• a method to get and remove an element from the slice (Pop).

Both operations have an effect on the slice size: the Push operation is to increase the size, the Pop is to reduce.

Open the stack.go file. Now we create a new struct Stack with only one parameter — storage (a []int slice) and two methods. Both methods work with a storage variable.

The Push method is pretty simple to create, we just get a Golang built-in function append. The Pop method is complex and consists of two actions: removing an element from a slice and returning its value. And, of course, we will not forget to check the size of the slice before removing it (we cannot return an element from an empty slice).

// stack.go
package main

import "errors"

type Stack struct {
    storage []int
}

func (s *Stack) Push(value int) {
    s.storage = append(s.storage, value)
}

func (s *Stack) Pop() (int, error) {
    last := len(s.storage) - 1
    if last <= -1 { // check the size
        return 0, errors.New("Stack is empty") // and return error
    }

    value := s.storage[last]     // save the value
    s.storage = s.storage[:last] // remove the last element

    return value, nil // return saved value and nil error
}

Now, we move to the main.go file and create a new stack structure.

// main.go
package main

import "fmt"

func main() {
    var myStack Stack

    myStack.Push(1)            // [1]
    myStack.Push(2)            // [1 2]
    popped, _ := myStack.Pop() // [1]
    myStack.Push(3)            // [1 3]

    fmt.Println(popped)        // 2
    fmt.Println(myStack.Pop()) // [1]   3 <nil>
    fmt.Println(myStack.Pop()) // []    1 <nil>
}

To run this code, just use the command below:

go run .

Pay attention to the first input value — 1. Regardless of future operations on the Stack structure, the 1 value is first in and last out (only when the last value remains in the stack storage).

Queue

The queue is working by the FIFO principle (First In, First Out):

The Push function will be the same in the queue, but the Pop function works in another way. Let's imagine the slice like a queue. The Push function will append an element to the end of the slice. But, when you want to Pop the element, you need to get the first element to remove and return it. When you remove the first element, all others must be shifted to the empty space (to reduce a slice size). Or, you can use the pointer to the first element (in this case, the size of a slice will always grow), and when you Pop the element, you just increase the pointer value.

But, we get another way (the topic is about a stack). We use stacks to create a queue. The Queue structure itself will not have a storage variable, but will include two stacks: input and output. The Push on the input stack will be used like a Push of the Queue, and the Pop of output, like a Pop of Queue. But where are the remaining (a Pop of input and a Push of output) operations? They are responsible for the work of the Queue. Let's see what happens when we Pop the Queue:

• if the output stack is not empty, we just Pop it;

• if the output stack is empty:

  • we Pop all elements from the input stack to the output stack;

  • and only then we Pop the output.

Let's get a code:

// queue.go
package main

import "errors"

type Queue struct {
    input  Stack
    output Stack
}

func (q *Queue) Push(value int) {
    q.input.Push(value)
}

func (q *Queue) Pop() (int, error) {
    outputVal, outputErr := q.output.Pop()
    if outputErr == nil { // if output stack is not empty
        return outputVal, nil // just return value
    }

    inputVal, inputErr := q.input.Pop()
    if inputErr != nil { // if input stack is empty
        return 0, errors.New("Queue is empty") // return the error
    }

    // if the output stack is empty but the input is not empty
    for inputErr == nil { // while input stack not empty...
        q.output.Push(inputVal)            // rearrange input to output
        inputVal, inputErr = q.input.Pop() // and read again
    }

    return q.output.Pop() // and Pop the output
}

And the main.go file:

// main.go
package main

import "fmt"

func main() {
    var myQueue Queue

    myQueue.Push(1)            // [1]   []
    myQueue.Push(2)            // [1 2] []
    popped, _ := myQueue.Pop() // []    [2]
    myQueue.Push(3)            // [3]   [2]
    myQueue.Push(4)            // [3 4] [2]

    fmt.Println(popped)        //            1
    fmt.Println(myQueue.Pop()) // [3 4] []   2 <nil>
    fmt.Println(myQueue.Pop()) // []    [4]  3 <nil>
    fmt.Println(myQueue.Pop()) // []    []   4 <nil>
}

Now we can run the code. Comments are a display of the values of the input and output stack storages (the third value in the comment is the output of the Pop function). The order of output is the same as the input. The queue works!

Conclusion

In this topic, you learned how to implement one of the most common data structures in Go. An interesting detail is that you use a stack every time you work with your computer when you use the undo command (Ctrl+Z or ⌘+Z). Every program keeps a stack of operations, and when you cancel the last operation via the undo command, the program just pops the operation from the stack. As a programmer, you have used stacks when writing recursive algorithms (of course, not direct, but the executor creates a stack of recursive calls). And of course, stacks are used to create other useful structures (like a queue) of the digital world. Let's go back to the main points of the topic:

• the stack is a structure with LIFO-order to elements;

• the common stack structure contains storage and two operations: Push and Pop;

• the stack works only with the last element of the storage;

• the queue is a structure with FIFO-order to elements;

• the queue can be implemented with stacks.