Go – Using a Slice as a Stack

Many programming languages such as Java and Python come with a very large set of features and standard library. While Go does come with an excellent standard library, it is deliberately smaller. On of the primary purposes of Go is to make it easier to learn, and this is achieved by making the language small and compact. The standard library has some great features such as the in-built production ready webserver, but on a more fundamental level, where are the data structures stacks and queues?

I’ve heard Go described as ‘a programmer’s language’ i.e. it’s for people who already know how to code. Given its origins and influence from C++, it may well not be the best first language to learn for a complete novice (for that maybe try Python or Java and then move onto Go).

There are 3rd part libraries for stacks and queues, but it’s quite easy to implement the behaviour using the in-built Slice. For those with a Java background, a slice in Go is like an ArrayList. You can dynamically add items and remove items from the array. To learn more check out the official documentation, Go Slices: usage and internals.

Stack and Queue data structures can be implemented using a backing array, so using a slice for this in Go fits nicely. The other way to implement would be to use a linked list, I may cover this in a future post.

To keep this clear (and stick to Single Responsibility ;)), I will look at a stack implementation and defer the queue for another post.

Stack (LIFO)

A quick recap: Think of a stack of dinner plates (or a stack of pancakes), the last plate added to the stack becomes the first plate to be removed. Therefore its LIFO – Last In First Out.

Common Operations

• Push – Add an item to the stack
• Pop – Remove the next item from the stack
• Peek – View the next item from the stack, but leave it there

In the code examples below I am just looking at the core logic to push and pop.

Push

func main() {
	// Stack LIFO
	var stack[]int
	
	// to push items onto the stack, simply append items to the slice
	stack = append(stack, 1)
	stack = append(stack, 2)
	stack = append(stack, 3)
}

Items are add to the slice using Go’s built in append function. This simply appends each element to the end of the array.

Pop

func main() {
    // Code will pop each item off the stack and print to screen
    // to pop (remove) the item, remove the last element from the slice
    for len(stack) > 0 {
        // find the index of the last item in the array
        i := len(stack) - 1
		
        fmt.Println(stack[i])
                
        // pop the item off the stack
        // by reassigning the slice minus the last element
	stack = stack[:i]
    }
}

For a stack, items must be removed in reverse order, Last In First Out, so as we append to the end of the list for a push, to pop an item off the stack, it must be removed from the end of the array.

To do this, check the slice has at least one element, as Go will panic if trying to access an element out of bounds. Use the len function to find the last element (len – 1). Storing this index in I (or use directly) allows direct access to the element in the slice.

This takes care of accessing the element (effectively, this is a peek), so to remove or pop the element of the stack, the stack is reassigned from 0 to the index i (excluding the last element)

Thats all for this one, queues next time.