Стеки фиксированного размера и очередь с max за O(1)

#cpp #алгоритм

                    
При помощи очереди с нахождением максимума за O(1) надо обрабатывать миллиарды элементов.
Чтобы программа работала быстрее, нужно придать фиксированный размер двум стекам, при
помощи которых моделируется очередь. Как это сделать правильно? Мои попытки:

AmpQueue(int size){
    std::vector< std::pair > v_temp;
    v_temp.resize(size);
    std::stack< std::pair, std::vector< std::pair > > s_temp(std::move(v_temp));
    s1.swap(s_temp);
    s2.swap(s_temp);
}


А вот и сама программа:

#include 
#include 
#include 
#include 

// Класс для эффективного нахождения максимальной
// амплитуды на подотрезке
class AmpQueue{
private:
    std::stack< std::pair, std::vector< std::pair > > s1, s2;
public:
    AmpQueue();
    AmpQueue(int size){
        std::vector< std::pair > v_temp;
        v_temp.resize(size);
        std::stack< std::pair, std::vector< std::pair > > s_temp(std::move(v_temp));
        s1.swap(s_temp);
        s2.swap(s_temp);
    }
    // Загрузка нового элемента в очередь с поддержной нахождения максимума
    void push(int new_element){
        int max = s1.empty() ? new_element : std::max (new_element, s1.top().second);
        s1.push(std::make_pair(new_element, max));
    }
    // Удаляет элемент из очереди и возвращает значение удаленного элемента
    int pop(){
        if(s2.empty())
            while(!s1.empty()){
                int element = s1.top().first;
                s1.pop();
                int max = s2.empty() ? element : std::max(element, s2.top().second);
                s2.push(std::make_pair(element, max));
            }
        int result = s2.top().first;
        s2.pop();
        return result;
    }
    // Получение текущего максимума в очереди за O(1)
    int max(){
        if(s1.empty() || s2.empty())
            return s1.empty() ? s2.top().second : s1.top().second;
        else
            return std::max(s1.top().second, s2.top().second);
    }
    // Проверка: пуста ли очередь
    bool empty(){
        return (s1.empty() && s2.empty());
    }
    // Загрузка в очередь последовательности из n чисел
    void load(int n){
        int value;
        while(n--){
            std::cin >> value;
            push(value);
        }
    }
};

int main(){
    int n, current, maximum, element;

    std::cin.sync_with_stdio(false);
    std::cin >> n;
    AmpQueue q(n);

    // Загрузим в очередь первые n значение амплитуды
    q.load(n);
    // Выведем текущий максимум
    std::cout << q.max() << std::endl;

    // Загружаем следующий элемент последовательности и ищем максимум
    std::cin >> current;
    while(current != -1){
        q.pop();
        q.push(current);
        std::cout << q.max() << std::endl;
        std::cin >> current;
    }
}


Программа сначала крашилась при запуске, а после исправлений стала выдавать одни
и те же числа. Возможно, этот код совсем плохой, потому что вчера я редактировал его
уже только на идеоне. Поэтому показываю код на идеоне:

https://ideone.com/bJUpwL

Предполагаю, что проблема в том, что два стека уже заполнены нулевыми парами и имеют
размер n, поэтому при добавлении новых элементов они укладываются сверху на существующие
нулевые элемента. Из-за этого алгоритм работает неправильно (точнее, из-за условия empty). 

Как все исправить?
    

Ответы

Ответ 1

Попробуйте использовать std::vector::reserve() вместо std::vector::resize(). Но в
push() вам нужно контроллировать верхний размер в любом случае.

Ваш поправленный пример, не могу оценить насколько он работающий: https://ideone.com/uF09OU