Задача
Реалізувати стек у вигляді набору стеків. Коли розмір кожного зі стеків у колекції досягає певного вказаного числе створювати новий стек.
ДОдати операції для отримання елементу з вершини стеку, додавання елементу на вершину стеку та ортимання елементу з довільного стеку в наборі.
Рішення
Перед додаванням елементу у стек треба перевірити чи поточний стек вже не містить максимум елементів, і якщо так то додати новий стек у колекцію.
При вилученні елемента треба перевірити чи у останньому стеку залишилися елементи, і якщо ні то вилучити його.
При вилученні елемента з довільного стека треба взяти перший елемент з наступного стека і помістити його на вершину поточного (замість вилученого). Повіторити для усих наступних стеків.
Реалізація що використовує список списків:
#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;
};