Что такое стек и как он устроен

Мы постепенно осваиваем способы организации и хранения данных. Уже было про деревья, попробуем про стеки. Это для тех, кто хочет в будущем серьёзно работать в ИТ, потому что стек — одна из фундаментальных концепций, которая влияет на качество вашего кода, но не касается какого-то конкретного языка программирования. 

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

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

👉 Главный принцип работы стека — данные, которые попали в стек недавно, используются первыми. Чем раньше попал, тем позже используется. После использования элемент стека исчезает, и верхним становится следующий элемент.

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

Когда кому-то понадобится тарелка, он не будет брать её снизу или из середины — он возьмёт первую сверху, потом следующую и так далее. 

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

Реализация стека — это когда стек создают с помощью какого-то языка программирования. Каким бы он ни был, основные операции со стеком будут называться одинаково:

• push — добавить элемент в вершу стека,
• pop — удалить и вернуть элемент из вершины стека,
• peek (иногда top) — вернуть элемент из вершины стека без удаления,
• is_empty — проверить, пуст ли стек.

Для примера покажем, как может выглядеть реализация стека на Python. Чтобы было понятнее, мы добавили комментарии к каждой строке кода:

class Stack:
    # инициализиция стека с использованием списка
    def __init__(self):
        self.items = []

    # метод для добавления элемента в стек
    def push(self, item):
        # добавляем элемент в конец списка (вершина стека)
        self.items.append(item)

    # метод для удаления и возврата элемента с вершины стека
    def pop(self):
        # если стек не пуст
        if not self.is_empty():
            # удаляем и возвращаем элемент из конца списка
            return self.items.pop()
        # если стек пустой
        else:
            # выбрасываем исключение
            raise IndexError("Попытка удаления из пустого стека")

    # метод для возврата элемента с вершины стека без его удаления
    def peek(self):
        # если стек не пуст
        if not self.is_empty():
            # возвращаем последний элемент списка
            return self.items[-1]
        # если стек пустой
        else:
            raise IndexError("Попытка возврата из пустого стека")
            # Если стек пустой, выбрасываем исключение

    # метод для проверки, пуст ли стек
    def is_empty(self):
        # Возвращаем True, если список пустой, иначе False
        return len(self.items) == 0

    # метод для получения количества элементов в стеке
    def size(self):
        # возвращаем длину списка
        return len(self.items)

# пример использования стека
# создаем новый экземпляр стека
stack = Stack()

# добавляем элемент 1 в стек
stack.push(1)

# добавляем элемент 2 в стек
stack.push(2)

# добавляем элемент 3 в стек
stack.push(3)

# удаляем и выводим верхний элемент стека (3)
print(stack.pop())

# выводим верхний элемент стека (2) без его удаления
print(stack.peek())

# проверяем, пуст ли стек
print(stack.is_empty())

# выводим количество элементов в стеке (2)
print(stack.size())

Если запустить этот код, получим такой результат в консоли:

Стек вызовов

В программировании есть два вида стека — стек вызовов и стек данных. 

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

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

Допустим, у нас есть программа, внутри которой есть три функции, причём одна из них внутри вызывает другую. Нарисуем, чтобы было понятнее:

Программа запускается, потом идёт вызов синей функции. Она выполняется, и программа продолжает с того места, где остановилась. Потом выполняется зелёная функция, которая вызывает красную. Пока красная не закончит работу, все остальные ждут. Как только красная закончилась — продолжается зелёная, а после её окончания программа продолжает свою работу с того же места.

А вот как стек помогает это реализовать на практике:

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

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

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

Переполнение стека

Почти всегда стек вызовов хранится в оперативной памяти и имеет определённый размер. Если у вас будет много вложенных вызовов или рекурсия с очень большой глубиной вложенности, то может случиться такая ситуация:

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

Стек данных

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

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

Что дальше

А дальше поговорим про тип данных под названием «куча». Да, такой есть, и с ним тоже можно эффективно работать. Стей тюнед.