Открыть сервис
Главная → Блог → Стек

Стек

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

Основные операции

Абстрактный тип «стек» обычно поддерживает следующий минимальный набор операций:

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

Операции push и pop выполняются за константное время O(1) в типичных реализациях (массив, связный список), так как доступ происходит только к одному концу структуры.

История термина

Термин «стек» (англ. stack — «стопка», «кипа») происходит от бытовой аналогии: элементы, подобно тарелкам в стопке, можно положить сверху или взять сверху, но нельзя извлечь элемент из середины, не сняв сначала все находящиеся над ним. В математике и информатике понятие стека впервые формализовано в трудах Алана Тьюринга в 1946 году в контексте теории автоматов. Практическая реализация в виде аппаратного стека появилась в архитектуре компьютеров в 1950-х годах, в частности в машинах с магазинной памятью (например, Burroughs B5000, 1961).

Виды стеков

LIFO-стек (классический)

Стандартная реализация, где удаление и вставка производятся строго с одного конца. Используется в большинстве языков программирования (например, std::stack в C++, Stack<T> в C#, list.append/list.pop в Python).

FIFO-стек (очередь)

Термин «стек» иногда ошибочно применяют к очередям, но правильный абстрактный тип для принципа «первым пришёл, первым ушёл» — очередь (queue). В рамках строгих определений стек всегда LIFO.

Двусторонний стек (double-ended stack, или deque)

Ограниченная модификация, где push и pop возможны с обоих концов. Полноценно реализуется в деке (double-ended queue), но не является классическим стеком.

Реверсивный стек

Разновидность, где возможно обращение порядка элементов (инвертирование) за линейное время. Применяется в некоторых трансляторах.

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

На основе массива

Статический массив фиксированного размера (или динамически расширяемый). Вершина стека задаётся индексом. Плюсы: быстрый доступ, маленькие накладные расходы. Минусы: ограничение по размеру или сложность перераспределения памяти. Пример на C:

```c

define MAX_STACK 100

int stack[MAX_STACK]; int top = -1;

void push(int val) { if (top >= MAX_STACK - 1) { / overflow / return; } stack[++top] = val; } int pop() { if (top < 0) { / empty / return -1; } return stack[top--]; } ```

На основе связного списка

Динамическая структура, где каждый элемент содержит указатель на предыдущий. Плюсы: безграничный размер (пока доступна память), лёгкое добавление/удаление. Минусы: больше памяти на указатели. Пример:

```c struct Node { int data; struct Node next; }; struct Node top = NULL;

void push(int val) { struct Node newNode = malloc(sizeof(struct Node)); newNode->data = val; newNode->next = top; top = newNode; } int pop() { if (top == NULL) return -1; struct Node temp = top; int val = temp->data; top = top->next; free(temp); return val; } ```

Аппаратный стек

В компьютерных архитектурах (x86, x86-64, ARM) стек реализован аппаратно через регистры ESP/RSP (указатель стека) и команды PUSH/POP. Используется для хранения адресов возврата, локальных переменных и контекста вызова функций. Стек растёт вниз (к меньшим адресам) на платформах x86.

Стек в языках высокого уровня

Во многих языках (Java, C#, Python, JavaScript) стек существует как встроенная структура (например, Stack в Java, ArrayDeque в качестве стека в Java) или как часть контейнерной библиотеки (STL в C++). Часто используется в комбинации с другими структурами.

Применение стека

Вычисление выражений

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

Системные вызовы и рекурсия

При вызове функции в память помещается запись активации (стековый кадр), содержащая адрес возврата, аргументы и локальные переменные. Рекурсия реализуется через стек вызовов; переполнение стека (stack overflow) возникает при слишком глубокой рекурсии.

Парсинг и языки программирования

Стеки используются в анализаторах (LR, LL) для проверки синтаксиса, в компиляторах и интерпретаторах. Пример — проверка корректности скобочных последовательностей (алгоритм: открывающая скобка — push, закрывающая — pop, если тип совпадает).

Управление отменой действий (Undo)

В редакторах, играх и пользовательских интерфейсах стек хранит последовательность действий. Операция Ctrl+Z выполняет pop последнего действия. Максимальная глубина отмены ограничена размером стека.

Обход графов (поиск в глубину)

DFS (Depth-First Search) может быть реализован либо рекурсивно (через стек вызовов), либо итеративно с явным стеком для хранения вершин для посещения.

В операционных системах

Стек используется для сохранения контекста прерываний, системных вызовов и многозадачности. Например, в ядре Linux каждый поток имеет собственный стек ядра.

Ограничения и особенности

  • Переполнение стека (stack overflow) — попытка добавить элемент в полностью заполненный стек фиксированного размера или при исчерпании памяти.
  • Опустошение стека (stack underflow) — попытка извлечь элемент из пустого стека; характерна для неправильно реализованных алгоритмов.
  • Аппаратный стек имеет фиксированный верхний предел (зависит от платформы и настроек линковщика).
  • Стеки не поддерживают произвольный доступ к элементам (только к вершине), поэтому неэффективны для поиска.

Примеры в реальной жизни

  • Стопка книг или журналов: последняя положенная книга берётся первой.
  • Система возврата в веб-браузере (кнопка «Назад»): история посещённых страниц организована как стек.
  • История командной строки (стрелка вверх для вызова предыдущих команд) часто реализуется на основе стека.

Математические и формальные свойства

Классический стек может быть описан как алгебраическая структура с операциями push и pop, подчиняющаяся аксиомам:

  1. Если стек S пуст, то pop(S) не определено.
  2. push(pop(push(S, x)), y) = push(S, y) (при условии корректного состояния).
  3. После последовательности операций LIFO гарантирует, что первый извлечённый элемент будет последним добавленным.

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

Критика и альтернативы

  • Для задач, где требуется двусторонний доступ, стек уступает дека (deque).
  • При большом количестве операций push/pop стек на основе массива может требовать перераспределения памяти (для динамических массивов), что приводит к амортизированным затратам.
  • В параллельных вычислениях классический стек небезопасен без синхронизации; существуют lock-free стеки (например, на основе CAS-операций).

Источники

  • Д. Кнут. «Искусство программирования», том 1: Основные алгоритмы. — М.: Вильямс, 2006.
  • Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. «Алгоритмы: построение и анализ». — М.: Вильямс, 2013.
  • A. V. Aho, J. D. Ullman. «Foundations of Computer Science». — Computer Science Press, 1992.
  • Документация языка C++ (std::stack) и Python (list as stack).
  • «Стек» в: Энциклопедия Википедия — свободная энциклопедия.

BFOmetr — база данных и аналитика по компаниям России.

На главную BFOmetr →

Похожие материалы