Сортировка стека рекурсией: полный разбор

Как отсортировать стек, имея в распоряжении только операции push, pop и peek? Задача популярна на собеседованиях и проверяет понимание рекурсии. В этой статье мы разберём эффективный подход без использования массивов или других структур — только рекурсия и стек. Вы увидите, как элегантно решить задачу и не потерять баллы на интервью.

Постановка задачи

Дан стек целых чисел. Нужно отсортировать его так, чтобы наименьший элемент оказался на дне, а наибольший — на вершине. Разрешены только стандартные операции стека: push, pop, peek (top) и проверка на пустоту. Нельзя использовать дополнительные структуры данных, такие как массивы или списки.

Наивное решение и его недостатки

Первое, что приходит в голову — вытолкнуть все элементы в массив, отсортировать его и загрузить обратно в стек. Этот подход работает за O(N log N) по времени и O(N) по памяти, но нарушает условие задачи: мы используем дополнительный массив. На собеседовании такое решение покажет, что вы не поняли суть ограничений.

Оптимальное решение: рекурсия как хранилище

Вместо внешнего массива можно использовать стек вызовов рекурсии. Идея проста: удаляем верхний элемент, рекурсивно сортируем оставшийся стек, а затем вставляем удалённый элемент на правильную позицию. Этот метод не требует дополнительных структур — вся информация хранится в кадре стека вызовов.

Алгоритм sort_stack

Рекурсивная функция sort_stack:

• Если стек пуст — вернуться (базовый случай).
• Извлечь верхний элемент (top).
• Рекурсивно отсортировать оставшийся стек.
• Вызвать функцию insert, чтобы вставить top на правильное место.

Алгоритм insert

Вспомогательная функция insert:

• Если стек пуст или его верхний элемент <= вставляемому значению — просто положить значение сверху.
• Иначе: извлечь верхний элемент, рекурсивно вставить значение, затем вернуть извлечённый элемент обратно.

Это гарантирует, что после вставки стек остаётся отсортированным (наибольший наверху).

Реализация на Python

def sort_stack(st):
    # Базовый случай: пустой стек
    if not st:
        return
    # Извлекаем верхний элемент
    top = st.pop()
    # Рекурсивно сортируем оставшийся стек
    sort_stack(st)
    # Вставляем top на правильную позицию
    insert(st, top)

def insert(st, value):
    # Если стек пуст или вершина меньше или равна value — кладём value сверху
    if not st or st[-1] <= value:
        st.append(value)
        return
    # Иначе извлекаем верхний элемент
    top = st.pop()
    # Рекурсивно вставляем value
    insert(st, value)
    # Возвращаем извлечённый элемент обратно
    st.append(top)

Детальный разбор на примере

Рассмотрим стек (вершина справа): [3, 1, 4, 2]. Вызовем sort_stack:

1. pop 3, остаток [1,4,2]
2. sort_stack([1,4,2]) → pop 1, остаток [4,2]
3. sort_stack([4,2]) → pop 4, остаток [2]
4. sort_stack([2]) → pop 2, остаток []
5. sort_stack([]) → return
6. insert([], 2) → стек пуст → push 2 → [2]
7. insert([2], 4) → 2 <= 4 → push 4 → [2,4]
8. insert([2,4], 1) → 4 > 1: pop 4, insert([2],1), push 4
9. insert([2],1) → 2 > 1: pop 2, insert([],1), push 2
10. insert([],1) → push 1 → [1]
11. push 2 → [1,2]
12. push 4 → [1,2,4]
13. insert([1,2,4], 3) → 4 > 3: pop 4, insert([1,2],3), push 4
14. insert([1,2],3) → 2 <= 3 → push 3 → [1,2,3]
15. push 4 → [1,2,3,4]

Итоговый стек: [1,2,3,4] (вершина 4 — наибольший).

Почему рекурсия работает?

Рекурсия автоматически сохраняет извлечённые элементы в стеке вызовов. После сортировки меньшего стека мы вставляем каждый удалённый элемент на правильное место. Таким образом, не требуется дополнительной памяти, кроме стека вызовов глубиной O(N).

Анализ сложности

• Время: O(N²) — в худшем случае каждый вызов insert может проходить через все элементы.
• Память: O(N) — глубина рекурсии равна размеру стека.

Практический вывод

Теперь вы знаете, как сортировать стек без дополнительных структур. Потренируйтесь на похожих задачах: обращение стека, удаление среднего элемента, проверка сбалансированности скобок. На собеседовании используйте фразу: «Рекурсивно сортируем меньший стек, затем вставляем удалённый элемент на правильную позицию с помощью вспомогательной рекурсивной функции».

Популярные похожие задачи

• Сортировка стека
• Обращение стека
• Удаление среднего элемента стека
• Проверка сбалансированности скобок