Для чего нужен стек?

Что такое стек?

Стек (Stack) — это абстрактный тип данных, работающий по принципу LIFO (Last In, First Out), что означает «последним пришёл — первым вышел». Это структура, в которой добавление (операция push) и удаление (операция pop) элементов происходят только с одного конца, называемого вершиной (top) стека. Важно понимать, что стек — это концепция, которая может быть реализована на различных нижележащих структурах, чаще всего на массивах или связных списках.

Зачем нужен стек: ключевые применения

1. Управление вызовами функций и програмным стеком (Call Stack)

Это самый фундаментальный пример использования стека в программировании. Когда ваша программа выполняет вызов функции, система (компилятор или среда исполнения) использует стек для:

• Сохранения адреса возврата (куда вернуться после выполнения функции).
• Передачи аргументов функции.
• Выделения памяти под локальные переменные функции.

Каждый новый вызов функции создаёт новый стековый фрейм (stack frame) и помещает его на вершину стека. Когда функция завершает работу, её фрейм извлекается, и управление возвращается по сохранённому адресу.

func functionA() {
    let x = 10
    functionB() // 1. Адрес возврата и контекст functionA кладётся в стек
    print(x)    // 3. Управление вернулось сюда
}

func functionB() {
    let y = 20
    // 2. Адрес возврата и контекст functionB кладётся в стек поверх фрейма A
} // 2.1 Фрейм B уничтожается, вершиной стека снова становится фрейм A

2. Выражения и парсинг

• Вычисление выражений (особенно в постфиксной/польской нотации): Стек идеально подходит для парсинга и вычисления математических выражений. Операторы и операнды помещаются и извлекаются в строгом порядке.
• Проверка сбалансированности скобок: Классическая задача. При обходе строки открывающие скобки ({[ пушатся в стек, а при встрече закрывающей проверяется, соответствует ли она вершине стека.

func isBalanced(_ string: String) -> Bool {
    var stack = [Character]()
    let pairs: [Character: Character] = [')': '(', ']': '[', '}': '{']

    for char in string {
        if "([{".contains(char) {
            stack.append(char) // Push opening bracket
        } else if let opening = pairs[char] { // Found a closing bracket
            if stack.isEmpty || stack.removeLast() != opening {
                return false
            }
        }
    }
    return stack.isEmpty
}

3. Алгоритмы обхода графов и деревьев (Depth-First Search, DFS)

Стек является неотъемлемой частью поиска в глубину. При обходе дерева или графа дочерние узлы или смежные вершины помещаются в стек, что обеспечивает переход к самому глубокому, а не к ближайшему элементу.

class TreeNode {
    let value: Int
    var children: [TreeNode]
}

func dfsIterative(root: TreeNode) {
    var stack = [root]
    while !stack.isEmpty {
        let node = stack.removeLast() // Pop
        print(node.value)
        // Дочерние узлы добавляются в стек, следующий будет последний добавленный
        stack.append(contentsOf: node.children.reversed())
    }
}

4. Механизм отмены действий (Undo/Redo)

В приложениях стек — основа функций «Отменить» (Undo) и «Повторить» (Redo). Каждое действие пользователя (например, ввод текста) сохраняется в стеке undoStack. При команде «Отменить» состояние извлекается из undoStack и помещается в redoStack.

class TextEditor {
    private var undoStack = [String]() // Стек для отмены
    private var redoStack = [String]() // Стек для повтора
    private var currentText = ""

    func typeText(_ newText: String) {
        undoStack.append(currentText) // Push текущего состояния перед изменением
        currentText += newText
        redoStack.removeAll() // Новое действие очищает стек повтора
    }

    func undo() {
        guard let lastState = undoStack.popLast() else { return }
        redoStack.append(currentText) // Текущее состояние идёт в стек повтора
        currentText = lastState       // Восстанавливаем предыдущее
    }
}

5. Навигация в iOS (UINavigationController)

UINavigationController — это прямое и визуальное воплощение стека в iOS-разработке. Каждый новый экран (UIViewController) «пушится» на стек навигации, а при возврате — «попится» с его вершины.

let initialVC = MainViewController()
let navController = UINavigationController(rootViewController: initialVC)

// Добавление нового экрана (Push)
let detailVC = DetailViewController()
navController.pushViewController(detailVC, animated: true) // DetailVC помещается на вершину стека

// Возврат (Pop)
navController.popViewController(animated: true) // DetailVC удаляется с вершины стека

Почему именно стек? Преимущества

• Простота и эффективность: Операции push и pop выполняются за O(1), так как работают только с вершиной.
• Четкий порядок управления: LIFO гарантирует, что ресурсы освобождаются в строго обратном порядке их выделения, что критически важно для управления памятью и вызовами.
• Естественность для многих задач: Рекурсия, синтаксический анализ, навигация — эти процессы по своей природе стекообразны.

Таким образом, стек — это не просто академическая структура данных, а краеугольный камень компьютерной науки, который лежит в основе управления исполнением программ, реализации ключевых алгоритмов и создания интуитивно понятного пользовательского интерфейса в мобильных и десктопных приложениях. Его понимание обязательно для разработчика любого уровня.