A stack on a slice

This theme adds no new Go constructs. You will build small tools from parts you already know: slices, loops, map, methods and errors. The first tool is a stack.

Picture a pile of plates. A clean plate goes on top, and you take one from the top too. The plate put down last leaves first.

The Undo button in an editor works the same way: first it undoes the latest action, then the one before it. Here the program needs the reverse of the order in which values were saved.

Undoing actions

In Go, an ordinary slice gives the reverse order if you add and remove elements only at its end:

package main

import "fmt"

func main() {
    var stack []string
    stack = append(stack, "type", "bold", "delete")
    last := stack[len(stack)-1]
    stack = stack[:len(stack)-1]
    fmt.Println(last, stack) // delete [type bold]
}

Let's walk through it line by line:

1. var stack []string declares an empty pile.
2. append puts three actions on the pile: typing, bold and deleting.
3. last := stack[len(stack)-1] takes the top action, "delete".
4. stack = stack[:len(stack)-1] removes it from the pile.
5. fmt.Println(last, stack) prints delete [type bold].

The top of the stack

A stack is a collection of values that you add to and remove from at one end only. That end is called the top. The value put on last is taken off first.

In a slice, the top is its end, that is, the element stack[len(stack)-1].

This is where the plates picture stops working. You cannot pull the bottom plate out of a real pile, but a slice lets you read any element by its index. What makes a slice a stack is an agreement: the code touches only its end.

Stack operations

Three operations work with a stack on a slice.

Push onto the stack

To push a value onto the stack means to add it with a call to append. The call append(stack, "type", "bold", "delete") adds three values in turn, and the last of them, "delete", ends up on top.

Look at the top

Reading stack[len(stack)-1] only looks at the top and does not change the stack.

Pop off the stack

To pop a value takes two steps:

1. Read the top: stack[len(stack)-1].
2. Shorten the slice with the expression stack[:len(stack)-1].

The end index of the expression is excluded, so the slice loses exactly its last element. No elements are copied, so a pop is equally fast on a stack of any size.

Reverse order

The loop for len(stack) > 0 pops values until the stack is empty. They come out in the reverse of the order in which they were pushed:

words := []string{"one", "two", "three"}
var stack []string
for _, w := range words {
    stack = append(stack, w)
}
var out []string
for len(stack) > 0 {
    top := stack[len(stack)-1]
    stack = stack[:len(stack)-1]
    out = append(out, top)
}
fmt.Println(out) // [three two one]

Let's see what happens here:

1. The first loop pushes the words onto the stack.
2. The second loop pops them one by one and appends them to out.
3. The last word pushed was "three", so it comes out first, and the program prints [three two one].

The element type can be anything: a stack of numbers or runes works the same way.

Where a stack helps

A stack suits tasks where whatever opened last must close first. Two examples:

• nested brackets in an expression—checking brackets with a stack is a common interview task;
• function calls—Go keeps them the same way: the function called last returns first.

Common mistake

A value is popped from an empty stack:

var stack []int
top := stack[len(stack)-1] // ✗
fmt.Println(top)

panic: runtime error: index out of range [-1]

The length of an empty slice is 0, so the index comes out as -1, and the program stops with a panic. You cannot take a plate from an empty pile. Before you read the top, check that len(stack) > 0, as in the loop above.

Key points

• A stack adds and removes values at one end: the value pushed last is popped first.
• On a slice, push is append, the top is stack[len(stack)-1], and pop is reading the top plus stack = stack[:len(stack)-1].
• Popped values come out in reverse order.
• Check len(stack) > 0 before reading the top, or an empty stack causes a panic.