Queue Implementation (Using VecDeque)

A queue is a linear data structure that follows the First In, First Out (FIFO) principle. In Rust, the VecDeque<T> type from the standard library is the most efficient and idiomatic choice for implementing a queue.

Unlike Vec, which is optimized for pushing and popping at one end, VecDeque supports constant-time insertion and removal at both ends.

Why Use VecDeque for a Queue?

VecDeque is ideal for queue behavior because:

• push_back adds elements to the rear
• pop_front removes elements from the front
• Both operations run in O(1) time
• Memory is managed safely and efficiently

Queue Operations

A queue typically supports:

• Enqueue - add an element to the rear
• Dequeue - remove an element from the front
• Front / Peek - view the front element
• Is Empty - check if the queue is empty

Rust Implementation

use std::collections::VecDeque;

#[derive(Debug)]
pub struct Queue<T> {
    data: VecDeque<T>,
}

impl<T> Queue<T> {
    pub fn new() -> Self {
        Queue {
            data: VecDeque::new(),
        }
    }

    pub fn enqueue(&mut self, value: T) {
        self.data.push_back(value);
    }

    pub fn dequeue(&mut self) -> Option<T> {
        self.data.pop_front()
    }

    pub fn peek(&self) -> Option<&T> {
        self.data.front()
    }

    pub fn is_empty(&self) -> bool {
        self.data.is_empty()
    }

    pub fn len(&self) -> usize {
        self.data.len()
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn queue_works() {
        let mut queue = Queue::new();

        assert!(queue.is_empty());

        queue.enqueue(1);
        queue.enqueue(2);
        queue.enqueue(3);

        assert_eq!(queue.peek(), Some(&1));
        assert_eq!(queue.dequeue(), Some(1));
        assert_eq!(queue.dequeue(), Some(2));
        assert_eq!(queue.dequeue(), Some(3));
        assert!(queue.is_empty());
    }
}

Example Usage

fn main() {
    let mut queue = Queue::new();

    queue.enqueue(10);
    queue.enqueue(20);
    queue.enqueue(30);

    println!("Front: {:?}", queue.peek()); // Some(10)

    while let Some(value) = queue.dequeue() {
        println!("Dequeued: {}", value);
    }
}

Output:

Front: Some(10)
Dequeued: 10
Dequeued: 20
Dequeued: 30

Time and Space Complexity

Time Complexity

Space Complexity

Advantages of VecDeque Queue

• Efficient at both ends
• Simple and readable
• No manual pointer handling
• Preferred queue implementation in Rust

Limitations

• Slightly more overhead than Vec
• Not thread-safe by default

Summary

• Queue behavior maps naturally to VecDeque
• FIFO semantics enforced cleanly
• Efficient and idiomatic Rust solution
• Best choice for most queue use cases

Playground Links

Rust - Queue Implementation (Using VecDeque)