Implementing a Stack with Push and Pop Operations in Rust

This challenge focuses on implementing a fundamental data structure: a stack. Stacks operate on a Last-In, First-Out (LIFO) principle, meaning the last element added is the first one to be removed. You will create a basic stack implementation in Rust that supports the essential push and pop operations. This is a foundational exercise for understanding data structures and memory management in Rust.

Problem Description

You are tasked with creating a Stack struct in Rust that can store elements of a generic type T. This Stack should implement two primary methods:

• push(item: T): Adds an element to the top of the stack.
• pop() -> Option<T>: Removes and returns the element from the top of the stack. If the stack is empty, it should return None.

Your implementation should be memory-safe and leverage Rust's ownership and borrowing rules effectively.

Key Requirements:

1. Generic Type T: The Stack should be able to hold elements of any type.
2. push Method: Implement a method push(&mut self, item: T) that adds item to the top of the stack.
3. pop Method: Implement a method pop(&mut self) -> Option<T> that removes and returns the top element.
4. Empty Stack Handling: The pop method must correctly handle the case where the stack is empty by returning None.
5. Internal Representation: You can choose an appropriate internal data structure for your stack (e.g., Vec).

Expected Behavior:

• Pushing elements onto the stack should add them in the order they are provided.
• Popping elements should remove them in reverse order of insertion.
• Calling pop on an empty stack should yield None without panicking.

Examples

Example 1:

// Initialize an empty stack of integers
let mut stack: Stack<i32> = Stack::new();

// Push some elements
stack.push(10);
stack.push(20);
stack.push(30);

// Pop elements
let item1 = stack.pop(); // Should be Some(30)
let item2 = stack.pop(); // Should be Some(20)
let item3 = stack.pop(); // Should be Some(10)
let item4 = stack.pop(); // Should be None

Output (Conceptual):

• item1: Some(30)
• item2: Some(20)
• item3: Some(10)
• item4: None

Explanation: Elements are pushed in the order 10, 20, 30. The pop operation removes them in the reverse order: 30, then 20, then 10. After all elements are popped, the stack is empty, and subsequent pop calls return None.

Example 2:

// Initialize a stack of strings
let mut string_stack: Stack<String> = Stack::new();

string_stack.push("hello".to_string());
string_stack.push("world".to_string());

let first_pop = string_stack.pop(); // Should be Some("world")
let second_pop = string_stack.pop(); // Should be Some("hello")
let third_pop = string_stack.pop();  // Should be None

Output (Conceptual):

• first_pop: Some("world")
• second_pop: Some("hello")
• third_pop: None

Explanation: This demonstrates the stack's ability to handle String types and the LIFO principle with non-primitive data.

Example 3: Edge Case - Empty Stack

let mut empty_stack: Stack<f64> = Stack::new();
let popped_item = empty_stack.pop(); // Should be None

Output (Conceptual):

• popped_item: None

Explanation: Attempting to pop from a newly created, empty stack correctly returns None.

Constraints

• The Stack struct and its methods must be implemented within a single Rust file.
• You are expected to use standard Rust library features. No external crates are permitted for the core stack implementation.
• The implementation should be reasonably efficient. For typical stack operations, the time complexity for push and pop should ideally be O(1) amortized.

Notes

• Consider using Vec<T> as the internal storage for your stack. Vec provides efficient push and pop operations at the end, which maps directly to stack behavior.
• Pay close attention to Rust's borrowing rules when implementing the pop method to ensure you are correctly returning ownership of the popped element.
• The Option<T> enum is crucial for handling the case where the stack might be empty when pop is called.
• To make your Stack struct usable, you'll likely need to implement a new() associated function to create an empty stack.