Набір стеків

Задача

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

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

Рішення

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

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

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

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

#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; };

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

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