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

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

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

Основные операции

У стека есть две ключевые операции, которые обычно реализуются за константное время O(1):

1. push (положить) — добавляет новый элемент на вершину стека.
2. pop (снять) — удаляет и возвращает элемент с вершины стека.

Также часто используются вспомогательные операции:

• peek (или top) — возвращает элемент с вершины стека, не удаляя его.
• isEmpty — проверяет, пуст ли стек.
• count (или size) — возвращает количество элементов в стеке.

Реализация стека

Стек можно реализовать на основе массива (Array) или связного списка (LinkedList). В iOS-разработке на Swift чаще всего используется массив, так как он предоставляет эффективные операции добавления и удаления с конца.

Пример реализации стека на Swift:

struct Stack<Element> {
    // В основе стека — массив
    private var storage: [Element] = []
    
    // Добавление элемента (push)
    mutating func push(_ element: Element) {
        storage.append(element)
    }
    
    // Удаление и возврат верхнего элемента (pop)
    @discardableResult
    mutating func pop() -> Element? {
        return storage.popLast()
    }
    
    // Просмотр верхнего элемента без удаления (peek/top)
    func peek() -> Element? {
        return storage.last
    }
    
    // Проверка на пустоту
    var isEmpty: Bool {
        return storage.isEmpty
    }
    
    // Количество элементов
    var count: Int {
        return storage.count
    }
}

Использование:

var bookStack = Stack<String>()
bookStack.push("Война и мир")
bookStack.push("Мастер и Маргарита")
bookStack.push("1984")

print(bookStack.peek()) // Optional("1984")
print(bookStack.pop())  // Optional("1984")
print(bookStack.pop())  // Optional("Мастер и Маргарита")
print(bookStack.isEmpty) // false

Применение стека в iOS-разработке

• Управление памятью и вызов функций: Это фундаментальное применение на уровне компилятора. Стек вызовов (call stack) хранит информацию об активных подпрограммах (функциях, методах). Каждый вызов метода помещает в стек новый стековый фрейм, содержащий локальные переменные, параметры и адрес возврата. Когда метод завершается, его фрейм удаляется, и управление возвращается по адресу из предыдущего фрейма.

• UINavigationController: Классический пример из UIKit. Контроллеры навигации хранят свои viewControllers именно в стеке. При вызове pushViewController(_:animated:) новый контроллер помещается на вершину стека и отображается. Метод popViewController(animated:) удаляет текущий контроллер с вершины, возвращая пользователя к предыдущему.

  // В основе UINavigationController лежит стек (массив) контроллеров
  // navigationController.viewControllers — это массив (стек) UIViewController'ов
  

• Отмена операций (Undo/Redo): Многие приложения (например, графические редакторы) используют два стека: один для отменённых действий, другой для повторных.

• Алгоритмы и парсинг:

    *   Проверка сбалансированности скобок в выражении.
    *   Преобразование выражений (инфиксная в постфиксную запись).
    *   Алгоритм обхода графа в глубину (DFS).

• Рекурсия: Любая рекурсивная функция неявно использует системный стек вызовов. При глубокой рекурсии существует риск переполнения стека (stack overflow).

Ключевые характеристики и сложность операций

• Временная сложность: Операции push, pop и peek в правильно реализованном стеке выполняются за O(1).
• Пространственная сложность: O(n), где n — количество элементов.
• Ограниченный доступ: Стек — структура данных с ограниченным доступом. Нет возможности напрямую получить доступ к элементам в середине или в начале (в отличие от массива или очереди). Это既是 ограничение, так и гарантия целостности данных в определённых сценариях.

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