Skip to content
Tutorials Center
My learning

Topics

Rust Reference ยท Collections

Rust VecDeque<T> type

Reference for Rust VecDeque<T>: ring buffer layout, push_front, push_back, pop_front, pop_back, indexing, make_contiguous, rotation and use as a queue.

VecDeque<T> (pronounced "vec-deck") is a growable double-ended queue built on a ring buffer. It supports O(1) insertion and removal at both ends, and O(1) indexing, which makes it the right tool for queues, sliding windows and breadth-first search. A Vec<T> is fast at the back only; removing from its front costs O(n).

Because the elements wrap around the end of the buffer, a VecDeque is not guaranteed to be one contiguous block, so it cannot dereference to a slice. Use as_slices(), make_contiguous() or iterators when you need to look at all elements.

Rust
use std::collections::VecDeque;

let mut q = VecDeque::new();
q.push_back(1);
q.push_front(0);

Try it

Rust Queue operations

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

Rust A sliding window and rotation

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

Syntax

Rust
pub struct VecDeque<T, A: Allocator = Global> { /* private */ }

VecDeque::new() -> VecDeque<T>
VecDeque::with_capacity(capacity: usize) -> VecDeque<T>
VecDeque::from(array_or_vec)
q.push_back(value)   q.push_front(value)
q.pop_back() -> Option<T>   q.pop_front() -> Option<T>
q.front() -> Option<&T>     q.back() -> Option<&T>
q[i]                 q.get(i) -> Option<&T>
Name Description
capacity Number of elements to reserve space for.
value The element to add; moved into the deque.
i Logical index counted from the front (0 is the front element).

Returns: the pop_*, front, back and get methods return Option, so an empty deque gives None.

Panics: q[i] panics when i >= len. insert(i, v) panics when i > len; remove(i) returns Option<T> instead of panicking.

Usage notes

  • Choose it for queues. push_back plus pop_front is a FIFO queue; push_back plus pop_back is a stack. Both ends are O(1) amortized.
  • Indexing is O(1) but slightly slower than Vec indexing because of the wrap-around arithmetic.
  • It is not a slice. Methods like sort, binary_search or windows need make_contiguous() (O(n), mutable) or the two halves from as_slices(). iter() always yields elements in logical order.
  • Conversions: Vec<T> into VecDeque<T> is O(1) (it reuses the buffer), and VecDeque<T> into Vec<T> is O(1) if the data is already contiguous, otherwise O(n). collect() and From<[T; N]> also work.
  • Middle insertion and removal are O(min(i, n - i)), because the deque shifts whichever side is shorter.
  • Capacity is managed like a vector's; see capacity and reserve. Do not rely on the exact numbers.
  • Other methods: extend, append, drain, retain, truncate, swap, contains, iter_mut, range, split_off, resize and rotate_left/rotate_right.
  • Thread safety: like other std collections it is not synchronized; wrap in a Mutex or use channels to share it.