min-queue.rs

/*
# Queue with minimum

Implement a queue that can also tell what is the current minimum. **The implementation must have O(1) complexity for all calls.**
*/

use std::collections::VecDeque;

pub struct MinQueue<T> {
    val_stack: VecDeque<T>,
    min_stack: VecDeque<T>,
}

struct Generate<T>(fn() -> T);

impl<T> Copy for Generate<T> {}

impl<T> Clone for Generate<T> {
    fn clone(&self) -> Self {
        *self
    }
}

impl<T: Clone + Ord> MinQueue<T> {
    pub fn new() -> Self {
        MinQueue {
            val_stack: (VecDeque::new()),
            min_stack: (VecDeque::new()),
        }
    }

    pub fn push(&mut self, val: T) {
        self.val_stack.push_back(val.clone());
        while !self.min_stack.is_empty() && val.clone() < self.min_stack.back().unwrap().clone() {
            self.min_stack.pop_back();
        }

        self.min_stack.push_back(val.clone());
    }

    pub fn pop(&mut self) -> Option<T> {
        if self.val_stack.is_empty() {
            return None;
        }
        if self.min_stack.front().unwrap().clone() ==  self.val_stack.front().unwrap().clone() {
            self.min_stack.pop_front();
        }

        Some(self.val_stack.pop_front().unwrap().clone())
    }

    pub fn front(&self) -> Option<&T> {
        if self.val_stack.is_empty() {
            return None;
        }

        Some(&self.val_stack.front().unwrap())
    }

    pub fn min(&self) -> Option<&T> {
        if self.min_stack.is_empty() {
            return None;
        }
        Some(&self.min_stack.front().unwrap())
    }

    pub fn len(&self) -> usize {
        if self.val_stack.is_empty() {
            return 0;
        }

        self.val_stack.len()
    }

    pub fn is_empty(&self) -> bool {
        self.val_stack.is_empty()
    }
}