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

При помощи очереди с нахождением максимума за 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).
Как все исправить?

Ответ

Попробуйте использовать std::vector::reserve() вместо std::vector::resize(). Но в push() вам нужно контроллировать верхний размер в любом случае.
Ваш поправленный пример, не могу оценить насколько он работающий: https://ideone.com/uF09OU