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

Задача

Черга – структура даних організована по принципу 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; };

Набір стеків

Задача

Реалізувати стек у вигляді набору стеків. Коли розмір кожного зі стеків у колекції досягає певного вказаного числе створювати новий стек.

ДОдати операції для отримання елементу з вершини стеку, додавання елементу на вершину стеку та ортимання елементу з довільного стеку в наборі.

Рішення

Перед додаванням елементу у стек треба перевірити чи поточний стек вже не містить максимум елементів, і якщо так то додати новий стек у колекцію.

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

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

Реалізація що використовує список списків:

#include <list> using namespace std; template <class T> class SetOfStacks { public: typedef list<T> InnerStack; SetOfStacks(int stackSize) : m_stackSize(stackSize) { } ~SetOfStacks() { for (list<InnerStack*>::const_iterator it = m_stacks.begin(); it != m_stacks.end(); ++it) { delete *it; } } void push(T x) { if (m_stacks.size() == 0) { m_stacks.push_back(new InnerStack()); } if (m_stacks.back()->size() == m_stackSize) { m_stacks.push_back(new InnerStack()); } InnerStack* currentStack = m_stacks.back(); currentStack->push_back(x); } T pop() { T x; if (m_stacks.size() > 0) { InnerStack* currentStack = m_stacks.back(); x = currentStack->back(); currentStack->pop_back(); if (currentStack->size() == 0) { delete currentStack; m_stacks.pop_back(); } } return x; } T popAt(int stack) { T x; if (stack < m_stacks.size()) { list<InnerStack*>::const_iterator it = m_stacks.begin(); for (int i = 0; i != stack; ++it, ++i); InnerStack* stackAt = *it; x = stackAt->back(); stackAt->pop_back(); for (list<InnerStack*>::const_iterator itNext = it; ++itNext != m_stacks.end(); ++it) { InnerStack* stackNext = *itNext; T move = stackNext->front(); stackNext->pop_front(); InnerStack* stackCurrent = *it; stackCurrent->push_back(move); } } InnerStack* currentStack = m_stacks.back(); if (currentStack->size() == 0) { delete currentStack; m_stacks.pop_back(); } return x; } private: list<InnerStack*> m_stacks; int m_stackSize; };