Простыми словами: что такое стек и как он устроен
2026-02-21 10:07 Diff
https://skillbox.ru/media/code/prostymi-slovami-chto-takoe-stek-i-kak-on-ustroen/

#статьи

  • 1 ноя 2023
  • 0

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

«Последним зашёл — первым вышел», или что общего между программированием и поездкой в утреннем метро.

Иллюстрация: Оля Ежак для Skillbox Media

Программист, консультант, специалист по документированию. Легко и доступно рассказывает о сложных вещах в программировании и дизайне.

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

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

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

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

Так же устроен и стек: чем выше элемент находится в пирамиде, тем раньше его заберут. Этим стеки отличаются от очереди (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

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

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

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

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

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

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

Шаг 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

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

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