«Последним зашёл — первым вышел», или что общего между программированием и поездкой в утреннем метро.
Если вы начинали изучать программирование, то наверняка слышали об ошибке переполнения стека. Той самой, в честь которой назвали известный айтишный сайт вопросов и ответов Stack Overflow. Пришло время разобраться, что вообще означает «стек», почему он может переполниться и чем это грозит.
Из этой статьи вы узнаете:
Что такое стек
Представьте себе детскую пирамидку, где кольца по очереди надеваются на штырёк. Кольца идут друг за другом: мы не можем добавить новые кольца в середину или основание пирамидки — только сверху. Если мы вдруг захотим разобрать пирамидку, сначала нужно снять верхнее кольцо, затем предыдущее и так далее, пока не дойдём до нижнего.
Так же устроен и стек: чем выше элемент находится в пирамиде, тем раньше его заберут. Этим стеки отличаются от очереди (queue) — структуры данных, где первым используется элемент, который появился раньше всех. Если очередь формируется возле кассы в «Пятёрочке», то стек — в забитом вагоне метро, где первым выходит тот, кто зашёл последним.
Если переложить нашу аналогию на язык компьютеров, получится несколько базовых команд, которые можно использовать со стеками:
- push — добавляет элемент на вершину стека.
- pop — удаляет элемент с вершины стека.
- peek — считывает элемент с вершины стека без его удаления.
- isEmpty — проверяет, пуст ли стек.
- size — возвращает количество элементов в стеке.
В зависимости от языка и способа реализации команды могут различаться, но этот список — база, без которой невозможно двигаться дальше.
Считается, что первым понятие стека ввёл в обиход ввёл Алан Тьюринг во время работы над прообразом современного компьютера. Позже эту идею запатентовали немецкие учёные Клаус Самельсон и Фридрих Л. Бауэр.
Где используются стеки
Частый сценарий использования стеков — реализация операции отмены в текстовых и графических редакторах. Например, нарисовали вы тень для кнопки в Figma — в стеке отмены появилась операция «Добавить тень». Если вы решите вернуть как было, компьютер быстро достанет последний элемент в стеке и ему не придётся перебирать всю хронологию ваших действий.
У этого есть и обратная сторона — чем дольше вы работаете над файлом, тем сильнее разрастается стек и тем больше он подъедает оперативки. Поэтому тот же Photoshop может начать тормозить после определённого количества операций. А если памяти мало изначально, система может выдавать ошибку переполнения стекового буфера.
Помимо имплементации отмены, стеки используются для массы других задач:
- Для хранения информации о вызовах функций и их локальных переменных.
- Для управления операциями в базах данных. Это может быть, например, откат транзакций или повтор операций.
- Для вычисления выражений, проверки скобок и выполнения других операций.
- Для управления вызовами системных функций и передачей параметров между приложениями и ядром операционной системы.
На некоторых из этих кейсов мы подробно остановимся чуть позже, а пока — разберёмся с реализациями стека.
Реализации стека
Так как стек — это чистая абстракция, для работы ему нужна реализация в виде конкретной структуры данных. Чаще всего стеки реализуют с помощью динамических массивов и связных списков. Разберём их подробнее.
Реализация с помощью динамического массива.
Динамическим называют массив, размер которого может увеличиваться или уменьшаться в процессе выполнения программы. Операции добавления (push) и удаления (pop) элементов производятся либо с конца, либо с начала массива.
Вот как выглядит создание стека с помощью списка на языке Python.
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
Реализация с помощью связанного списка.
Здесь стек представляет собой связанный список, где каждый узел содержит какие-то данные и указатель на предыдущий узел. При добавлении новый элемент становится вершиной стека, а при удалении на вершине оказывается предыдущий элемент.
Пример реализации стека с использованием связанного списка на Python
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
Что выбрать?
Зависит от задачи. Если вам важна эффективность при доступе к элементам и при этом стек имеет фиксированный размер или меняется редко, лучше выбрать динамический массив. Если же вам нужно менять размер стека и вы не знаете заранее его максимальную величину, связанный список может быть удобнее.
Стек вызовов
Стек вызовов — это структура данных, которая управляет вызовами функций во время выполнения программы. Звучит сложно, на деле — всё просто, следите за руками.
Когда компьютер выполняет программу и доходит до вызова какой-то функции, ему нужно ненадолго переключиться, чтобы эту самую функцию выполнить. Чтобы запомнить, где он остановился, компьютер сохраняет в памяти специальные закладки — так называемые точки перехода. Область памяти, где хранятся точки перехода, как раз и называется стеком вызовов.
В точке перехода хранится всё, чтобы компьютер быстро и безболезненно вернулся к выполнению основного кода: значения переменных, аргументы функций и адрес возврата — то место, куда компьютер должен перейти после окончания подпрограммы. Жизненная аналогия для точки перехода — это чекпойнт в игре: добежали, сохранились и можете пойти спокойно пить чай, пребывая в уверенности, что сможете начать с того же места.
Если внутри одной функции произойдёт вызов другой функции, история аналогичная: компьютер поставит на паузу выполнение первой, сохранит в стеке точку перехода, а затем перейдёт к выполнению второй. Этот принцип будет работать для любой степени вложенности функции, вплоть до рекурсии.
Чтобы было понятнее, изобразим весь этот процесс на схеме. Представим, что у нас есть программа с тремя функциями: первая вызывает вторую, вторая — третью и так далее.
Что такое переполнение стека
Чтобы стек не разрастался в памяти, ему задаётся конкретный размер — либо системой, либо самим программистом. Но если вызовов в программе будет слишком много, стек может внезапно переполниться — в этом случае программа аварийно завершит работу и выдаст ошибку о переполнении стека.
Случиться это может по разным причинам:
- Рекурсия большой глубины вложенности. При каждом витке рекурсии в стек добавляются новые элементы. Когда элементов бывает очень много, стек переполняется. В различных языках может быть разная глубина рекурсии, например в 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
Что запомнить
Давайте подытожим всё, что мы узнали из этой статьи:
- Стек — это способ хранения данных, работающий по принципу «последним пришёл, первым вышел». Он применяется в разных областях программирования и алгоритмов.
- Две наиболее распространённые реализации стека: с использованием динамического массива и с помощью связанного списка.
- Есть множество видов стеков, которые применяются в разных областях. Основные из них — стек вызовов и стек данных.
- Стек вызовов — это структура данных, которая управляет вызовами функций во время выполнения программы.
- Если программа пытается разместить на стеке больше данных, чем он может вместить, происходит переполнение стека. Это приводит к аварийному завершению работы программы и другим непредсказуемым последствиям.
- Стеки данных используются при вычислении выражений, обратной польской нотации, для обхода деревьев, графов и других целей.
Дерево — это структура, где есть несколько узлов, соединённых ветвями. Например, семья — это дерево: у каждого есть родители и дети.