Introduction

In Rust, VecDeque is a double-ended queue implemented with a growable ring buffer. It allows for efficient insertion and removal of elements at both ends of the queue. VecDeque is part of the standard library's std::collections module and is useful when you need a collection that supports fast, flexible insertion and deletion operations from both the front and the back.

Using VecDeque

To use VecDeque, you need to import it from the std::collections module. You can create a VecDeque by using the VecDeque::new method. Elements can be added using methods like push_back and push_front, and accessed or removed using methods like pop_back and pop_front.

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::new();
    deque.push_back(1);
    deque.push_back(2);
    deque.push_front(0);

    println!("Deque: {:?}", deque);
    println!("First element: {:?}", deque.pop_front());
}
// Output:
// Deque: [0, 1, 2]
// First element: Some(0)

Key Methods

Below are some of the key methods exposed by the VecDeque class:

VecDeque::new

Creates a new, empty VecDeque.

use std::collections::VecDeque;

fn main() {
    let deque: VecDeque<i32> = VecDeque::new();
    println!("Created an empty deque: {:?}", deque);
}
// Output:
// Created an empty deque: []

VecDeque::push_back

Adds an element to the back of the VecDeque.

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::new();
    deque.push_back(10);
    deque.push_back(20);
    println!("Deque after push_back: {:?}", deque);
}
// Output:
// Deque after push_back: [10, 20]

VecDeque::push_front

Adds an element to the front of the VecDeque.

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::new();
    deque.push_front(5);
    deque.push_front(15);
    println!("Deque after push_front: {:?}", deque);
}
// Output:
// Deque after push_front: [15, 5]

VecDeque::pop_back

Removes and returns the last element from the VecDeque. Returns None if the deque is empty.

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::new();
    deque.push_back(30);
    deque.push_back(40);
    println!("Popped element: {:?}", deque.pop_back());
    println!("Deque after pop_back: {:?}", deque);
}
// Output:
// Popped element: Some(40)
// Deque after pop_back: [30]

VecDeque::pop_front

Removes and returns the first element from the VecDeque. Returns None if the deque is empty.

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::new();
    deque.push_front(50);
    deque.push_front(60);
    println!("Popped element: {:?}", deque.pop_front());
    println!("Deque after pop_front: {:?}", deque);
}
// Output:
// Popped element: Some(60)
// Deque after pop_front: [50]

Example Usage

Example 1: Basic Usage

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::new();
    deque.push_back(1);
    deque.push_back(2);
    deque.push_front(0);

    println!("Deque: {:?}", deque);
    println!("First element: {:?}", deque.pop_front());
}
// Output:
// Deque: [0, 1, 2]
// First element: Some(0)

Example 2: Inserting at Both Ends

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::new();
    deque.push_back(5);
    deque.push_front(3);
    deque.push_back(7);
    println!("Deque: {:?}", deque);
}
// Output:
// Deque: [3, 5, 7]

Example 3: Removing Elements

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::new();
    deque.push_back(10);
    deque.push_back(20);
    deque.push_back(30);

    println!("Removed from front: {:?}", deque.pop_front());
    println!("Removed from back: {:?}", deque.pop_back());
    println!("Deque: {:?}", deque);
}
// Output:
// Removed from front: Some(10)
// Removed from back: Some(30)
// Deque: [20]

Example 4: Iterating Over Elements

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::new();
    deque.push_back(1);
    deque.push_back(2);
    deque.push_back(3);

    for element in &deque {
        println!("{}", element);
    }
}
// Output:
// 1
// 2
// 3

Example 5: Using Double-Ended Iterator

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::new();
    deque.push_back(1);
    deque.push_back(2);
    deque.push_back(3);

    let mut iter = deque.iter();
    println!("First: {:?}", iter.next());
    println!("Last: {:?}", iter.next_back());
}
// Output:
// First: Some(1)
// Last: Some(3)

Considerations

VecDeque is useful for cases where you need frequent insertions and deletions at both ends of the deque.
It provides O(1) time complexity for operations like push and pop at both ends.
While VecDeque offers efficient front and back operations, it may not be as memory efficient as Vec for random access or iteration.