Stacks

A Stack represents a collection of elements that follows the Last-In, First-Out (LIFO) principle.

• Push: Add to top ($O(1)$)
• Pop: Remove from top ($O(1)$)
• Peek: Look at top ($O(1)$)

Memory Layout

• Python: Uses Dynamic Arrays (list). Memory is contiguous. Resizing happens automatically.
• Rust: Uses Vec<T>. Memory is strictly owned. Pushing beyond capacity triggers reallocation.

Implementation

from typing import Any, Optional
 
class Stack:
    def __init__(self):
        self.items = []
 
    def push(self, item: Any) -> None:
        self.items.append(item)
 
    def pop(self) -> Optional[Any]:
        if not self.items:
            return None
        return self.items.pop()
 
    def peek(self) -> Optional[Any]:
        if not self.items:
            return None
        return self.items[-1]
 
    def is_empty(self) -> bool:
        return len(self.items) == 0

pub struct Stack<T> {
    items: Vec<T>,
}
 
impl<T> Stack<T> {
    pub fn new() -> Self {
        Stack { 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()
    }
}
 
fn main() {}