Stacks

Stacks are one of the most intuitive data structures. Think of a stack of plates: you add new plates on top, and you remove plates from the top. This Last-In-First-Out (LIFO) behavior is the foundation of the stack data structure.

What is a Stack?

A stack is a linear data structure that follows the LIFO (Last In, First Out) principle. The last element added is the first one removed.

Stack Operations:

   push(40)        pop()
      ↓              ↑
    +----+        +----+
    | 40 | ← top  |    | (40 removed)
    +----+        +----+
    | 30 |        | 30 | ← new top
    +----+        +----+
    | 20 |        | 20 |
    +----+        +----+
    | 10 |        | 10 |
    +----+        +----+

Core Operations

A stack supports these fundamental operations:

| Operation | Description | Time Complexity | |-----------|-------------|-----------------| | push(item) | Add item to top | O(1) | | pop() | Remove and return top item | O(1) | | peek() / top() | Return top item without removing | O(1) | | isEmpty() | Check if stack is empty | O(1) | | size() | Return number of elements | O(1) |

Implementation Using Dynamic Array

The simplest implementation uses a dynamic array:

pub struct Stack<T> {
    items: Vec<T>,
}

impl<T> Stack<T> {
    pub fn new() -> Self {
        Self { items: Vec::new() }
    }

    pub fn push(&mut self, item: T) {
        self.items.push(item);
    }

    pub fn pop(&mut self) -> Option<T> {
        self.items.pop()
    }

    pub fn peek(&self) -> Option<&T> {
        self.items.last()
    }

    pub fn is_empty(&self) -> bool {
        self.items.is_empty()
    }

    pub fn size(&self) -> usize {
        self.items.len()
    }
}

Implementation Using Linked List

A singly linked list also works well for stacks:

struct Node<T> {
    value: T,
    next: Option<Box<Node<T>>>,
}

pub struct LinkedStack<T> {
    top: Option<Box<Node<T>>>,
    size: usize,
}

impl<T> LinkedStack<T> {
    pub fn new() -> Self {
        Self {
            top: None,
            size: 0,
        }
    }

    pub fn push(&mut self, item: T) {
        let new_node = Box::new(Node {
            value: item,
            next: self.top.take(),
        });
        self.top = Some(new_node);
        self.size += 1;
    }

    pub fn pop(&mut self) -> Option<T> {
        self.top.take().map(|node| {
            self.top = node.next;
            self.size -= 1;
            node.value
        })
    }

    pub fn peek(&self) -> Option<&T> {
        self.top.as_ref().map(|node| &node.value)
    }

    pub fn is_empty(&self) -> bool {
        self.top.is_none()
    }

    pub fn size(&self) -> usize {
        self.size
    }
}

The Call Stack

One of the most important uses of stacks is the call stack that manages function calls in programs:

fn main() {
    let a = func_a(5);
    println!("{}", a);
}

fn func_a(x: i32) -> i32 {
    let b = func_b(x + 1);
    b * 2
}

fn func_b(y: i32) -> i32 {
    y + 10
}

Call stack visualization:

Step 1: main() called
+----------+
|  main()  |
+----------+

Step 2: func_a(5) called
+----------+
| func_a() |
+----------+
|  main()  |
+----------+

Step 3: func_b(6) called
+----------+
| func_b() |
+----------+
| func_a() |
+----------+
|  main()  |
+----------+

Step 4: func_b returns 16
+----------+
| func_a() | ← receives 16
+----------+
|  main()  |
+----------+

Step 5: func_a returns 32
+----------+
|  main()  | ← receives 32
+----------+

Step 6: main completes, stack empty

Classic Applications

1. Balanced Parentheses

Check if parentheses are balanced in an expression:

use std::collections::HashMap;

fn is_balanced(s: &str) -> bool {
    let mut stack = Vec::new();
    let pairs: HashMap<char, char> = [
        (')', '('),
        ('}', '{'),
        (']', '['),
    ].iter().cloned().collect();

    for ch in s.chars() {
        if "({[".contains(ch) {
            stack.push(ch);
        } else if ")}]".contains(ch) {
            if stack.is_empty() || stack.last() != pairs.get(&ch) {
                return false;
            }
            stack.pop();
        }
    }

    stack.is_empty()
}

// Examples
fn main() {
    println!("{}", is_balanced("({[]})")); // true
    println!("{}", is_balanced("([)]"));   // false
    println!("{}", is_balanced("(("));     // false
}

2. Reverse a String

fn reverse_string(s: &str) -> String {
    let mut stack = Vec::new();
    for ch in s.chars() {
        stack.push(ch);
    }

    let mut result = String::new();
    while let Some(ch) = stack.pop() {
        result.push(ch);
    }

    result
}

fn main() {
    println!("{}", reverse_string("hello")); // "olleh"
}

3. Undo Functionality

pub struct TextEditor {
    text: String,
    undo_stack: Vec<String>,
}

impl TextEditor {
    pub fn new() -> Self {
        Self {
            text: String::new(),
            undo_stack: Vec::new(),
        }
    }

    pub fn write(&mut self, s: &str) {
        self.undo_stack.push(self.text.clone()); // Save current state
        self.text.push_str(s);
    }

    pub fn undo(&mut self) {
        if let Some(previous) = self.undo_stack.pop() {
            self.text = previous;
        }
    }

    pub fn get_text(&self) -> &str {
        &self.text
    }
}

fn main() {
    let mut editor = TextEditor::new();
    editor.write("Hello");
    editor.write(" World");
    println!("{}", editor.get_text()); // "Hello World"
    editor.undo();
    println!("{}", editor.get_text()); // "Hello"
}

4. Expression Evaluation

Evaluate postfix (Reverse Polish Notation) expressions:

fn evaluate_postfix(expression: &str) -> i32 {
    let mut stack: Vec<i32> = Vec::new();

    for token in expression.split_whitespace() {
        if let Ok(num) = token.parse::<i32>() {
            stack.push(num);
        } else {
            let b = stack.pop().unwrap();
            let a = stack.pop().unwrap();

            let result = match token {
                "+" => a + b,
                "-" => a - b,
                "*" => a * b,
                "/" => a / b,
                _ => panic!("Unknown operator"),
            };

            stack.push(result);
        }
    }

    stack[0]
}

fn main() {
    // "3 + 4 * 2" in postfix is "3 4 2 * +"
    println!("{}", evaluate_postfix("3 4 2 * +")); // 11
}

Array vs Linked List Implementation

| Aspect | Array-based | Linked List-based | |--------|-------------|-------------------| | Memory | Contiguous, may waste space | Exact size needed | | Cache | Better locality | Worse locality | | Push | Amortized O(1) | Always O(1) | | Pop | O(1) | O(1) | | Random access | O(1) (if needed) | O(n) |

For most applications, array-based stacks are preferred due to:

• Better cache performance
• Simpler implementation
• Dynamic arrays handle resizing efficiently

Common Patterns

Monotonic Stack

A stack where elements are always in sorted order:

fn next_greater_element(arr: &[i32]) -> Vec<i32> {
    let n = arr.len();
    let mut result = vec![-1; n];
    let mut stack: Vec<usize> = Vec::new(); // Stack of indices

    for i in 0..n {
        // Pop elements smaller than current
        while !stack.is_empty() && arr[*stack.last().unwrap()] < arr[i] {
            let idx = stack.pop().unwrap();
            result[idx] = arr[i];
        }
        stack.push(i);
    }

    result
}

fn main() {
    let arr = [4, 5, 2, 10, 8];
    println!("{:?}", next_greater_element(&arr));
    // Output: [5, 10, 10, -1, -1]
}

Min Stack

A stack that supports getting the minimum element in O(1):

pub struct MinStack {
    stack: Vec<i32>,
    min_stack: Vec<i32>,
}

impl MinStack {
    pub fn new() -> Self {
        Self {
            stack: Vec::new(),
            min_stack: Vec::new(),
        }
    }

    pub fn push(&mut self, x: i32) {
        self.stack.push(x);
        if self.min_stack.is_empty() || x <= *self.min_stack.last().unwrap() {
            self.min_stack.push(x);
        }
    }

    pub fn pop(&mut self) -> Option<i32> {
        if let Some(val) = self.stack.pop() {
            if !self.min_stack.is_empty() && val == *self.min_stack.last().unwrap() {
                self.min_stack.pop();
            }
            Some(val)
        } else {
            None
        }
    }

    pub fn top(&self) -> Option<i32> {
        self.stack.last().copied()
    }

    pub fn get_min(&self) -> Option<i32> {
        self.min_stack.last().copied()
    }
}

Key Takeaways

1. Stacks follow LIFO: last in, first out
2. Core operations (push, pop, peek) are all O(1)
3. The call stack manages function invocations
4. Stacks are essential for parsing, undo operations, and backtracking
5. Both arrays and linked lists work well for implementation
6. Monotonic stacks solve many "next greater/smaller element" problems

Stacks may seem simple, but they're fundamental to how computers execute programs and solve a wide variety of algorithmic problems.