Стек на списке: реализация push и pop через массив

Стек - структура данных с дисциплиной LIFO (last in, first out): последний добавленный элемент уходит первым. Самая частая реализация стека на списке - это не связный список, а обычный массив (в Python его называют list, отсюда и путаница в терминах): элементы лежат подряд в памяти, а вершина стека отслеживается одним целым числом top. Ниже разберём, как устроены push и pop через индекс вершины, почему при переполнении массив приходится расширять вдвое, и почему средняя сложность push всё равно остаётся O(1), хотя отдельная операция может стоить O(n). Чтобы увидеть это на числах, покрути калькулятор ниже: он симулирует последовательность push и pop и показывает, как растёт ёмкость массива и сколько ячеек пришлось скопировать при расширениях.

Что такое стек и зачем ему список (массив)

Абстрактный стек поддерживает три операции: push(x) - положить элемент на вершину, pop() - снять и вернуть верхний элемент, peek() - посмотреть верхний элемент, не снимая. Реализовать это можно на связном списке (каждый элемент хранит указатель на предыдущий) или на списке-массиве: непрерывном блоке памяти фиксированной ёмкости $C$ с указателем вершины $top$, равным числу элементов сейчас в стеке. Массив предпочитают, когда важна компактность и скорость: элементы лежат подряд, без накладных расходов на указатели, и обращение по индексу - мгновенное. Плата за это - необходимость время от времени расширять массив, когда место заканчивается.

Операции push и pop через индекс вершины

Реализация предельно проста. Пока в массиве есть свободное место, push кладёт элемент в ячейку с индексом $top$ и увеличивает $top$ на единицу:

$\text{push}(x):\quad arr[top] = x,\ \ top \mathrel{+}= 1.$

$\text{pop}():\quad top \mathrel{-}= 1,\ \ \text{return } arr[top].$

Обе операции в этом случае - константное время: ни поиска, ни сдвига элементов не требуется, меняется только значение индекса. Проблема возникает, когда $top$ достигает текущей ёмкости $C$ массива: класть новый элемент уже некуда.

Рассчитать для своей задачи

Расширение ёмкости: почему push всё равно O(1) в среднем

Когда $top = C$, происходит resize: выделяется новый массив ёмкостью $2C$, все $C$ элементов копируются в него, старый массив освобождается, и только после этого новый элемент дописывается на вершину:

$\text{resize}:\quad C_{\text{new}} = 2\,C_{\text{old}},\qquad \text{копий} = C_{\text{old}}.$

Один такой push стоит $O(n)$ - нужно скопировать всё содержимое. Но расширения случаются редко: ёмкость удваивается, поэтому между двумя соседними расширениями число дешёвых push растёт экспоненциально. Если считать по методу агрегата, суммарная цена копирований после $N$ операций push при стартовой ёмкости $C_0=1$ равна геометрической сумме:

$\sum_{i=0}^{\log_2 N} C_0 \cdot 2^{i} \;<\; 2N.$

Добавив ещё $N$ операций записи (по одной на каждый push), получаем, что суммарная стоимость $N$ вызовов push меньше $3N$, то есть амортизированная стоимость одного push - константа, $O(1)$. Именно рост коэффициентом 2 (а не, скажем, добавление фиксированных 10 ячеек за раз) даёт эту оценку: при линейном приросте ёмкости суммарная цена копирований становится квадратичной, и амортизированная сложность push деградирует до $O(n)$.

Рассчитать для своей задачи

Для 10 последовательных push при стартовой ёмкости 1 расширения происходят на 2-м, 3-м, 5-м и 9-м push (ёмкость проходит путь $1\to2\to4\to8\to16$), суммарно копируется $1+2+4+8=15$ ячеек - меньше границы $2\cdot10=20$. Средняя цена одного push здесь $\approx 2{,}5$ операции, что и есть иллюстрация константной амортизированной сложности при переменном фактическом времени отдельных вызовов.

Куда девается память после pop

Здесь кроется частая путаница. Операция pop - это просто $top \mathrel{-}= 1$: она не уменьшает ёмкость массива и не освобождает память под неиспользуемые ячейки. Даже если из стека вынуты почти все элементы, выделенный блок памяти остаётся прежнего размера - используется только его начало до индекса $top$. Коэффициент заполнения (load factor) $top / C$ после серии pop может стать сколь угодно малым, и память при этом простаивает. Некоторые реализации добавляют «сжатие» - уменьшение ёмкости вдвое, когда заполнение падает ниже четверти, - но в учебной и большинстве практических реализаций (включая стандартный list в Python и Vec в Rust без явного shrink_to_fit) этого не делают: постоянные пере-аллокации в обе стороны обошлись бы дороже, чем немного лишней памяти.

Стек на списке против стека на связном списке

У связного списка каждый push и pop - гарантированно $O(1)$ в худшем случае, без всяких амортизаций: новый узел просто присоединяется или отсоединяется от головы, копировать ничего не нужно. Плата - память: на каждый элемент нужен ещё указатель (обычно 8 байт на 64-битной системе) и отдельная аллокация в куче, которая на порядок медленнее одного присваивания в массиве. Список-массив, напротив, тратит меньше памяти на элемент и быстрее в среднем случае за счёт локальности данных (все элементы лежат рядом, что дружелюбно к кэшу процессора), но платит редкими дорогими resize. На практике для стеков предсказуемого небольшого размера почти всегда выбирают именно список-массив: средняя цена ниже, а редкие пики $O(n)$ не критичны, если не работать в системах жёсткого реального времени.

Пример пошагового построения стека

Возьмём стартовую ёмкость $C_0 = 1$ и выполним 10 push подряд. Ёмкость проходит путь $1 \to 2 \to 4 \to 8 \to 16$, расширения случаются на push номер 2 (копия 1 ячейки), номер 3 (копия 2), номер 5 (копия 4) и номер 9 (копия 8). После десятого push стек заполнен полностью: $top = 10$, ёмкость $C = 16$, суммарно скопировано $1+2+4+8=15$ ячеек. Теперь выполним 4 pop подряд: $top$ последовательно уменьшается $10\to9\to8\to7\to6$, а ёмкость остаётся равной 16 - ни одного resize вниз не происходит. Итог: в стеке 6 элементов, под них выделено место на 16, коэффициент заполнения $6/16 = 37{,}5\%$. Ровно эту последовательность операций можно проиграть в калькуляторе выше, изменяя число push и pop.

Частые ошибки

• Путать список-массив со связным списком. «Реализация на списке» без уточнения часто означает именно массив (как Python list), а не структуру с указателями - от этого зависит, есть ли вообще амортизация.
• Забывать про амортизацию и говорить «push - это O(n)». Отдельный push при resize действительно стоит $O(n)$, но в среднем по длинной последовательности - $O(1)$; это разные утверждения о сложности.
• Считать, что pop уменьшает выделенную память. Без явного сжатия ёмкость после pop не меняется - это не баг, а стандартное поведение.
• Использовать линейный прирост ёмкости (например, C += 10 вместо C *= 2). Это ломает амортизационную оценку: суммарная цена копирований становится $O(N^2)$ вместо $O(N)$.
• Проверять переполнение уже после записи в массив. Условие top === capacity нужно проверять ДО записи нового элемента, иначе запись уйдёт за границу массива.

FAQ

Почему ёмкость расширяют именно вдвое, а не на фиксированное число? Удвоение даёт геометрическую прогрессию расходов на копирование, поэтому их сумма ограничена $2N$ и амортизированная стоимость push остаётся $O(1)$. Прирост на константу даёт квадратичную суммарную стоимость.

Какая сложность у pop в стеке на списке? Всегда $O(1)$ - операция лишь уменьшает индекс вершины, копирования и пере-аллокации не требуется (если реализация не делает явного сжатия ёмкости).

Что произойдёт, если попытаться сделать pop у пустого стека? Это ошибка underflow: индекс $top$ уже равен нулю, брать элемент неоткуда. Корректная реализация обязана проверять $top > 0$ перед pop и бросать исключение или возвращать признак ошибки.

Коротко

Стек на списке (массиве) хранит элементы подряд и следит только за индексом вершины $top$: push кладёт элемент и увеличивает $top$, pop уменьшает $top$ - обе операции $O(1)$, пока хватает места. Когда $top$ достигает ёмкости $C$, происходит resize с удвоением ($C \to 2C$) и копированием всех элементов - разовая цена $O(n)$, но благодаря геометрическому росту суммарная стоимость $N$ push остаётся меньше $3N$, то есть амортизированная сложность push - $O(1)$. Pop, в отличие от push, никогда не уменьшает ёмкость - освобождение памяти требует отдельной логики сжатия, которую большинство реализаций сознательно не делают.