Задача

Відсортувати стек за зростанням.

Рішення

Використаємо додатковий стек:

  1. Беремо черговий елемент з оригінального стеку
  2. Доки поточний елемент більше за верхній елемент допоміжного стеку переміщуємо елемент з вершини допоміжного стеку в оригінальний стек
  3. Поміщуємо елемент у допоміжний стек
  4. Якщо оригінальний стек не порожній переходимо до кроку 1.
template <class T> void sort_stack(stack<T>& s) { stack<T> s2; while (!s.empty()) { T x = s.top(); s.pop(); while (!s2.empty() && s2.top() < x) { s.push(s2.top()); s2.pop(); } s2.push(x); } s = s2; }

Задача

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