Struct MinStack

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

A LIFO stack that supports O(1) push, pop and find-minimum.

Internally, each element on the stack contains a value and the index of the minimum value below it (or itself if it is smaller than everything below it). Each time we push, we compare the new value to the smallest value already on the stack. If it is smaller, we push the new value with its own index. Otherwise, we push the new value with the index of the smaller value that was already on the stack.

To find the minimum value, we just use the index of the last element on the stack.

Example

use rust_dsa::MinStack;

// First, we create a new stack.
let mut stack = MinStack::new();

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

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

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

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

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

// We can also create stacks from arrays.
let a = MinStack::from(['s', 't', 'a', 'c', 'k']);

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

assert!(a == b);

Implementations

impl<T> MinStack<T>

pub fn new() -> MinStack<T>

Creates an empty stack.

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

Creates an empty stack with the specified capacity.

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

where T: Ord,

Pushes an element onto the top of the stack.

Example

use rust_dsa::MinStack;

let mut stack = MinStack::new();
stack.push(5);

assert_eq!(stack.pop(), Some(5));
assert_eq!(stack.pop(), None);

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

Removes the last element on the stack and returns it or None if the stack is empty.

Example

use rust_dsa::MinStack;

let mut stack = MinStack::from([5]);

assert_eq!(stack.pop(), Some(5));
assert_eq!(stack.pop(), None);

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

Returns a reference the last element on the stack or None if the stack is empty.

Example

use rust_dsa::MinStack;

let mut stack = MinStack::from(['a']);

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

stack.pop();

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

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

Returns the smallest element on the stack or None if the stack is empty.

Example

use rust_dsa::MinStack;

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

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

stack.pop();

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

stack.clear();

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

pub fn len(&self) -> usize

Returns the number of elements on the stack.

Example

use rust_dsa::MinStack;

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

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

stack.clear();

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

pub fn is_empty(&self) -> bool

Returns true if the stack is empty.

Example

use rust_dsa::MinStack;

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

assert!(!stack.is_empty());

stack.clear();

assert!(stack.is_empty());

pub fn clear(&mut self)

Clears the stack.

Example

use rust_dsa::MinStack;

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

assert!(!stack.is_empty());

stack.clear();

assert!(stack.is_empty());

Trait Implementations

impl<T: Clone> Clone for MinStack<T>

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

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T> Debug for MinStack<T>

where T: Debug,

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

Formats the value using the given formatter.

impl<T> Default for MinStack<T>

fn default() -> MinStack<T>

Returns the “default value” for a type.

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

where T: Ord,

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

Converts to this type from the input type.

impl<T> FromIterator<T> for MinStack<T>

where T: Ord,

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

Creates a value from an iterator.

impl<'a, T> IntoIterator for &'a MinStack<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 MinStack<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 MinStack<T>

where T: PartialEq,

fn eq(&self, other: &MinStack<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 MinStack<T>