Stack Data Structure in Rust

About This Module

This module introduces the stack data structure, a fundamental Last-In-First-Out (LIFO) container. Students will learn about stack operations, computational complexity, and multiple implementation strategies using both linked lists and vectors. The module explores the trade-offs between different implementations and demonstrates practical applications of stacks in programming and data science.

Prework

Before this lecture, please read:

Pre-lecture Reflections

  1. What are some real-world examples where LIFO behavior is useful?
  2. How might stack implementation affect performance in different scenarios?
  3. What are the memory layout differences between stack implementations using vectors vs. linked lists?

Learning Objectives

By the end of this lecture, you should be able to:

  • Understand the LIFO principle and stack operations
  • Implement stacks using different underlying data structures
  • Analyze the computational complexity of stack operations
  • Compare performance characteristics of vector-based vs. linked list-based stacks
  • Choose appropriate stack implementations based on use case requirements

Stacks

  • A Stack is a container of objects that are inserted and removed according the LIFO (Last In First Out) principle
  • Insertions are known as "Push" operations while removals are known as "Pop" operations

Universal Stack Operations

Stack operations would be along the lines of:

  • push(object): Insert object onto top of stack. Input: object, Output: none
  • pop(): Remove top object from stack and return it. Input: none, Output: object
  • size(): Number of objects in stack
  • isEmpty(): Return boolean indicated if stack is empty
  • top() or peek(): Return a reference to top object in the stack without removing it

Question: Which Rust data structure could we use to implement a stack?

Computational complexity of Stack operations

Assume we are using a singly (or doubly) linked list

  • Push: O(1)
  • Pop: O(1)
  • Size: O(1) (keep an auxiliary counter)
  • isEmpty: O(1)
  • top: O(1)

Using Vectors to implement a stack

  • Implementing a stack using a vector is straightforward.
  • We can build on Vec<T> methods.
#![allow(unused)]
fn main() {
#[derive(Debug)]
pub struct Stack<T> {
    v: Vec<T>,
}

impl <T> Stack<T> {
    pub fn new() -> Self {
        Stack {v : Vec::new() }
        
    }
    pub fn push(&mut self, obj:T) {
        self.v.push(obj)
    }
     
    pub fn pop(&mut self) -> Option<T> {
        return self.v.pop();
    }
    
    pub fn size(&mut self) -> usize {
        return self.v.len();
    }
    
    pub fn isEmpty(&mut self) -> bool {
        return self.v.len() == 0;
    }
    
    pub fn top(&mut self) -> Option<&T> {
        return self.v.last()
    }
}
}

Using our stack implementation

Now let's use it!

#[derive(Debug)]
pub struct Stack<T> {
    v: Vec<T>,
}

impl <T> Stack<T> {
    pub fn new() -> Self {
        Stack {v : Vec::new() }
        
    }
    pub fn push(&mut self, obj:T) {
        self.v.push(obj)
    }
     
    pub fn pop(&mut self) -> Option<T> {
        return self.v.pop();
    }
    
    pub fn size(&mut self) -> usize {
        return self.v.len();
    }
    
    pub fn isEmpty(&mut self) -> bool {
        return self.v.len() == 0;
    }
    
    pub fn top(&mut self) -> Option<&T> {
        return self.v.last()
    }
}

fn main() {
    let mut s: Stack<i32> = Stack::new();

    println!("Pushing 13, 11, and 9\n");
    s.push(13);
    s.push(11);
    s.push(9);

    println!("size: {}", s.size());
    println!("isEmpty: {}", s.isEmpty());

    println!("\ntop: {:?}", s.top());
    println!("pop: {:?}", s.pop());
    println!("size: {}", s.size());

    println!("\ntop: {:?}", s.top());
    println!("pop: {:?}", s.pop());
    println!("size: {}", s.size());

    println!("\ntop: {:?}", s.top());
    println!("pop: {:?}", s.pop());
    println!("size: {}", s.size());
    println!("isEmpty: {}", s.isEmpty());

    println!("\ntop: {:?}", s.top());
    println!("pop: {:?}", s.pop());
}

Which implementation is better: LinkedList or Vec?

  • Computation complexity is the same for both (at least on average)
  • The Vector implementation has the occasional long operation which may be undesirable in a real-time system

BUT the most important consideration is spatial locality of reference.

  • In a vector objects will be contiguous in memory so accessing one will fetch its neighbors into the cache for faster access
  • In the linked list version each object is allocated independently so their placement in memory is unclear

In-Class Poll

True or False:

  1. In a stack, the most recently added element is the first one to be removed.

    • True ✓ (This is the definition of LIFO - Last In First Out)

  2. The pop() operation on a stack has O(n) time complexity when using a singly linked list implementation.

    • False ✗ (pop() is O(1) for both linked list and vector implementations)

  3. A vector-based stack implementation may occasionally have long operations due to resizing.

    • True ✓ (When the vector needs to grow, it must allocate new memory and copy elements)

  4. The top() or peek() operation removes the top element from the stack.

    • False ✗ (top/peek only returns a reference without removing the element; pop removes it)

  5. Vector-based stacks generally have better spatial locality of reference than linked list-based stacks.

    • True ✓ (Vector elements are contiguous in memory, improving cache performance)

Recap

  • Stacks are a fundamental data structure
  • They are implemented using a vector or a linked list
  • They are a Last-In-First-Out (LIFO) data structure