Rust Queue and Stack Collections: Vec and VecDeque

Rust usually uses general-purpose collections rather than separate Stack and Queue types. Use Vec<T> as a LIFO stack and VecDeque<T> as an efficient FIFO queue. You will learn the relevant methods, why the collections differ, and how to choose the right one.

A stack and a queue describe how values are accessed:

• A stack is LIFO: last in, first out. The most recently added item is removed first.
• A queue is FIFO: first in, first out. The earliest added item is removed first.

Rust's standard library does not provide direct equivalents of C++'s std::stack and std::queue container adapters. Instead, it provides collections with operations that naturally implement these behaviors:

• Use Vec<T> for a stack.
• Use std::collections::VecDeque<T> for a queue.

This choice is important for performance. A Vec is optimized for adding and removing values at its end, so it is ideal for a stack. Removing from the beginning of a Vec shifts all remaining elements, which is inefficient for a queue. VecDeque supports efficient operations at both the front and back, making it appropriate for FIFO queues.

Think of a stack as a pile of plates:

• Put a plate on the top.
• Take a plate from the top.
• The last plate placed there is the first one removed.

Think of a queue as a line at a checkout:

• New customers join at the back.
• The customer at the front is served first.
• The first customer to arrive is the first customer to leave.

Vec is built for working efficiently at one end, like the top of the plate pile. VecDeque is built for working efficiently at both ends, like a line with an entrance and an exit.

For a stack, use Vec<T> and treat its end as the top:

let mut stack: Vec<&str> = Vec::new();

stack.push("first");
stack.push("second");

assert_eq!(stack.last(), Some(&"second"));
assert_eq!(stack.pop(), Some("second"));
assert_eq!(stack.pop(), Some("first"));
assert_eq!(stack.pop(), None);

• push(value) adds value to the end of the vector.
• pop() removes and returns the final value as Option<T>.
• last() borrows the final value as Option<&T> without removing it.

For a queue, import and use VecDeque<T>:

use std::collections::VecDeque;

let mut queue: VecDeque<&str> = VecDeque::new();

queue.push_back("first");
queue.push_back("second");

assert_eq!(queue.front(), Some(&"first"));
assert_eq!(queue.back(), Some(&"second"));
assert_eq!(queue.pop_front(), Some("first"));
assert_eq!(queue.pop_front(), Some("second"));
assert_eq!(queue.pop_front(), None);

• push_back(value) adds an item to the back of the queue.
• pop_front() removes and returns the item at the front.
• front() and back() borrow an item without removing it.

The Option return type handles an empty collection safely: None means there was no value to return.

Consider this queue:

use std::collections::VecDeque;

let mut jobs = VecDeque::new();
jobs.push_back("email");
jobs.push_back("report");
let next = jobs.pop_front();

Execution trace:

1. VecDeque::new() creates an empty queue: [].
2. push_back("email") adds a job at the back: ["email"].
3. push_back("report") adds another job after it: ["email", "report"].
4. pop_front() removes the front job, which is "email".
5. next becomes Some("email"), and the queue now contains ["report"].

Now compare a stack:

let mut undo_stack = Vec::new();
undo_stack.push("typed A");
undo_stack.push("typed B");
let action = undo_stack.pop();

After the two pushes, the vector is ["typed A", "typed B"]. pop() removes the final item, so action is Some("typed B"). This is LIFO behavior.

Vec<T> as a stack is useful for:

• Undo history in an editor: undo the newest action first.
• Parsing nested expressions, parentheses, or markup tags.
• Depth-first search through a tree or graph.
• Tracking function-like work that must be completed in reverse order.

VecDeque<T> as a queue is useful for:

• Processing web jobs in arrival order.
• Breadth-first search through a tree or graph.
• Buffering messages, events, or log records.
• Scheduling tasks that should run in the order they were submitted.
• Maintaining a fixed-size recent-history buffer by adding at the back and removing from the front.

In real Rust projects, stacks and queues are often kept private behind domain-specific functions instead of exposing collection operations everywhere.

A queue-processing loop commonly handles empty queues through Option:

use std::collections::VecDeque;

fn process_all(mut tasks: VecDeque<String>) {
    while let Some(task) = tasks.pop_front() {
        println!("Processing {task}");
    }
}

while let Some(...) stops naturally when the queue is empty. It avoids unsafe indexing and avoids manually checking the length.

For a bounded queue, remove old values after adding a new one:

use std::collections::VecDeque;

fn add_recent(items: &mut VecDeque<String>, item: String, limit: usize) {
    items.push_back(item);

    if items.len() > limit {
        items.pop_front();
    }
}

For stacks, developers often use a Vec with guard-style handling of an empty stack:

fn undo(history: &mut Vec<String>) -> Option<String> {
    history.pop()
}

Returning Option<String> makes the possibility of "nothing to undo" explicit to callers.

Using Vec::remove(0) for a busy queue

This works functionally, but it is usually inefficient because every remaining element must shift left.

let mut queue = vec!["first", "second", "third"];
let first = queue.remove(0); // Avoid for a frequently used FIFO queue

Use VecDeque instead:

use std::collections::VecDeque;

let mut queue = VecDeque::from(["first", "second", "third"]);
let first = queue.pop_front();

Reversing the queue ends

This code behaves like a stack, not a FIFO queue:

use std::collections::VecDeque;

let mut queue = VecDeque::new();
queue.push_back(1);
queue.push_back(2);
let value = queue.pop_back(); // Removes 2 first: LIFO

For FIFO behavior, pair push_back with pop_front.

Treating pop() as if it always returns a value

pop() and pop_front() return Option<T> because a collection may be empty.

let mut stack: Vec<i32> = Vec::new();
let value = stack.pop(); // None

Handle None with match, if let, while let, or an appropriate fallback such as unwrap_or.

Using indexing to inspect an empty collection

let stack: Vec<i32> = Vec::new();
let top = stack[stack.len() - 1]; // Panics due to underflow/out-of-bounds access

Use last() for stacks or front() and back() for queues. These return Option safely.

Vec versus VecDeque:

• Vec stores values contiguously and is often the default growable sequence.
• VecDeque is a double-ended queue. Its internal layout allows efficient front and back operations.
• Choose VecDeque when your design regularly removes from the front.

A VecDeque can technically act as a stack too, but Vec is simpler and more conventional when only end-based stack operations are needed.

// Stack: LIFO
let mut stack: Vec<i32> = Vec::new();
stack.push(10);           // add to top
let top = stack.last();   // Option<&i32>, inspect top
let item = stack.pop();   // Option<i32>, remove top

// Queue: FIFO
use std::collections::VecDeque;

let mut queue: VecDeque<i32> = VecDeque::new();
queue.push_back(10);      // add at back
let first = queue.front(); // Option<&i32>, inspect front
let last = queue.back();   // Option<&i32>, inspect back
let item = queue.pop_front(); // Option<i32>, remove front

• Stack rule: use push + pop on Vec.
• Queue rule: use push_back + pop_front on VecDeque.
• All pop and peek methods return Option because the collection might be empty.
• Avoid Vec::remove(0) for a frequently used queue; it shifts remaining elements.
• VecDeque also offers push_front() and pop_back() when both ends are needed.

Does Rust have a built-in stack type?

Rust does not provide a separate standard-library Stack type. Use Vec<T> with push() and pop().

Does Rust have a built-in queue type?

Rust does not provide a C++-style std::queue adapter. Use std::collections::VecDeque<T> with push_back() and pop_front().

Why is Vec good for a stack?

Adding to and removing from the end of a Vec is efficient, which matches normal stack operations.

Why should I not use Vec as a FIFO queue?

Removing from index 0 requires shifting the remaining values. For repeated queue operations, use VecDeque.

What does pop_front() return when the queue is empty?

It returns None. When an item exists, it returns Some(item).

Can VecDeque be used as a stack?

Yes. You can use push_back() and pop_back(), but Vec is usually the clearer choice for a simple stack.

How do I look at the next queue item without removing it?

Call queue.front(). It returns Option<&T>.

How do I look at the top stack item without removing it?

Call stack.last(). It returns Option<&T>.

• Vectors (Vec<T>) — the standard growable collection used for stack behavior.
• Double-ended queues (VecDeque<T>) — the standard collection for efficient front and back operations.
• Option<T> — pop and peek operations use Option to represent an empty collection safely.
• Ownership and borrowing — pop transfers ownership of an item, while front, back, and last return borrowed references.
• Iteration — collections can be processed with for loops or iterator methods.
• Breadth-first search — a common algorithmic use of FIFO queues.
• Depth-first search — a common algorithmic use of LIFO stacks.