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

Задача

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

Рішення

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

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

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

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