Стек
Последнее обновление
У стека ровно один открытый конец. Значение кладут на вершину (push), а снимают тоже с вершины (pop), поэтому последнее добавленное значение всегда выходит первым. Именно это и означает LIFO, и в этом вся суть: добраться до середины, не сняв всё, что лежит сверху, невозможно. Нажмите «воспроизвести» выше и посмотрите, как столбик растёт с каждым добавлением и уменьшается с того же конца при каждом снятии.
Ограничение и есть смысл структуры. Поскольку обе операции трогают только вершину, каждая из них выполняется за O(1), каким бы высоким ни стал стек, и именно эта предсказуемость сделала стек опорой очень многого: стек вызовов, на котором работает рекурсия, история отмены действий в редакторе, проверка парности скобок в парсере и явный стек, который превращает рекурсивный поиск в глубину в цикл. Поменяйте конец, с которого удаляют, и получится очередь.
Временная и пространственная сложность
Для обычного стека на массиве или на связном списке:
| Операция | Сложность | Примечания |
|---|---|---|
| Push (добавление) | O(1) | На динамическом массиве амортизированно O(1), так как он изредка меняет размер. |
| Pop (извлечение) | O(1) | Всегда верхний элемент, поэтому ничего сдвигать не нужно. |
| Peek (просмотр вершины) | O(1) | Прочитать верхнее значение, не снимая его. |
| Поиск | O(n) | Стек нужен не для этого: придётся снимать значения одно за другим. |
| Память | O(n) | По одной ячейке на каждое хранимое значение. |
Шаг за шагом
| Шаг | Что происходит |
|---|---|
| 1 | Стек начинается пустым, вершина не указывает ни на что. |
| 2 | Push записывает значение в позицию вершины и поднимает вершину на единицу. |
| 3 | Каждое следующее добавление ложится прямо над предыдущим значением. |
| 4 | Pop читает значение на вершине, а затем опускает вершину на единицу. |
| 5 | Возвращается всегда то значение, которое положили последним. |
| 6 | Снять значение с пустого стека нельзя: это ошибка, которую называют опустошением стека (stack underflow), поэтому реальный код сначала проверяет is_empty(). |
Разобранный пример
Добавляем 3, 7, 5, а затем опустошаем стек:
| Операция | Стек (снизу вверх) | Возвращает |
|---|---|---|
push(3) | [3] | ничего |
push(7) | [3, 7] | ничего |
push(5) | [3, 7, 5] | ничего |
pop() | [3, 7] | 5, самое новое значение |
pop() | [3] | 7 |
pop() | [] | 3, самое старое значение, последним |
Когда использовать стек
| Используйте, когда | Избегайте, когда |
|---|---|
| Вам нужен сначала самый свежий элемент: отмена действий, кнопка «назад», проверка скобок | Вам нужен сначала самый старый элемент, для этого есть очередь |
| Вы превращаете рекурсивный алгоритм в итеративный | Вам нужно искать или обращаться по индексу в середину данных |
| Вы разбираете вложенные структуры: выражения, JSON или HTML | Многим читателям нужен произвольный доступ, и тогда лучше подойдут массив или словарь |
Вам нужны гарантированные вставка и удаление за O(1) без перебалансировки | Данные должны храниться в отсортированном порядке, для чего подойдут куча или дерево |
Код Stack
Чистая, готовая к запуску реализация Stack на Python, JavaScript, Java, C++, C. Выберите язык, скопируйте код или откройте его уже загруженным в плейграунде Coddy.
Код Stack на Python
Python
1stack = []2
3# Push three values onto the top4for value in [3, 7, 5]:5 stack.append(value)6 print(f"push {value} -> {stack}")7
8# Pop them back off: last in, first out9while stack:10 value = stack.pop()11 print(f"pop {value} -> {stack}")12
13print("empty:", len(stack) == 0)Код Stack на JavaScript
JavaScript
1const stack = [];2
3// Push three values onto the top4for (const value of [3, 7, 5]) {5 stack.push(value);6 console.log(`push ${value} ->`, stack);7}8
9// Pop them back off: last in, first out10while (stack.length > 0) {11 const value = stack.pop();12 console.log(`pop ${value} ->`, stack);13}14
15console.log('empty:', stack.length === 0);Код Stack на Java
Java
1import java.util.ArrayDeque;2import java.util.Deque;3
4public class Main {5 public static void main(String[] args) {6 Deque<Integer> stack = new ArrayDeque<>();7
8 // Push three values onto the top9 for (int value : new int[] {3, 7, 5}) {10 stack.push(value);11 System.out.println("push " + value + " -> " + stack);12 }13
14 // Pop them back off: last in, first out15 while (!stack.isEmpty()) {16 int value = stack.pop();17 System.out.println("pop " + value + " -> " + stack);18 }19
20 System.out.println("empty: " + stack.isEmpty());21 }22}Код Stack на C++
C++
1#include <iostream>2#include <stack>3
4int main() {5 std::stack<int> stack;6
7 // Push three values onto the top8 for (int value : {3, 7, 5}) {9 stack.push(value);10 std::cout << "push " << value << " -> size " << stack.size() << "\n";11 }12
13 // Pop them back off: last in, first out14 while (!stack.empty()) {15 int value = stack.top();16 stack.pop();17 std::cout << "pop " << value << " -> size " << stack.size() << "\n";18 }19
20 std::cout << "empty: " << std::boolalpha << stack.empty() << "\n";21 return 0;22}Код Stack на C
C
1#include <stdio.h>2
3#define CAP 164
5int stack[CAP];6int top = 0; /* index of the next free slot */7
8int main(void) {9 int values[3] = {3, 7, 5};10
11 /* Push three values onto the top */12 for (int i = 0; i < 3; i++) {13 stack[top++] = values[i];14 printf("push %d -> size %d\n", values[i], top);15 }16
17 /* Pop them back off: last in, first out */18 while (top > 0) {19 int value = stack[--top];20 printf("pop %d -> size %d\n", value, top);21 }22
23 printf("empty: %d\n", top == 0);24 return 0;25}Частые вопросы о стеке
Что означает LIFO?
Last in, first out, то есть последним пришёл, первым вышел: значение, добавленное последним, снимается первым. Обычная картинка для этого, стопка тарелок: вы берёте ту, которую только что положили, а не самую нижнюю. Очередь работает по противоположному правилу, FIFO.
Чем стек отличается от очереди?
Только концом, с которого удаляют. Обе структуры добавляют с одного конца за
O(1); стек удаляет с того же конца (LIFO), а очередь с противоположного (FIFO). Всё остальное, включая таблицу сложности выше, совпадает.Какие основные операции у стека?
push кладёт значение на вершину, pop снимает верхнее значение и возвращает его, peek (иногда top) читает вершину, не снимая её, а is_empty сообщает, осталось ли что-нибудь. Все четыре выполняются за O(1).Что такое переполнение стека?
Это добавление на стек, в котором больше нет места. Классический пример: стек вызовов. Каждый вызов функции кладёт на него кадр, поэтому рекурсия, которая никогда не доходит до базового случая, кладёт кадры до тех пор, пока не упрётся в лимит стека среды выполнения, и программа падает. Зеркальная ошибка, снятие значения с пустого стека, называется опустошением стека (stack underflow).
Как реализуют стек?
Два распространённых способа. Динамический массив кладёт и снимает с конца: амортизированно
O(1) и дружелюбно к кешу, так работают list в Python и ArrayDeque в Java. Связный список кладёт и снимает с головы: O(1) в худшем случае и без перевыделения, но по указателю на элемент. std::stack в C++ устроен как адаптер: по умолчанию он работает поверх std::deque, сегментированного массива, а при желании принимает другой контейнер.Где стеки применяются в реальных программах?
Стек вызовов для вызовов функций и рекурсии, история отмены и повтора действий, навигация «назад» в браузере, вычисление выражений и проверка парности скобок в парсерах, а также явный стек, который превращает рекурсивный поиск в глубину в итеративный цикл.
Связанные ресурсы
Больше визуализаций
