#codingexercise

Question: Define a queue in which we can get its maximum number with a function max. In this stack, the time complexity of max, push_back, and pop_front are all O(1).

Answer:

Public class QueueWithMax<T>{

Public class InternalData {

T number {get;set;}

Int index {get;set;}

}

Deque<InternalData> data;

Deque<InternalData> maximums;

Int currentIndex;

Public QueueWithMax(){

currentIndex = 0;

}

Public void push_back(T number) {

            While(maximums.empty == false && number >= maximum.back().number)

                        maximums.pop_back();

             InternalData idata = {number, currentIndex};

             data.push_back(internalData);

             maximums.push_back(internalData);

             ++currentIndex;

}

Public T pop_front(){

            If (maximums.empty())

                        Throw new exception(“queue is empty”);

            If (maximums.front().index == data.front().index)

                        Maximums.pop_front();

             Return Data.pop_front().number;

}

Public T max() const {

            If (maximums.empty())

                        Throw new exception(“queue is empty”);

            Return maximums.front().number;

}

}