Stack Implementation (Using `Vec`)

A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. In Rust, the Vec<T> type is a natural and efficient choice for implementing a stack because it already supports pushing and popping elements from the end in constant time.

This section demonstrates a clean stack implementation using Vec.

Why Use Vec for a Stack?

Rust’s Vec is ideal for stack behavior because:

• push adds an element to the end
• pop removes the last element
• Both operations run in O(1) amortized time
• Memory management is handled safely by Rust

Stack Operations

A stack typically supports the following operations:

• Push - add an element to the top
• Pop - remove the top element
• Peek - view the top element
• Is Empty - check if the stack has no elements

Rust Implementation

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

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

    pub fn push(&mut self, value: T) {
        self.data.push(value);
    }

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

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

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

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

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn stack_works() {
        let mut stack = Stack::new();

        assert!(stack.is_empty());

        stack.push(1);
        stack.push(2);
        stack.push(3);

        assert_eq!(stack.peek(), Some(&3));
        assert_eq!(stack.pop(), Some(3));
        assert_eq!(stack.pop(), Some(2));
        assert_eq!(stack.pop(), Some(1));
        assert!(stack.is_empty());
    }
}

Example Usage

fn main() {
    let mut stack = Stack::new();

    stack.push(10);
    stack.push(20);
    stack.push(30);

    println!("Top: {:?}", stack.peek()); // Some(30)

    while let Some(value) = stack.pop() {
        println!("Popped: {}", value);
    }
}

Output:

Top: Some(30)
Popped: 30
Popped: 20
Popped: 10

Time and Space Complexity

Time Complexity

Space Complexity

Advantages of Vec-Based Stack

• Simple and idiomatic
• Fast in practice
• Safe memory handling
• Minimal code

Limitations

• Stack size limited by available memory
• Not thread-safe by default (can be wrapped if needed)

Summary

• Vec provides a clean stack abstraction
• Push/pop naturally map to stack behavior
• Efficient and safe in Rust
• Preferred choice unless special constraints exist

Playground Links

Rust - Stack Implementation (Using Vec)