Struct MinQueue

pub struct MinQueue<T> { /* private fields */ }

A FIFO queue that supports O(1) push, pop and find-minimum.

Keith Schwarz explains how this works here.

Example

use rust_dsa::MinQueue;

// First, we create a new queue.
let mut queue = MinQueue::new();

// We can push elements.
queue.push(1);
queue.push(6);
queue.push(2);
queue.push(3);

// We can get the minimum element.
assert_eq!(queue.get_min(), Some(&1));

// We can peek and poll as usual.
assert_eq!(queue.peek(), Some(&1));
assert_eq!(queue.poll(), Some(1));

// The min element reflects the queue's new state.
assert_eq!(queue.get_min(), Some(&2));

// We can iterate over the queue.
for x in queue {
    // Prints 6, 2 and 3.
    println!("{x}");
}

// We can also create queues from arrays.
let a = MinQueue::from(['q', 'u', 'e', 'u', 'e']);

// And iterators.
let b: MinQueue<_> = "queue".chars().collect();

assert!(a == b);

Implementations

impl<T> MinQueue<T>

pub fn new() -> MinQueue<T>

Creates an empty queue.

pub fn with_capacity(capacity: usize) -> MinQueue<T>

Creates an empty queue with the specified capacity.

pub fn push(&mut self, value: T)

where T: Ord,

Pushes an element into the queue.

Example

use rust_dsa::MinQueue;

let mut queue = MinQueue::new();
queue.push(5);

assert_eq!(queue.poll(), Some(5));
assert_eq!(queue.poll(), None);

pub fn poll(&mut self) -> Option<T>

where T: Ord,

Removes the next element in the queue and returns it or None if the queue is empty.

Example

use rust_dsa::MinQueue;

let mut queue = MinQueue::from([5]);

assert_eq!(queue.poll(), Some(5));
assert_eq!(queue.poll(), None);

pub fn peek(&self) -> Option<&T>

Returns a reference the next element in the queue or None if the queue is queue.

Example

use rust_dsa::MinQueue;

let mut queue = MinQueue::from(['a']);

assert_eq!(queue.peek(), Some(&'a'));

queue.poll();

assert_eq!(queue.peek(), None);

pub fn get_min(&mut self) -> Option<&T>

where T: Ord,

Returns the smallest element in the queue or None if the queue is empty.

Example

use rust_dsa::MinQueue;

let mut queue = MinQueue::from([1, 5, 3, 4, 8, 2, 6]);

assert_eq!(queue.get_min(), Some(&1));

queue.poll();

assert_eq!(queue.get_min(), Some(&2));

queue.clear();

assert_eq!(queue.get_min(), None);

pub fn len(&self) -> usize

Returns the number of elements in the queue.

Example

use rust_dsa::MinQueue;

let mut queue = MinQueue::from([1, 5, 3, 4, 8, 2, 6]);

assert_eq!(queue.len(), 7);

queue.clear();

assert_eq!(queue.len(), 0);

pub fn is_empty(&self) -> bool

Returns true if the queue is empty.

Example

use rust_dsa::MinQueue;

let mut queue = MinQueue::from([1, 5, 3, 4, 8, 2, 6]);

assert!(!queue.is_empty());

queue.clear();

assert!(queue.is_empty());

pub fn clear(&mut self)

Clears the queue.

Example

use rust_dsa::MinQueue;

let mut queue = MinQueue::from([5, 3, 4, 8, 2, 6, 1]);

assert!(!queue.is_empty());

queue.clear();

assert!(queue.is_empty());

Trait Implementations

impl<T: Clone> Clone for MinQueue<T>

fn clone(&self) -> MinQueue<T>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T> Debug for MinQueue<T>

where T: Debug,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T> Default for MinQueue<T>

fn default() -> MinQueue<T>

Returns the “default value” for a type.

impl<T, const N: usize> From<[T; N]> for MinQueue<T>

where T: Ord,

fn from(array: [T; N]) -> MinQueue<T>

Converts to this type from the input type.

impl<T> FromIterator<T> for MinQueue<T>

where T: Ord,

fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> MinQueue<T>

Creates a value from an iterator.

impl<'a, T> IntoIterator for &'a MinQueue<T>

type IntoIter = Iter<'a, T>

Which kind of iterator are we turning this into?

type Item = &'a T

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T> IntoIterator for MinQueue<T>

type IntoIter = IntoIter<T>

Which kind of iterator are we turning this into?

type Item = T

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T> PartialEq for MinQueue<T>

where T: PartialEq,

fn eq(&self, other: &MinQueue<T>) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<T: Eq> Eq for MinQueue<T>