Stacks: Like a Stack of Plates

Welcome! You’ve learned about arrays, slices, strings, and linked lists. Now let’s learn about Stacks - one of the simplest and most useful data structures.

What is a Stack? (Real Life Analogy)

The Cafeteria Plate Stack

Imagine you’re at a cafeteria. There’s a tall stack of clean plates. You can only:

• Take a plate from the top of the stack
• Put a dirty plate back on the top of the stack

You cannot take a plate from the middle or bottom. That’s exactly how a stack works!

Stack Rules:

• Last In, First Out (LIFO): The last thing you put in is the first thing you take out
• Only top access: You can only add/remove from the top
• Like a stack of plates, books, or pancakes

Stack Operations (Like Plate Management)

The Basic Actions

// Our stack will hold integers (like plate numbers)
type Stack struct {
    plates []int  // Using a slice to store our plates
}

1. Push: Add a Plate to the Top

func (s *Stack) Push(plate int) {
    // Add plate to the end of our slice (top of stack)
    s.plates = append(s.plates, plate)
}

// Example: Adding plates to the stack
stack := &Stack{plates: []int{}}

stack.Push(1)  // Stack: [1]
stack.Push(2)  // Stack: [1, 2]
stack.Push(3)  // Stack: [1, 2, 3]

2. Pop: Take a Plate from the Top

func (s *Stack) Pop() (int, bool) {
    // Check if stack is empty
    if len(s.plates) == 0 {
        return 0, false  // No plates left!
    }
    
    // Get the top plate
    topPlate := s.plates[len(s.plates)-1]
    
    // Remove it from stack
    s.plates = s.plates[:len(s.plates)-1]
    
    return topPlate, true
}

// Example: Taking plates from stack
plate, success := stack.Pop()  // Gets 3, Stack now: [1, 2]
plate, success := stack.Pop()  // Gets 2, Stack now: [1]
plate, success := stack.Pop()  // Gets 1, Stack now: []

3. Peek: Look at the Top Plate (Without Taking It)

func (s *Stack) Peek() (int, bool) {
    if len(s.plates) == 0 {
        return 0, false
    }
    
    return s.plates[len(s.plates)-1], true
}

// Example: Checking top plate
topPlate, exists := stack.Peek()  // Sees 3, but doesn't remove it

4. Check if Stack is Empty

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

// Example
if stack.IsEmpty() {
    fmt.Println("No more plates!")
}

5. Count Plates in Stack

func (s *Stack) Size() int {
    return len(s.plates)
}

// Example
count := stack.Size()  // How many plates are stacked

Real Life Example: Browser Back Button

package main

import "fmt"

type BrowserHistory struct {
    pages []string  // Stack of visited pages
}

func NewBrowserHistory() *BrowserHistory {
    return &BrowserHistory{
        pages: []string{},
    }
}

func (bh *BrowserHistory) VisitPage(url string) {
    // Add new page to top of stack
    bh.pages = append(bh.pages, url)
    fmt.Printf("Visited: %s\n", url)
}

func (bh *BrowserHistory) GoBack() string {
    if len(bh.pages) <= 1 {
        return "Can't go back further!"
    }
    
    // Remove current page from top
    currentPage := bh.pages[len(bh.pages)-1]
    bh.pages = bh.pages[:len(bh.pages)-1]
    
    // The new top is now the previous page
    previousPage := bh.pages[len(bh.pages)-1]
    
    fmt.Printf("Went back from %s to %s\n", currentPage, previousPage)
    return previousPage
}

func (bh *BrowserHistory) CurrentPage() string {
    if len(bh.pages) == 0 {
        return "No pages visited"
    }
    return bh.pages[len(bh.pages)-1]
}

func main() {
    browser := NewBrowserHistory()
    
    browser.VisitPage("google.com")
    browser.VisitPage("github.com")
    browser.VisitPage("stackoverflow.com")
    
    fmt.Printf("Current page: %s\n", browser.CurrentPage())
    
    browser.GoBack()  // Back to github.com
    browser.GoBack()  // Back to google.com
}

Output:

Visited: google.com
Visited: github.com
Visited: stackoverflow.com
Current page: stackoverflow.com
Went back from stackoverflow.com to github.com
Went back from github.com to google.com

Real Life Example: Undo Function in Text Editor

package main

import "fmt"

type TextEditor struct {
    text    string
    history []string  // Stack of previous versions
}

func NewTextEditor() *TextEditor {
    return &TextEditor{
        text:    "",
        history: []string{},
    }
}

func (te *TextEditor) Type(text string) {
    // Save current state before changing
    te.history = append(te.history, te.text)
    
    // Add new text
    te.text += text
    fmt.Printf("Typed: '%s' -> Text is now: '%s'\n", text, te.text)
}

func (te *TextEditor) Undo() bool {
    if len(te.history) == 0 {
        fmt.Println("Nothing to undo!")
        return false
    }
    
    // Restore previous version
    te.text = te.history[len(te.history)-1]
    te.history = te.history[:len(te.history)-1]
    
    fmt.Printf("Undid -> Text is now: '%s'\n", te.text)
    return true
}

func main() {
    editor := NewTextEditor()
    
    editor.Type("Hello")
    editor.Type(" World")
    editor.Type("!")
    
    editor.Undo()  // Remove "!"
    editor.Undo()  // Remove " World"
}

Output:

Typed: 'Hello' -> Text is now: 'Hello'
Typed: ' World' -> Text is now: 'Hello World'
Typed: '!' -> Text is now: 'Hello World!'
Undid -> Text is now: 'Hello World'
Undid -> Text is now: 'Hello'

Real Life Example: Function Calls (Call Stack)

Every time you call a function, it gets added to the “call stack”:

package main

import "fmt"

// This demonstrates how function calls work like a stack
func main() {
    fmt.Println("Starting main()")
    first()
    fmt.Println("Back in main()")
}

func first() {
    fmt.Println("  In first()")
    second()
    fmt.Println("  Back in first()")
}

func second() {
    fmt.Println("    In second()")
    third()
    fmt.Println("    Back in second()")
}

func third() {
    fmt.Println("      In third()")
    // deepest point
    fmt.Println("      Back in third()")
}

// Output shows the stack behavior:
// Starting main()
//   In first()
//     In second()
//       In third()
//       Back in third()
//     Back in second()
//   Back in first()
// Back in main()

Advanced Example: Checking Balanced Parentheses

package main

import "fmt"

type Stack struct {
    items []rune  // Using rune for characters
}

func (s *Stack) Push(item rune) {
    s.items = append(s.items, item)
}

func (s *Stack) Pop() (rune, bool) {
    if len(s.items) == 0 {
        return 0, false
    }
    item := s.items[len(s.items)-1]
    s.items = s.items[:len(s.items)-1]
    return item, true
}

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

func isBalanced(code string) bool {
    stack := &Stack{}
    
    for _, char := range code {
        switch char {
        case '(', '{', '[':
            // Opening brackets go on stack
            stack.Push(char)
        case ')', '}', ']':
            // Closing brackets must match top of stack
            if stack.IsEmpty() {
                return false  // No opening bracket to match
            }
            
            top, _ := stack.Pop()
            if !isMatchingPair(top, char) {
                return false  // Wrong type of bracket
            }
        }
    }
    
    return stack.IsEmpty()  // All brackets should be matched
}

func isMatchingPair(open, close rune) bool {
    pairs := map[rune]rune{
        ')': '(',
        '}': '{',
        ']': '[',
    }
    return pairs[close] == open
}

func main() {
    testCases := []string{
        "()",           // balanced
        "()()",         // balanced
        "(())",         // balanced
        "(()",          // not balanced
        "())",          // not balanced
        "{[()]}",       // balanced
        "{[(])}",       // not balanced
    }
    
    for _, test := range testCases {
        balanced := isBalanced(test)
        status := "NOT balanced"
        if balanced {
            status = "balanced"
        }
        fmt.Printf("'%s' is %s\n", test, status)
    }
}

Output:

'()' is balanced
'()()' is balanced
'(())' is balanced
'(()' is NOT balanced
'())' is NOT balanced
'{[()]}' is balanced
'{[(])}' is NOT balanced

Stack Implementation Using Linked List

Sometimes you want to implement a stack using linked lists instead of slices:

type Node struct {
    data int
    next *Node
}

type LinkedStack struct {
    top  *Node
    size int
}

func (ls *LinkedStack) Push(data int) {
    // New node becomes the top
    newNode := &Node{data: data, next: ls.top}
    ls.top = newNode
    ls.size++
}

func (ls *LinkedStack) Pop() (int, bool) {
    if ls.top == nil {
        return 0, false
    }
    
    // Get data from top node
    data := ls.top.data
    
    // Move top to next node
    ls.top = ls.top.next
    ls.size--
    
    return data, true
}

func (ls *LinkedStack) Peek() (int, bool) {
    if ls.top == nil {
        return 0, false
    }
    return ls.top.data, true
}

func (ls *LinkedStack) IsEmpty() bool {
    return ls.top == nil
}

func (ls *LinkedStack) Size() int {
    return ls.size
}

Practice Time!

Exercise 1: Reverse a String Using Stack

Create a function that reverses a string using a stack.

Exercise 2: Calculator with Undo

Create a simple calculator that can:

• Add numbers
• Subtract numbers
• Undo the last operation

Exercise 3: Browser History with Forward

Extend the browser history to support:

• Going forward (after going back)
• Showing history list
• Going to specific page in history

Exercise 4: Valid HTML Tags

Check if HTML tags are properly nested:

• <div><p></p></div> ✓ valid
• <div><p></div></p> ✗ invalid

Exercise 5: Evaluate Simple Math Expression

Evaluate expressions like “3 + 4 * 2” using stacks.

When to Use Stacks

Use stacks when:

• You need LIFO (Last In, First Out) behavior
• You’re doing undo/redo operations
• You’re checking balanced parentheses/brackets
• You’re evaluating expressions
• You’re managing function calls (automatic)

Don’t use stacks when:

• You need to access middle elements frequently
• You need FIFO (First In, First Out) behavior (use queues instead)

What’s Next?

Stacks are simple but powerful! Next, we’ll learn about Queues - which are like stacks but work the opposite way (First In, First Out).

Quick Quiz

1. What’s the difference between a stack and a regular list?
2. What does LIFO mean?
3. Can you access the middle element of a stack directly?
4. Name three real-life examples of stacks.
5. Why do programming languages use stacks for function calls?

Remember: Stacks are like cafeteria plate stacks - you only touch the top plate!