Data Structures: 1. Stack

Mar 20, 2022

Introduction #

The stack is one of the simplest data structures and one that is easy to image from every day life. If you have a stack of dishes, you normally add to the top of the stack and when you want to take one off you also take it from the top. This is known as First In First Out, or FIFO. The act of adding a plate is called pushing a new plate onto the stack, removing one is called popping the plate from the stack. A stack has a length - the number of plates in the stack. You also know when the stack is empty - there are no plates left. And that essentially tells you everything you need to know about a stack.

There is one other point to note in the solution. We are using any type instead of a specific type like string or int. This means we don’t have to write different stacks for different types.

Solution #

package main

import "fmt"

type Stack struct {
    stack []any
}

func (s *Stack) IsEmpty() bool {
    return len(s.stack) == 0
}

func (s *Stack) SizeOf() int {
    return len(s.stack)
}

func (s *Stack) Push(v any) {
    s.stack = append(s.stack, v)
}

func (s *Stack) Peek() (v any, err error) {

    if s.IsEmpty() {
        return "", fmt.Errorf("Stack is empty")
    }

    v = s.stack[len(s.stack)-1]

    return v, nil
}

func (s *Stack) Pop() (v any, err error) {

    if s.IsEmpty() {
        return "", fmt.Errorf("Stack is empty")
    }

    v = s.stack[len(s.stack)-1]
    s.stack = s.stack[:len(s.stack)-1]

    return v, nil
}

func main() {
    s := &Stack{
        stack: make([]any, 0),
    }

    fmt.Printf("Size of new stack: %d\n", s.SizeOf())
    fmt.Printf("Stack is empty?: %v\n", s.IsEmpty())
    fmt.Println("Push three items ('One', 'Two', 'Three') onto the stack")

    s.Push("One")
    s.Push("Two")
    s.Push("Three")

    fmt.Printf("Size after pushing three elements: %d\n", s.SizeOf())
    fmt.Printf("Stack is empty?: %v\n", s.IsEmpty())

    if head, err := s.Peek(); err == nil {
        fmt.Printf("Peek: Current head element: %v\n", head)
    }

    fmt.Println("Now pop the three elements")

    if element, err := s.Pop(); err == nil {
        fmt.Printf("Pop: %v\n", element)
    }

    if element, err := s.Pop(); err == nil {
        fmt.Printf("Pop: %v\n", element)
    }

    if element, err := s.Pop(); err == nil {
        fmt.Printf("Pop: %v\n", element)
    }

    fmt.Println("Stack should now be empty, so another pop should not work")

    if _, err := s.Pop(); err != nil {
        fmt.Printf("Pop: %s\n", err)
    }

    fmt.Printf("Size of stack: %d\n", s.SizeOf())
    fmt.Printf("Stack is empty?: %v\n", s.IsEmpty())

    fmt.Println("Now push another three entires onto the stack (1, 2, 3)")

    s.Push(1)
    s.Push(2)
    s.Push(3)

    fmt.Printf("Size after pushing three elements: %d\n", s.SizeOf())
    fmt.Printf("Stack is empty?: %v\n", s.IsEmpty())

    if head, err := s.Peek(); err == nil {
        fmt.Printf("Peek: Current head element: %v\n", head)
    }

    fmt.Println("Now pop the three elements")

    if element, err := s.Pop(); err == nil {
        fmt.Printf("Pop: %v\n", element)
    }

    if element, err := s.Pop(); err == nil {
        fmt.Printf("Pop: %v\n", element)
    }

    if element, err := s.Pop(); err == nil {
        fmt.Printf("Pop: %v\n", element)
    }

    fmt.Println("Stack should now be empty, so another pop should not work")

    if _, err := s.Pop(); err != nil {
        fmt.Printf("Pop: %s\n", err)
    }

    fmt.Printf("Size of stack: %d\n", s.SizeOf())
    fmt.Printf("Stack is empty?: %v\n", s.IsEmpty())
}

Testing #

Size of new stack: 0
Stack is empty?: true
Push three items ('One', 'Two', 'Three') onto the stack
Size after pushing three elements: 3
Stack is empty?: false
Peek: Current head element: Three
Now pop the three elements
Pop: Three
Pop: Two
Pop: One
Stack should now be empty, so another pop should not work
Pop: Stack is empty
Size of stack: 0
Stack is empty?: true
Now push another three entires onto the stack (1, 2, 3)
Size after pushing three elements: 3
Stack is empty?: false
Peek: Current head element: 3
Now pop the three elements
Pop: 3
Pop: 2
Pop: 1
Stack should now be empty, so another pop should not work
Pop: Stack is empty
Size of stack: 0
Stack is empty?: true