入ってる中の最大の値をO(1)で返すデータ構造。

max_queue.cpp

#include <list>

template <typename T>
struct max_queue {
    max_queue():queue_(),max_(){}
    void enqueue(const T& n){
        queue_.push_back(n);
        const T& new_item = queue_.back();
        while(!max_.empty() && *max_.back() < new_item){
            max_.pop_back();
        }
        max_.push_back(&new_item);
    }
    T dequeue(){
        if(queue_.empty()){ throw std::exception(); }
        const T& deleting_item = queue_.front();
        const T ans = queue_.front(); // copy
        if(max_.front() == &deleting_item){
            max_.pop_front();
        }
        queue_.pop_front();
        return ans;
    }
    const T& max()const{
        if(max_.empty()){ throw std::exception(); }
        return *max_.front();
    }
private:
    std::list<T> queue_;
    std::list<const T*> max_;
};

#include <assert.h>
#include <iostream>
int main(void){
    max_queue<int> q;
    q.enqueue(1); assert(q.max()==1);
    q.enqueue(3); assert(q.max()==3);
    q.enqueue(5); assert(q.max()==5);
    q.enqueue(2); assert(q.max()==5);
    q.enqueue(7); assert(q.max()==7);
    q.enqueue(4); assert(q.max()==7);
    q.enqueue(1); assert(q.max()==7);
    q.enqueue(2); assert(q.max()==7);
    q.enqueue(1); assert(q.max()==7);
    assert(q.dequeue()==1); assert(q.max()==7);
    assert(q.dequeue()==3); assert(q.max()==7);
    assert(q.dequeue()==5); assert(q.max()==7);
    assert(q.dequeue()==2); assert(q.max()==7);
    assert(q.dequeue()==7); assert(q.max()==4);
    assert(q.dequeue()==4); assert(q.max()==2);
    assert(q.dequeue()==1); assert(q.max()==2);
    assert(q.dequeue()==2); assert(q.max()==1);
    assert(q.dequeue()==1);
}