sundeepblue
2/11/2014 - 9:01 PM

Queue with push_rear(), pop_front() and get_min() in constant time

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