What a stack is
A stack is a collection where you add and remove elements at one end only, called the top. The element added last is the first to come out. This rule is known as last in, first out, or LIFO. A pile of plates works the same way: you put a plate on top and take the top plate off, and you don't pull one from the middle.
A stack supports a few operations:
- push adds an element on the top;
- pop removes the top element and gives it back;
- peek looks at the top element without removing it;
- is empty and size tell you what is in the stack.
Every one of these is a constant-time operation. That is the reason stacks show up in so many algorithms: they remember things in the order they arrived and give back the most recent one first.
A stack in Rust is a Vec
Rust's standard library has no separate stack type. A Vec<T> already works as one, with its end acting as the top. The methods map to the operations like this:
| Operation | Method | Returns |
|---|---|---|
| push | push(value) | nothing |
| pop | pop() | Option<T> |
| peek | last() | Option<&T> |
| is empty | is_empty() | bool |
| size | len() | usize |
Here they are at work:
fn main() {
let mut stack: Vec<i32> = Vec::new();
stack.push(10);
stack.push(20);
stack.push(30);
println!("{:?}", stack); // [10, 20, 30]
println!("{:?}", stack.last()); // Some(30)
println!("{}", stack.len()); // 3
println!("{:?}", stack.pop()); // Some(30)
println!("{:?}", stack.pop()); // Some(20)
println!("{:?}", stack); // [10]
}
The stack must be declared mut, because push and pop change it. The top of the stack is the last element, so [10, 20, 30] has 30 on top.
Options instead of errors
Both pop() and last() return an Option, because the stack might be empty. On an empty stack they return None, and they don't panic:
fn main() {
let mut stack: Vec<i32> = vec![10];
stack.pop();
println!("{}", stack.is_empty()); // true
println!("{:?}", stack.pop()); // None
println!("{:?}", stack.last()); // None
}
You have three common ways to deal with the Option:
matchwith aSomearm and aNonearm, when both cases need different code;if let Some(top) = stack.pop(), orwhile let Some(top) = stack.pop()to empty the stack one element at a time;unwrap(), when you already know the stack isn't empty, for example right after checking!stack.is_empty(). OnNone,unwrap()panics withcalled `Option::unwrap()` on a `None` value.
The while let form is the idiomatic loop for draining a stack:
fn main() {
let mut s: Vec<i32> = vec![1, 2, 3];
while let Some(top) = s.pop() {
println!("{}", top);
}
}
It prints 3, then 2, then 1: the reverse of the order in which they were pushed. That reversal is the stack's signature behaviour. Pushing the characters of "stack" one by one and popping them all gives kcats.
Gotchas in Rust
last()borrows the stack. It gives a reference to the top,Option<&T>. While you hold that reference, you can't change the stack. This fails to compile:
The compiler reports thatfn main() { let mut stack = vec![1, 2, 3]; let top = stack.last().unwrap(); stack.push(4); println!("{}", top); }stackcan't be borrowed as mutable because it is also borrowed as immutable. When the element is a smallCopytype such asi32orchar, copy it out withif let Some(&top) = stack.last(), or with*stack.last().unwrap(), and the borrow ends right away.- Dereferencing. The reference returned by
last()has to be dereferenced with*where a plain value is needed. A stack of indices,Vec<usize>, is used asnums[*stack.last().unwrap()]. Comparing the reference itself with a number, without the*, doesn't compile. - Pop returns the value. After
let top = stack.pop(), the element is no longer in the stack. Uselast()when you only want to look. - Don't insert at the front.
insert(0, x)andremove(0)shift every element and takeO(n). AVecis a fast stack only at the end. - Index types.
len()and indices areusize. If a stack holds indices, make it aVec<usize>so that they can index a vector with no cast, and cast toi32only when a result needs it.
Complexity
push takes O(1) amortized. When a Vec runs out of room, it allocates a larger buffer and moves the elements, which is occasionally expensive. Because the buffer grows geometrically, the average cost of a push stays constant. pop, last, len and is_empty are O(1). A stack holding n elements uses O(n) space.
How stacks are used in this chapter
A stack is the right tool when the most recent item is the one you need to deal with next. Two patterns come up again and again:
- Matching. Scanning a string and pushing each opening bracket, then popping when a closing bracket arrives, checks that brackets close in the right order. The one that opened last must be the first to close.
- Waiting for an answer. Scanning an array and keeping the indices of elements that have not found what they are waiting for, such as a greater value to their right. When a new element arrives, it settles the waiting entries at the top of the stack and then joins them.
In both, each element is pushed once and popped at most once, so the whole scan stays linear even when it contains a loop inside a loop.
Key takeaways
- A stack is last in, first out. All its work happens at the top.
- In Rust, use a
Vec:push,pop,last,is_emptyandlenare all you need. pop()andlast()return anOption:Nonemeans empty, andunwrap()onNonepanics.last()borrows the stack, so copy the value out before you change it.- Every operation takes constant time, so a stack costs nothing extra in a linear scan.
