double_vec_queue

A simple queue implementation using two vectors for efficient FIFO operations.

Overview

This crate provides a Queue<T> data structure that uses a dual-vector approach:

• Inbox: stores newly pushed elements
• Outbox: stores elements ready to be popped (in reverse order for efficient access)

This design enables amortized O(1) push and pop operations while minimizing allocations.

Features

• Generic queue implementation for any type T
• Efficient push/pop operations with amortized O(1) complexity
• Support for peeking at the front element
• Iteration support (by value, reference, and mutable reference)
• Conversion from Vec<T>
• Standard Rust iterator traits

Usage

Add this to your Cargo.toml:

[dependencies]
double_vec_queue = "0.1"

Examples

Basic Operations

use double_vec_queue::Queue;

let mut queue = Queue::new();

// Push elements
queue.push(1);
queue.push(2);
queue.push(3);

// Pop elements (FIFO order)
assert_eq!(queue.pop(), Some(1));
assert_eq!(queue.pop(), Some(2));

// Peek at the front
assert_eq!(queue.peek(), Some(&3));

// Pop the remaining element
assert_eq!(queue.pop(), Some(3));
assert_eq!(queue.pop(), None);

Creating from a Vec

use double_vec_queue::Queue;

let queue = Queue::from_vec(vec![1, 2, 3]);

Iteration

use double_vec_queue::Queue;

let mut queue = Queue::from_vec(vec![1, 2, 3]);

// Iterate by reference
for item in &queue {
    println!("{}", item);
}

// Iterate by mutable reference
for item in &mut queue {
    *item += 10;
}

// Iterate by value (consumes queue)
for item in queue {
    println!("{}", item);
}

Implementation Details

The queue uses a dual-vector strategy where:

• Elements are pushed into the inbox vector
• When popping, if the outbox is empty, all elements from inbox are moved to outbox in reverse order
• This provides amortized O(1) time complexity for both push and pop operations

License

Licensed under either of Apache License, Version 2.0 or MIT license at your option.