Skip to content
Hacking with RustHacking with Rust
Select theme

How to use a Vec as a queue

Short answer: reach for VecDeque, not Vec. push_back adds to the back, pop_front takes from the front, and neither moves the other elements. Vec::remove(0) does the same job and shifts the whole tail left every time, so draining a queue that way costs O(n) per item.

From a fresh project (cargo new queue-demo — the name is mine, and nothing below prints it), replace the contents of src/main.rs with each block and run it with cargo run. Everything here is Rust 1.99.0, edition 2024.

The queue itself

Section titled “The queue itself”
use std::collections::VecDeque;


fn main() {
    let mut queue: VecDeque<&str> = VecDeque::new();
    queue.push_back("first");
    queue.push_back("second");
    queue.push_back("third");


    println!("len: {}", queue.len());
    println!("front: {:?}", queue.front());
    println!("back: {:?}", queue.back());


    println!("pop_front: {:?}", queue.pop_front());
    println!("pop_front: {:?}", queue.pop_front());
    println!("left: {:?}", queue);
    println!("pop_front: {:?}", queue.pop_front());
    println!("pop_front on empty: {:?}", queue.pop_front());
}
Run this in the Rust Playground
len: 3
front: Some("first")
back: Some("third")
pop_front: Some("first")
pop_front: Some("second")
left: ["third"]
pop_front: Some("third")
pop_front on empty: None

front and back look without taking, and all three of these return an Option — Some while the queue holds something, None when it runs dry — so a drain loop can run until the queue is empty without tracking a length. It is a double-ended queue, so push_front and pop_back work at the other end too. A Vec already has push and pop at the back; a queue needs the front.

Why remove(0) is the wrong tool

Section titled “Why remove(0) is the wrong tool”
fn main() {
    let mut v: Vec<i32> = vec![1, 2, 3];
    if let Some(x) = v.remove(0) {
        println!("{x}");
    }
}
Run this in the Rust Playground
error[E0308]: mismatched types
 --> src/main.rs:3:12
  |
3 |     if let Some(x) = v.remove(0) {
  |            ^^^^^^^   ----------- this expression has type `i32`
  |            |
  |            expected `i32`, found `Option<_>`
  |
  = note: expected type `i32`
             found enum `Option<_>`


For more information about this error, try `rustc --explain E0308`.

The mistake is natural: pop_front hands back an Option, so remove looks like it should too. Vec::remove returns the element itself, and on an empty Vec it panics with removal index (is 0) should be < len (is 0). The cost is the real problem. The standard library’s own note on remove gives it “a worst-case performance of O(n)” — it shifts every element after the index to the left — and points at VecDeque::pop_front for removing from the front of a Vec.

use std::collections::VecDeque;
use std::hint::black_box;
use std::time::Instant;


fn drain_with_remove(n: usize) -> usize {
    let mut v: Vec<usize> = (0..n).collect();
    let mut total = 0;
    while !v.is_empty() {
        total += black_box(v.remove(0));
    }
    total
}


fn drain_with_pop_front(n: usize) -> usize {
    let mut q: VecDeque<usize> = (0..n).collect();
    let mut total = 0;
    while let Some(x) = q.pop_front() {
        total += black_box(x);
    }
    total
}


fn main() {
    for &n in &[1_000usize, 10_000, 100_000] {
        let mut remove_times = Vec::new();
        let mut pop_times = Vec::new();
        for _ in 0..5 {
            let start = Instant::now();
            black_box(drain_with_remove(n));
            remove_times.push(start.elapsed());
            let start = Instant::now();
            black_box(drain_with_pop_front(n));
            pop_times.push(start.elapsed());
        }
        remove_times.sort();
        pop_times.sort();
        println!("n={n}: remove(0) {:?}, pop_front {:?}", remove_times[2], pop_times[2]);
    }
}
Run this in the Rust Playground

Run that with cargo run --release: median of five rounds, draining a queue built from 0..n one item at a time. At 100,000 items remove(0) takes about 740 ms and pop_front about 130 µs. Ten times the items makes remove(0) roughly a hundred times slower — each pop shifts what is left, so the total grows with the square of the count — while pop_front costs the same per item whatever the size. A plain cargo run prints different numbers — larger for pop_front, about the same for remove(0).

When the order genuinely does not matter, swap_remove(0) is O(1): it moves the last element into the hole, so ["a", "b", "c", "d"] loses "a" and becomes ["d", "b", "c"]. That is no longer a queue, but it is the right tool for “delete this one item”.

What the ring buffer costs you

Section titled “What the ring buffer costs you”
use std::collections::VecDeque;


fn main() {
    let mut queue: VecDeque<i32> = VecDeque::new();
    for i in 0..8 {
        queue.push_back(i);
    }
    for _ in 0..4 {
        queue.pop_front();
    }
    for i in 8..12 {
        queue.push_back(i);
    }


    println!("len: {}, capacity: {}", queue.len(), queue.capacity());
    let (head, tail) = queue.as_slices();
    println!("as_slices: {:?} and {:?}", head, tail);
    println!("iter: {:?}", queue.iter().collect::<Vec<_>>());
    println!("index 0: {}", queue[0]);
    println!("get 100: {:?}", queue.get(100));
}
Run this in the Rust Playground
len: 8, capacity: 8
as_slices: [4, 5, 6, 7] and [8, 9, 10, 11]
iter: [4, 5, 6, 7, 8, 9, 10, 11]
index 0: 4
get 100: None

The two slices are the ring showing through: after the pops and pushes the buffer has wrapped, so part of the queue sits at the end of the allocation and the rest at the start. iter() and Debug still walk front to back, and the capacity never moved: the queue kept its buffer instead of reallocating one. When one contiguous slice is needed, make_contiguous() rotates the deque and returns &[T]; the standard library’s words are that the elements are “not necessarily contiguous in memory”, and it names sorting as the reason to reach for it. VecDeque also indexes by position only: queue[0] works, while &queue[1..3] does not compile, because the index takes a usize and not a range.

Section titled “Related”

Next in this chapter: how to get the largest element from a collection.