Struct Queue

Source

pub struct Queue<E: Clone> { /* private fields */ }

Expand description

A persistent (immutable) FIFO queue data structure.

Queue is implemented using two lists (front and back) to achieve amortized O(1) enqueue and dequeue operations. All operations return a new queue, leaving the original unchanged.

§Performance

enqueue: O(1)
dequeue: O(1) amortized, O(n) worst case when reversing back list
is_empty: O(1)
len: O(1) - length is cached
to_vec: O(n)

Implementations§

Source §

impl<E: Clone> Queue<E>

Source

pub fn empty() -> Self

Creates a new empty queue.

§Examples

use pfds::Queue;
 
let queue: Queue<i32> = Queue::empty();
assert!(queue.is_empty());
assert_eq!(queue.len(), 0);

Source

pub fn enqueue(&self, e: E) -> Self

Creates a new queue with the given element added to the back.

This operation is O(1) and shares structure with the original queue.

§Arguments

e - The element to add to the back of the queue

§Examples

use pfds::Queue;
 
let queue = Queue::empty().enqueue(1).enqueue(2).enqueue(3);
assert_eq!(queue.len(), 3);

Source

pub fn dequeue(&self) -> (E, Self)

Removes and returns the front element and a new queue without that element.

This operation is O(1) amortized. When the front list is empty, it reverses the back list which takes O(n) time.

§Returns

A tuple containing:

The front element
A new queue without the front element

§Panics

Panics if the queue is empty.

§Examples

use pfds::Queue;
 
let queue = Queue::empty().enqueue(1).enqueue(2);
let (first, queue2) = queue.dequeue();
assert_eq!(first, 1);
assert_eq!(queue.len(), 2);  // Original unchanged
assert_eq!(queue2.len(), 1);

Source

pub fn is_empty(&self) -> bool

Returns true if the queue is empty.

This operation is O(1).

§Examples

use pfds::Queue;
 
let empty = Queue::<i32>::empty();
assert!(empty.is_empty());
 
let non_empty = empty.enqueue(1);
assert!(!non_empty.is_empty());

Source

pub fn len(&self) -> usize

Returns the number of elements in the queue.

This operation is O(1) as the length is cached.

§Examples

use pfds::Queue;
 
let queue = Queue::empty().enqueue(1).enqueue(2).enqueue(3);
assert_eq!(queue.len(), 3);

Source

pub fn to_vec(&self) -> Vec<E>

Converts the queue to a vector.

Elements are returned in FIFO order (oldest elements first). This operation is O(n).

§Examples

use pfds::Queue;
 
let queue = Queue::empty().enqueue(1).enqueue(2).enqueue(3);
let vec = queue.to_vec();
assert_eq!(vec, vec![1, 2, 3]); // FIFO order

Source

pub fn iter(&self) -> QueueIter<'_, E> ⓘ

Returns an iterator over the queue elements.

The iterator yields elements in FIFO order (oldest first).

§Examples

use pfds::Queue;
 
let queue = Queue::empty().enqueue(1).enqueue(2).enqueue(3);
let collected: Vec<_> = queue.iter().collect();
assert_eq!(collected, vec![1, 2, 3]);