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();
}
}