Чергу на основі двох стеків

Задача

Черга – структура даних організована по принципу FIFO (First In First Out) – перший зайшов, перший вийшов.

Реалізувати чергу з використанням двох стеків як допоміжних структур.

Рішення

Рішення доволі просте – у першому стеку елементи містяться у зворотньому порядку. Цей стек використовується для додавання. Другий чтек для зчитування.

При необхідності зчитування треба перекласти есі елементи з першого стеку у другий (тепер вони у правильному порядку) і повернути елемент з вершини.

Щоб не перекладати увесь стекпри кожній операції можна зробити наступну оптимізацію. При зчитуванні елемента якщо другий стек не порожній то поернути елемент з нього. Інакше перекласти усі елементи з першого стека у другий і повернути елемент з вершини другого стеку.

template <class T> class QueueOn2Stacks { public: QueueOn2Stacks() {} void add(T x) { m_s1.push(x); } T remove() { T x; if (m_s2.size() != 0) { x = m_s2.top(); m_s2.pop(); return x; } while (m_s1.size() != 0) { m_s2.push(m_s1.top()); m_s1.pop(); } x = m_s2.top(); m_s2.pop(); return x; } private: stack<T> m_s1; stack<T> m_s2; };

Залишити відповідь

Зайти з допомогою: