In this tutorial, we will explore the fundamentals of using and working with a stack in the Go programming language.
What Is a Stack?
Let us start at the basics and explore what is a stack. In simple terms, a stack is a linear data structure that is comprised of a collection of elements.
There are two main operations involved in a stack structure:
- Push – This operation adds an element at the top of the stack.
- Pop – This operation removes and returns the top element from the stack.
There are some operations that are supported by a stack such as element peeking without popping the element, size determination, and more.
Stacks follow the Last-In-First-Out (LIFO) principle which means that the last item that is pushed onto the stack is the first one to be popped off.
Golang Stack Structure
In Go, we use stacks using the stack structures. There are two main data types that we can use to implement a stack in Go. These include the following:
- Slice – Using a slice as the underlying data structure.
- Linked List – Implementing a stack with a linked list.
Method 1: Using a Slice as a Stack
The simplest way of implementing a stack in Go is to use a slice. This involves starting out with an empty slice and adding the “push” and “pop” properties of stack.
An example code is as follows:
import "fmt"
func main() {
var stack []int
stack = append(stack, 1)
stack = append(stack, 2)
stack = append(stack, 3)
top := stack[len(stack)-1]
stack = stack[:len(stack)-1]
fmt.Println("Popped:", top)
}
In the given example, we start by creating an empty stack using a Go slice.
We then push the elements on to the stack using the “append” methods. Finally, we can pop the elements from the stack using the negative based indexing.
Method 2: Using a Linked List as Stack
We can also implement a stack using a linked list of nodes. We can then implement both “push” and “pop” methods that allow us to add and remove the elements from the stack.
Take a look at the following implementation:
import (
"fmt"
)
// Node in linked list
type Node struct {
data int
next *Node
}
// Stack as linked list
type Stack struct {
top *Node
}
// add an element to the top of the stack
func (s *Stack) Push(value int) {
newNode := &Node{data: value, next: s.top}
s.top = newNode
}
// remove and return the top element from the stack
func (s *Stack) Pop() (int, error) {
if s.top == nil {
return 0, fmt.Errorf("stack is empty")
}
value := s.top.data
s.top = s.top.next
return value, nil
}
// return the top element without removing it (peek)
func (s *Stack) Peek() (int, error) {
if s.top == nil {
return 0, fmt.Errorf("stack is empty")
}
return s.top.data, nil
}
// check if the stack is empty
func (s *Stack) IsEmpty() bool {
return s.top == nil
}
// return the number of elements in the stack
func (s *Stack) Size() int {
size := 0
current := s.top
for current != nil {
size++
current = current.next
}
return size
}
func main() {
stack := Stack{}
// Push elements onto the stack
stack.Push(1)
stack.Push(2)
stack.Push(3)
// Pop elements from the stack
popped, _ := stack.Pop()
fmt.Println("Popped:", popped)
}
The given code shows a complete implementation of a stack using a linked list. This includes some of the most common features of stack such as push, pop, peek, size check, empty check, and more.
Conclusion
In this tutorial, we learned about one of the most important data structures in computer science which is known as stack. We also learned how to implement a stack using a Go slice and linked list.
