Struct Deque

Source

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

Expand description

A deque implementation backed by a ring buffer.

§Example

use rust_dsa::Deque;

// First, we create a new deque.
let mut deque = Deque::new();

// Then we can push values onto the front or back.
deque.push_back(4);
deque.push_back(1);
deque.push_front(3);

// And pop from the front or back.
assert_eq!(deque.pop_back(), Some(1));
assert_eq!(deque.pop_front(), Some(3));
assert_eq!(deque.pop_front(), Some(4));

// We can also crate deques from arrays.
let deque_a = Deque::from(['d', 'e', 'q', 'u', 'e']);

// And iterators.
let deque_b: Deque<_> = "deque".chars().collect();

// We can iterate over a deque.
for (a, b) in std::iter::zip(deque_a, deque_b) {
    assert_eq!(a, b);
}

let mut deque = Deque::from([1, 2, 3, 4, 5]);
for i in 0..1_000_000 {
    deque.pop_front();
    deque.push_back(i);
}
// After pushing and poping a million elements,
// the capacity is still 5.
assert_eq!(deque.capacity(), 5);

assert_eq!(
    deque.into_iter().collect::<Vec<_>>(),
    vec![999_995, 999_996, 999_997, 999_998, 999_999]
);

§Runtime complexity

Operation	Runtime Complexity
Deque::push_back	O(1)
Deque::push_front	O(1)
Deque::pop_back	O(1)
Deque::pop_front	O(1)

Implementations§

Source §

impl<T> Deque<T>

Source

pub fn new() -> Deque<T>

Creates an empty deque.

Source

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

Creates an empty deque with the given capacity.

§Example

use rust_dsa::Deque;

let deque: Deque<u8> = Deque::with_capacity(10);

assert_eq!(deque.capacity(), 10);

Source

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

Pushes a value onto the back of the deque.

§Example

use rust_dsa::Deque;

let mut deque = Deque::new();

deque.push_back(5);

assert_eq!(deque.peek_back(), Some(&5));

Source

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

Pushes a value onto the front of the deque.

§Example

use rust_dsa::Deque;

let mut deque = Deque::new();

deque.push_front(5);

assert_eq!(deque.peek_front(), Some(&5));

Source

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

Pops a value from the back of the deque.

§Example

use rust_dsa::Deque;

let mut deque = Deque::from([1, 2, 3]);

assert_eq!(deque.pop_back(), Some(3));
assert_eq!(deque.pop_back(), Some(2));
assert_eq!(deque.pop_back(), Some(1));
assert_eq!(deque.pop_back(), None);

Source

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

Pops a value from the front of the deque.

§Example

use rust_dsa::Deque;

let mut deque = Deque::from([1, 2, 3]);

assert_eq!(deque.pop_front(), Some(1));
assert_eq!(deque.pop_front(), Some(2));
assert_eq!(deque.pop_front(), Some(3));
assert_eq!(deque.pop_front(), None);

Source

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

Peeks the value at the back of the deque.

§Example

use rust_dsa::Deque;

let deque = Deque::from(['a', 'b', 'c']);

assert_eq!(deque.peek_back(), Some(&'c'));

let empty: Deque<u8> = Deque::new();
assert_eq!(empty.peek_back(), None);

Source

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

Peeks the value at the front of the deque.

§Example

use rust_dsa::Deque;

let deque = Deque::from(['a', 'b', 'c']);

assert_eq!(deque.peek_front(), Some(&'a'));

let empty: Deque<u8> = Deque::new();
assert_eq!(empty.peek_front(), None);

Source

pub fn get(&self, index: usize) -> Option<&T>

Returns a reference to the element in position index if index is in bounds.

.get(0) is equivalent to .peek_front().

§Example

use rust_dsa::Deque;

let mut deque = Deque::from(['a', 'b', 'c']);

assert_eq!(deque.get(1), Some(&'b'));

deque.pop_front();
assert_eq!(deque.get(1), Some(&'c'));

deque.pop_front();
assert_eq!(deque.get(1), None);

Source

pub fn drain<R>(&mut self, range: R) -> Drain<T>
where R: RangeBounds<usize>,

Removes the specified range from the deque, returning all removed elements as an iterator.

To simplify the implementation, this always reallocates the deque.

§Panics

Panics if the starting point is greater than the end point or if the end point is greater than the length of the deque.

§Example

use rust_dsa::Deque;

let mut deque: Deque<_> = ('a'..='z').collect();

let mut drain = deque.drain(1..25);
assert_eq!(drain.next(), Some('b'));
assert_eq!(drain.next(), Some('c'));
// etc...

// Now, deque is just ['a', 'z']
assert_eq!(deque.pop_front(), Some('a'));
assert_eq!(deque.pop_front(), Some('z'));
assert_eq!(deque.pop_front(), None);

Source

pub fn len(&self) -> usize

Returns the length of the deque.

§Example

use rust_dsa::Deque;

let full: Deque<_> = (0..10).collect();
assert_eq!(full.len(), 10);

let empty: Deque<bool> = Deque::new();
assert_eq!(empty.len(), 0);

Source

pub fn is_empty(&self) -> bool

Returns true if the deque is empty.

§Example

use rust_dsa::Deque;

let empty: Deque<bool> = Deque::new();
assert!(empty.is_empty());

let full: Deque<_> = (0..10).collect();
assert!(!full.is_empty());

Source

pub fn clear(&mut self)

Clears the deque.

§Example

use rust_dsa::Deque;

let mut deque = Deque::from([1, 2, 3]);

assert!(!deque.is_empty());

deque.clear();

assert!(deque.is_empty());

Source

pub fn shrink_to_fit(&mut self)

Shrinks the capacity of the buffer if possible.

§Example

use rust_dsa::Deque;

let mut deque = Deque::with_capacity(10);
deque.push_back("foo");
deque.push_back("bar");

assert_eq!(deque.capacity(), 10);
assert_eq!(deque.len(), 2);

deque.shrink_to_fit();

assert_eq!(deque.capacity(), 2);
assert_eq!(deque.len(), 2);

Source

pub fn capacity(&self) -> usize

Returns the number of elements the deque can hold without reallocating.

§Example

use rust_dsa::Deque;

let mut deque = Deque::with_capacity(10);

assert_eq!(deque.capacity(), 10);

for i in 0..20 {
    deque.push_back(i);
}

assert!(deque.capacity() > 10);