How to Implement a Generic Stack in Rust
Rust Recipes is a problem-oriented series of articles that assist developers while learning Rust. Every article solves simple, everyday development tasks using the Rust standard library or leveraging popular and proven crates.
Question: How to implement a generic stack in Rust?
To implement a generic stack, we can simply create a custom struct wrapping a vector (Vec<T>):
struct Stack<T> {
items: Vec<T>,
}
impl<T> Stack<T> {
fn new() -> Self {
Stack { items: Vec::new() }
}
fn push(&mut self, item: T) {
self.items.push(item);
}
fn pop(&mut self) -> Option<T> {
self.items.pop()
}
fn is_empty(&self) -> bool {
self.items.is_empty()
}
fn size(&self) -> usize {
self.items.len()
}
}
The implementation (impl<T> Stack<T>) uses a generic type T to allow it to store any type of data. The Stack struct has five methods: new, push, pop, is_empty, and size:
- The
newmethod creates a new instance of theStackstruct by creating a new empty vector (Vec<T>) - The
pushmethod adds a new item to the top of the stack by pushing it onto the vector - The
popmethod removes and returns the top item from the stack, or returnsNoneif the stack is empty - The
is_emptymethod returns a boolean value indicating whether or not the stack is empty - The
sizemethod returns the number of items currently in the stack
This implementation provides basic functionality for a stack, which can be used to store and manipulate data in a Last-In-First-Out (LIFO) manner. The following code demonstrates using the generic stack with values of type i32:
fn main() {
let mut stack = Stack::new();
println!("Pushing 1");
stack.push(1);
println!("Pushing 2");
stack.push(2);
println!("Pushing 3");
stack.push(3);
println!("Size of the stack: {}", stack.size());
let first = stack.pop();
println!("Got: {first:?}");
let second = stack.pop();
println!("Got: {second:?}");
println!("Pushing 4");
stack.push(4);
let third = stack.pop();
println!("Got: {third:?}");
let fourth = stack.pop();
println!("Got: {fourth:?}");
let fifth = stack.pop();
println!("Got: {fifth:?}");
println!("Is the stack empty? {}", stack.is_empty());
}
When we execute the program, the following output will be generated:
Pushing 1
Pushing 2
Pushing 3
Size of the stack: 3
Got: Some(3)
Got: Some(2)
Pushing 4
Got: Some(4)
Got: Some(1)
Got: None
Is the stack empty? true
Need to share such a stack between threads? Learn how to share state between threads
in Rust. Or see how pattern matching
helps to deal with Option<T> values like the one returned by pop.