MinMaxQ

/*
* Author : Nikhil Garg
* Date   : 2010-12-31
* A templatized MinMax Queue implementation.
* Provides O(1) insert, delete, fimnMin and findMax opertions.
* Assumption : all elements pushed in queue are different. This assumption can be
* relaxed after some extra book keeping code.
*
* I'm pre allocating space for queues. This can also be changed by replacing vectors with STL queues.
*
*/

#include<vector>
using namespace std;

template <class T>
class MinMaxQueue
{
    vector<T> Q, Qmax, Qmin;
    int qf, qmaxf, qminf, qb, qmaxb, qminb;

    public :

        MinMaxQueue(int N)
        {
            qf = qb = 0;       Q.resize(N);
            qmaxf = qmaxb = 0; Qmax.resize(N);
            qminf = qminb = 0; Qmin.resize(N);
        }

        void push(T v)
        {
            while( qmaxf < qmaxb && Qmax[qmaxb -1] < v) qmaxb--;
            while( qminf < qminb && Qmin[qminb -1] > v) qminb--;

            Q[qb++] = v;
            Qmax[qmaxb++] = v;
            Qmin[qminb++] = v;
        }

        T pop()
        {
            T v = Q[qf++];
            if (v == Qmax[qmaxf])   qmaxf ++;
            if (v == Qmin[qminf])   qminf ++;
            return v;
        }

        T front()   {  return Q[qf];        }
        T getMax()  {  return Qmax[qmaxf];  }
        T getMin()  {  return Qmin[qminf];  }

        int size()  {  return qb - qf;      }
};