Stacks

Imagine a stack of plates: you add new plates to the top, and when you take a plate, you take it from the top. This simple, intuitive concept is the core of a stack, a fundamental data structure in computer science.

A stack operates on a Last-In, First-Out (LIFO) principle. This means the element that was most recently added to the stack is the first one to be removed. It's essentially a specialized type of queue where operations are restricted to one end.

The two primary operations for a stack are:

• Push: Adding an element to the top of the stack.
• Pop: Removing the top element from the stack.

In Go, we can implement a stack using various underlying data structures. Let's explore the common approaches.

---

Basic Stack Implementation with a Go Slice

A Go slice provides a convenient way to implement a basic stack. We'll define a Stack struct with a slice to hold its Data, and then add Push and Pop methods.

package main

import (
	"errors" // For returning errors in Pop
	"fmt"    // For printing examples
)

// Stack represents a basic LIFO stack using a slice of integers.
type Stack struct {
	Data []int
}

// Push adds an integer to the top of the stack.
func (s *Stack) Push(v int) {
	s.Data = append(s.Data, v) // Append adds to the end of the slice, which we treat as the 'top'
}

// Pop retrieves and removes the top element from the stack.
// It returns an error if the stack is empty.
func (s *Stack) Pop() (int, error) {
	if s.IsEmpty() { // Check if the stack is empty before trying to pop
		return 0, errors.New("Stack is empty")
	}
	lastIndex := len(s.Data) - 1 // Get the index of the last element
	last := s.Data[lastIndex]    // Get the last element
	s.Data = s.Data[:lastIndex]  // Slice the array to remove the last element
	return last, nil             // Return the element and no error
}

// IsEmpty checks if the stack contains any elements.
func (s *Stack) IsEmpty() bool {
	return len(s.Data) == 0
}

// Peek returns the top element without removing it.
func (s *Stack) Peek() (int, error) {
	if s.IsEmpty() {
		return 0, errors.New("Stack is empty")
	}
	return s.Data[len(s.Data)-1], nil
}

func main() {
	myStack := Stack{} // Initialize an empty stack

	fmt.Println("Is stack empty?", myStack.IsEmpty()) // Output: Is stack empty? true

	fmt.Println("Pushing 10, 20, 30 onto the stack...")
	myStack.Push(10)
	myStack.Push(20)
	myStack.Push(30)

	fmt.Println("Is stack empty?", myStack.IsEmpty()) // Output: Is stack empty? false

	top, err := myStack.Peek()
	fmt.Printf("Top element (peek): %d, Error: %v\n", top, err) // Output: Top element (peek): 30, Error: <nil>

	val, err := myStack.Pop()
	fmt.Printf("Popped: %d, Error: %v\n", val, err) // Output: Popped: 30, Error: <nil>

	val, err = myStack.Pop()
	fmt.Printf("Popped: %d, Error: %v\n", val, err) // Output: Popped: 20, Error: <nil>

	val, err = myStack.Pop()
	fmt.Printf("Popped: %d, Error: %v\n", val, err) // Output: Popped: 10, Error: <nil>

	val, err = myStack.Pop()
	fmt.Printf("Popped: %d, Error: %v\n", val, err) // Output: Popped: 0, Error: Stack is empty
}

Note on Efficiency: While simple, the slice-based Pop operation s.Data = s.Data[:lastIndex] is efficient because Go's slices are backed by arrays. Removing from the end (which we treat as the top of the stack) is an $O(1)$ operation, avoiding costly reallocations and copies that would occur if we were removing from the beginning of a slice (as in a FIFO queue implemented with Data = Data[1:]).

---

Size-Limited Stack

Just like queues, stacks can also have a predefined maximum capacity. We can extend our Stack implementation by adding a MaxSize field and preventing Push operations when the stack is full.

package main

import (
	"errors"
	"fmt"
)

type Stack struct {
	Data    []int
	MaxSize int // Add the MaxSize attribute
}

// Push adds an integer to the top of the stack, checking for capacity.
func (s *Stack) Push(v int) error {
	if s.MaxSize != 0 && len(s.Data) >= s.MaxSize { // Check if the stack is full
		return errors.New("Stack is full")
	}
	s.Data = append(s.Data, v)
	return nil // Return nil on success
}

// Pop retrieves and removes the top element from the stack. (Same as before)
func (s *Stack) Pop() (int, error) {
	if s.IsEmpty() {
		return 0, errors.New("Stack is empty")
	}
	lastIndex := len(s.Data) - 1
	last := s.Data[lastIndex]
	s.Data = s.Data[:lastIndex]
	return last, nil
}

// IsEmpty checks if the stack contains any elements. (Same as before)
func (s *Stack) IsEmpty() bool {
	return len(s.Data) == 0
}

// IsFull checks if the stack has reached its maximum capacity.
func (s *Stack) IsFull() bool {
	return s.MaxSize != 0 && len(s.Data) == s.MaxSize
}

func main() {
	limitedStack := Stack{MaxSize: 2} // Initialize a stack with max size 2

	err := limitedStack.Push(100)
	fmt.Printf("Push 100: %v\n", err) // Output: Push 100: <nil>

	err = limitedStack.Push(200)
	fmt.Printf("Push 200: %v\n", err) // Output: Push 200: <nil>

	fmt.Println("Is stack full?", limitedStack.IsFull()) // Output: Is stack full? true

	err = limitedStack.Push(300)
	fmt.Printf("Push 300: %v\n", err) // Output: Push 300: Stack is full

	val, _ := limitedStack.Pop()
	fmt.Printf("Popped: %d\n", val) // Output: Popped: 200

	err = limitedStack.Push(400)
	fmt.Printf("Push 400: %v\n", err) // Output: Push 400: <nil>
}

---

More Efficient with a Linked List

While slices are efficient for stack operations in Go, a singly linked list offers another classic and often more conceptual way to implement a stack, especially when Push and Pop need to be $O(1)$ operations with strict guarantees on memory usage per element. We treat the Head of the linked list as the "top" of our stack.

Let's assume we have a simple generic Node and List structure (similar to what might be in a "Linked Lists" article):

// Node and List structs for a generic singly linked list
// (You'd define these once, perhaps in a separate package,
// or inline them for a self-contained example)
type Node[T any] struct {
	Value T
	Next  *Node[T]
}

type List[T any] struct {
	Head *Node[T]
	// Tail *Node[T] // Not strictly needed for a stack, as we only operate on the head
	Size int // Keep track of size for IsEmpty and optional IsFull
}

Now, let's implement our stack using this linked list:

package main

import (
	"errors"
	"fmt"
)

// Assuming Node and List structs are defined as above,
// or imported from a package like "mydata/linkedlist".

// Stack now uses a singly linked list for its Data storage.
type Stack[T any] struct { // Make the Stack itself generic
	Data List[T]
	// MaxSize int // Can still add MaxSize logic if needed
}

// Push adds an element to the top of the stack (prepends to the linked list).
func (s *Stack[T]) Push(v T) {
	newNode := &Node[T]{Value: v, Next: s.Data.Head} // New node points to current head
	s.Data.Head = newNode                           // New node becomes the new head
	s.Data.Size++                                   // Increment size
}

// Pop retrieves and removes the element from the top of the stack (removes head of linked list).
func (s *Stack[T]) Pop() (T, error) {
	var zeroValue T // Get the zero value for type T
	if s.IsEmpty() {
		return zeroValue, errors.New("Stack is empty")
	}

	val := s.Data.Head.Value      // Get the value from the head node
	s.Data.Head = s.Data.Head.Next // Move head to the next node
	s.Data.Size--                 // Decrement size
	return val, nil
}

// IsEmpty checks if the stack is empty.
func (s *Stack[T]) IsEmpty() bool {
	return s.Data.Head == nil // Or return s.Data.Size == 0
}

// Peek returns the top element without removing it.
func (s *Stack[T]) Peek() (T, error) {
	var zeroValue T
	if s.IsEmpty() {
		return zeroValue, errors.New("Stack is empty")
	}
	return s.Data.Head.Value, nil
}

func main() {
	// Example with a stack of strings
	stringStack := Stack[string]{}
	fmt.Println("Is string stack empty?", stringStack.IsEmpty()) // Output: Is string stack empty? true

	stringStack.Push("Task A")
	stringStack.Push("Task B")
	stringStack.Push("Task C")

	fmt.Println("Is string stack empty?", stringStack.IsEmpty()) // Output: Is string stack empty? false

	topTask, _ := stringStack.Peek()
	fmt.Printf("Top task (peek): %s\n", topTask) // Output: Top task (peek): Task C

	task, err := stringStack.Pop()
	fmt.Printf("Popped: %s, Error: %v\n", task, err) // Output: Popped: Task C, Error: <nil>

	task, err = stringStack.Pop()
	fmt.Printf("Popped: %s, Error: %v\n", task, err) // Output: Popped: Task B, Error: <nil>

	task, err = stringStack.Pop()
	fmt.Printf("Popped: %s, Error: %v\n", task, err) // Output: Popped: Task A, Error: <nil>

	task, err = stringStack.Pop()
	fmt.Printf("Popped: %s, Error: %v\n", task, err) // Output: Popped: , Error: Stack is empty
}

This linked-list based implementation provides guaranteed $O(1)$ performance for Push and Pop operations, regardless of stack size, because it only involves modifying pointers at the head of the list.

---

Key Use Cases for Stacks

Stacks are a fundamental concept with wide-ranging applications in computer science:

• Function Call Stack (Program Execution): Whenever you execute a program, function calls are managed using a stack. When a function is called, its execution context (local variables, return address) is "pushed" onto the call stack. When the function finishes, its context is "popped" off, and control returns to the previous function. This is why you see a stack trace when an error occurs – it's a snapshot of the functions currently on the call stack.

• Depth-First Search (DFS): DFS is a graph traversal algorithm that systematically explores as far as possible along each branch before backtracking. It naturally uses a stack (either explicitly or implicitly through recursion, which relies on the call stack) to keep track of the nodes to visit next.

• Undo/Redo Functionality: Many applications (text editors, drawing tools) implement undo/redo by storing operations on a stack. "Undo" pops an operation, and "Redo" can push it onto another stack.

• Expression Evaluation: Stacks are crucial for evaluating mathematical expressions (e.g., converting infix to postfix notation and then evaluating postfix expressions).

• Browser History: The "back" button in a web browser can be modeled using a stack, where each visited page is pushed onto the stack. Clicking "back" pops the current page and navigates to the previous one.

• Balancing Symbols (Parentheses, Brackets): Compilers and parsers use stacks to check if parentheses, braces, and brackets are correctly matched and nested in code.

Understanding stacks is vital for grasping the underlying mechanisms of many algorithms and system processes. They are a powerful tool for managing data where the order of insertion and removal is critical.