Что такое Stack?

Что такое стек (Stack) в программировании?

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

Ключевые характеристики стека

Основные операции и свойства стека:

• Добавление элемента (Push) — операция помещения нового элемента на верхушку стека.
• Удаление элемента (Pop) — операция извлечения и удаления элемента с верхушки стека.
• Просмотр верхушки (Peek/Top) — операция получения значения верхнего элемента без его удаления.
• Проверка на пустоту (IsEmpty) — проверка, содержит ли стек элементы.
• Размер (Size) — получение текущего количества элементов в стеке.

Важно понимать, что доступ к элементам стека возможен только через его верхушку. Нельзя напрямую получить или изменить элемент в середине стека без предварительного извлечения всех элементов, находящихся над ним.

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

В Go стек не является встроенной структурой данных, но его легко реализовать с использованием срезов (slices) или связных списков. Наиболее распространён и эффективен подход на основе среза.

Пример реализации на основе среза

// Stack представляет собой стек целых чисел.
type Stack struct {
    items []int
}

// Push добавляет значение на верхушку стека.
func (s *Stack) Push(item int) {
    s.items = append(s.items, item)
}

// Pop удаляет и возвращает значение с верхушки стека.
// Возвращает false, если стек пуст.
func (s *Stack) Pop() (int, bool) {
    if len(s.items) == 0 {
        return 0, false
    }
    index := len(s.items) - 1
    item := s.items[index]
    s.items = s.items[:index] // Удаляем последний элемент
    return item, true
}

// Peek возвращает значение с верхушки стека без удаления.
func (s *Stack) Peek() (int, bool) {
    if len(s.items) == 0 {
        return 0, false
    }
    return s.items[len(s.items)-1], true
}

// IsEmpty проверяет, пуст ли стек.
func (s *Stack) IsEmpty() bool {
    return len(s.items) == 0
}

// Size возвращает текущее количество элементов в стеке.
func (s *Stack) Size() int {
    return len(s.items)
}

// Пример использования
func main() {
    var stack Stack

    stack.Push(10)
    stack.Push(20)
    stack.Push(30)

    if top, ok := stack.Peek(); ok {
        fmt.Printf("Верхушка стека: %d\n", top) // Вывод: 30
    }

    fmt.Printf("Размер стека: %d\n", stack.Size()) // Вывод: 3

    for !stack.IsEmpty() {
        if item, ok := stack.Pop(); ok {
            fmt.Printf("Извлечено: %d\n", item)
        }
    }
    // Вывод:
    // Извлечено: 30
    // Извлечено: 20
    // Извлечено: 10
}

Практическое применение стека в Go-разработке

1. Управление вызовами функций и памятью (Call Stack). Самое известное применение — стек вызовов программы. При каждом вызове функции в стек помещается её контекст (фрейм): аргументы, локальные переменные и адрес возврата. Когда функция завершает работу, её фрейм извлекается из стека, и управление возвращается по адресу возврата. Именно это обеспечивает вложенность и правильный порядок выполнения функций.

2. Алгоритмы и задачи:

    *   **Парсинг и валидация выражений**: проверка сбалансированности скобок `()`, `[]`, `{}`, конвертация инфиксных выражений в постфиксные (польскую нотацию) и их вычисление.
    *   **Обход графов и деревьев**: реализация **нерекурсивного (итеративного) поиска в глубину (DFS)** с использованием стека для хранения вершин.
    *   **Отмена действий (Undo)**: например, в текстовом редакторе каждое действие можно помещать в стек, чтобы откатывать их в обратном порядке.
    *   **История браузера**: кнопки «Назад» и «Вперёд» часто реализуются с использованием двух стеков.

1. Синтаксический анализ и компиляция: стеки используются для разбора синтаксических конструкций, управления областями видимости переменных и промежуточными результатами.

Стек вызовов (Call Stack) в деталях

Рассмотрим на простом примере, почему стек — идеальная структура для управления вызовами:

func main() {
    a := 1
    result := double(addOne(a)) // Вызовы вложенных функций
    fmt.Println(result)
}

func addOne(x int) int {
    return x + 1
}

func double(x int) int {
    return x * 2
}

Последовательность работы стека вызовов:

1. В начале выполняется main(). В стек помещается её фрейм.
2. Внутри main() вызывается addOne(a). Фрейм addOne кладётся поверх фрейма main. Теперь main "приостановлена".
3. addOne завершается, возвращает значение 2. Её фрейм извлекается из стека. Управление возвращается в main именно в ту точку, откуда был сделан вызов.
4. Далее вызывается double(2). Её фрейм помещается в стек.
5. double завершается, её фрейм извлекается.
6. Наконец, завершается main, её фрейм извлекается, программа завершена.

Эта модель LIFO идеально соответствует вложенной природе вызовов функций: последняя вызванная функция (double) завершается первой, затем — предпоследняя (addOne), и так далее, до самой первой (main).

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