Простыми словами: что такое стек и как он устроен

Если вы начинали изучать программирование, то наверняка слышали об ошибке переполнения стека. Той самой, в честь которой назвали известный айтишный сайт вопросов и ответов Stack Overflow. Пришло время разобраться, что вообще означает «стек», почему он может переполниться и чем это грозит.

Из этой статьи вы узнаете:

• Что такое стек
• Где он используется
• Какие у него есть реализации
• Что такое стек вызовов
• Почему он может переполниться
• Что такое стек данных
• Что запомнить

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

Стек (stack) — это способ организации данных в памяти компьютера. Он работает по принципу «последним пришёл, первым вышел» (last in first out, LIFO). Это значит, что последний элемент, добавленный в стек, будет взят из него первым. Добавлять новые элементы и удалять существующие из стека можно только с одного конца, который называется вершиной.

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

Так же устроен и стек: чем выше элемент находится в пирамиде, тем раньше его заберут. Этим стеки отличаются от очереди (queue) — структуры данных, где первым используется элемент, который появился раньше всех. Если очередь формируется возле кассы в «Пятёрочке», то стек — в забитом вагоне метро, где первым выходит тот, кто зашёл последним.

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

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

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

Где используются стеки

Частый сценарий использования стеков — реализация операции отмены в текстовых и графических редакторах. Например, нарисовали вы тень для кнопки в Figma — в стеке отмены появилась операция «Добавить тень». Если вы решите вернуть как было, компьютер быстро достанет последний элемент в стеке и ему не придётся перебирать всю хронологию ваших действий.

У этого есть и обратная сторона — чем дольше вы работаете над файлом, тем сильнее разрастается стек и тем больше он подъедает оперативки. Поэтому тот же Photoshop может начать тормозить после определённого количества операций. А если памяти мало изначально, система может выдавать ошибку переполнения стекового буфера.

Помимо имплементации отмены, стеки используются для массы других задач:

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

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

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

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

Реализация с помощью динамического массива.

Динамическим называют массив, размер которого может увеличиваться или уменьшаться в процессе выполнения программы. Операции добавления (push) и удаления (pop) элементов производятся либо с конца, либо с начала массива.

class Stack:
    # Конструктор для инициализации стека
    def __init__(self):
        self.items = []
    # Функция для проверки того, есть ли в стеке элементы
    def is_empty(self):
        return len(self.items) == 0


    # Функция для добавления элемента в стек
    def push(self, item):
        self.items.append(item)
    # Функция для удаления верхнего элемента из стека
    def pop(self):
        if not self.is_empty():
            return self.items.pop()
        else:
            print("Стек пуст. Мы не можем удалить из него элемент.")
    # Функция для чтения верхнего элемента стека
    def peek(self):
        if not self.is_empty():
            return self.items[-1]
        else:
            print("Стек пуст. Мы не можем прочитать верхний элемент.")
    # Функция, возвращающая размер стека
    def size(self):
        return len(self.items)

stack = Stack()
print(stack.is_empty())  # True


stack.push(1)
stack.push(2)
stack.push(3)
print(stack.size())     # 3
print(stack.peek())     # 3


item = stack.pop()
print(item)             # 3
print(stack.size())     # 2
print(stack.is_empty()) # False

Реализация с помощью связанного списка.

Здесь стек представляет собой связанный список, где каждый узел содержит какие-то данные и указатель на предыдущий узел. При добавлении новый элемент становится вершиной стека, а при удалении на вершине оказывается предыдущий элемент.

class Node:
    # Конструктор для инициализации узла
    def __init__(self, data):
        self.data = data
        self.next = None


class Stack:
    # Конструктор для инициализации стека
    def __init__(self):
        self.top = None
   
    # Функция для добавления нового узла
    def push(self, data):
        new_node = Node(data)
        new_node.next = self.top
        self.top = new_node
   
    # Функция для удаления верхнего элемента
    def pop(self):
        if not self.is_empty():
            popped = self.top
            self.top = self.top.next
            popped.next = None
            return popped.data
        else:
            print("Стек пуст. Мы не можем удалить из него элемент.")
       
    # Функция для чтения верхнего элемента
    def peek(self):
        if not self.is_empty():
            return self.top.data
        else:
            print("Стек пуст. Мы не можем прочитать верхний элемент.")


    # Функция для проверки, есть ли в стеке элементы
    def is_empty(self):
        return self.top is None


    # Функция, возвращающая размер стека
    def size(self):
        count = 0
        current = self.top
        while current:
            count += 1
            current = current.next
        return count

stack = Stack()
print(stack.is_empty())  # True


stack.push(1)
stack.push(2)
stack.push(3)
print(stack.size())     # 3
print(stack.peek())     # 3


item = stack.pop()
print(item)             # 3
print(stack.size())     # 2
print(stack.is_empty()) # False

Что выбрать?

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

Стек вызовов

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

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

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

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

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

Шаг 1. Компьютер выполняет основную программу и доходит до вызова функции 1. Он прерывает выполнение основной программы, помещает адрес возврата в стек и переходит к выполнению функции 1.

Шаг 2. Компьютер выполняет функцию 1 и доходит до вызова функции 2. Он прерывает выполнение функции 1, помещает её адрес возврата в стек и выполняет функцию 2.

Шаг 3. Компьютер заканчивает выполнение функции 2, считывает и удаляет с вершины стека адрес возврата функции 1. Затем он переходит к функции 1 и продолжает её выполнение с инструкции, находящейся по адресу возврата.

Шаг 4. Компьютер заканчивает выполнение функции 1, считывает и удаляет с вершины стека адрес возврата основной программы. Затем он переходит к основной программе и продолжает её выполнение с указанного адреса. Стек полностью очищается до следующего вызова.

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

Чтобы стек не разрастался в памяти, ему задаётся конкретный размер — либо системой, либо самим программистом. Но если вызовов в программе будет слишком много, стек может внезапно переполниться — в этом случае программа аварийно завершит работу и выдаст ошибку о переполнении стека.

Случиться это может по разным причинам:

• Рекурсия большой глубины вложенности. При каждом витке рекурсии в стек добавляются новые элементы. Когда элементов бывает очень много, стек переполняется. В различных языках может быть разная глубина рекурсии, например в Python она ограничена примерно 3000 вызовов.
• Бесконечные циклы, которые тоже приводят к накоплению данных в стеке. Вот пример бесконечного цикла на Python, который приводит к переполнению стека вызовов:

def infinite_loop():
    while True:
        pass

# Вызываем бесконечный цикл
infinite_loop()

• Огромные массивы или другие структуры в программах.

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

Стеки данных

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

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

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

Другой кейс — вычисление выражений в обратной польской нотации (ОПН). Это такие выражения, в которых сначала пишутся числа, а потом знаки операций. Например, 2+ 3∗4 будет записано как 2 3 4 ∗ +. Идея в том, чтобы создать алгоритм, который будет сначала «откладывать» числа в стек, а как доберётся до знаков операций — достанет их оттуда и проведёт вычисления.

Для самых стойких — вот как это реализуется с помощью Python:

import operator

OPERATORS = {'+': operator.add, '-': operator.sub, '*': operator.mul, '/': operator.truediv} # Создаём словарь, содержащий арифметические операции и их обозначения

def polsk(strok):

    stack = [] # Создаём стек
    lst = strok.split()


    for i in lst:    # Перебираем элементы списка
        if i.isdigit():
            stack.append(i)  # Если элемент — число, то помещаем его в стек      
        else:
            a, b = stack.pop(), stack.pop() # Считываем в переменные a и b два последних элемента стека и удаляем их из стека
            stack.append(OPERATORS[i](int(a), int(b))) # Выполняем над ними операцию и результат помещаем в стек
           
    return stack.pop()

print(polsk('11 26 33 + +'))   # 70

Что запомнить

Давайте подытожим всё, что мы узнали из этой статьи:

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