Категорія: Стеки і черги

Відсортувати стек

Задача

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

Рішення

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

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