Min Queue

Description:

是sliding windown maximum或者minimum的一部分。

Example:

Note

Idea:

用deque当辅助，两头都可以。

新elem进的时候，

while(!dequeMin.empty() && dequeMin.back()>x){
    dequeMin.pop_back();
}
dequeMin.push_back(x);

Code:

#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
#include <queue>

using namespace std;

class MinQueue{
public:
    void push(int x){
        queueData.push(x);
        while(!dequeMin.empty() && dequeMin.back()>x){
            dequeMin.pop_back();
        }
        dequeMin.push_back(x);
    }

    void pop(){
        int elem=queueData.front();
        queueData.pop();
        if(elem==dequeMin.front()){
            dequeMin.pop_front();
        }
    }

    bool empty(){
        return queueData.empty();
    }

    int front(){
        return queueData.front();
    }

    int getMin(){
        return dequeMin.front();
    }

    void viewDeque(){
        for(auto elem: dequeMin){
            cout<<elem<<' ';
        }
        cout<<endl;
    }

private:
    deque<int> dequeMin;
    queue<int> queueData;
};

int main(){
    MinQueue myMinQueue;

    myMinQueue.push(1);
    myMinQueue.viewDeque();
    myMinQueue.push(2);
    myMinQueue.viewDeque();
    myMinQueue.push(2);
    myMinQueue.viewDeque();
    myMinQueue.push(3);
    myMinQueue.viewDeque();
    myMinQueue.push(5);
    myMinQueue.viewDeque();
    myMinQueue.push(4);
    myMinQueue.viewDeque();

    while(!myMinQueue.empty()){
        cout<< myMinQueue.getMin() <<endl;
        myMinQueue.pop();
    }
}