Queue with push_rear(), pop_front() and get_min() in constant time
#include <iostream>
#include <queue>
using namespace std;
class myqueue {
private:
deque<int> q;
deque<int> minq;
public:
void push(int x) {
q.push_back(x);
if(minq.empty()) minq.push_back(x);
else {
while(!minq.empty() && minq.back() > x)
minq.pop_back();
minq.push_back(x);
}
}
void pop() {
if(q.empty()) return;
if(q.front() == minq.front())
minq.pop_front();
q.pop_front();
}
int getmin() {
if(minq.empty()) return -1;
return minq.front();
}
};
int main() {
myqueue *m = new myqueue;
m->push(12); cout<<m->getmin()<<endl;
m->push(5); cout<<m->getmin()<<endl;
m->push(10); cout<<m->getmin()<<endl;
m->pop();
m->pop();
cout<<m->getmin()<<endl;
}