Стек в программировании

Стек – абстрактный тип данных (АТД) с дисциплиной доступа LIFO (last in – first out): последним пришёл – первым обслужен. Он лежит в основе вызовов функций и рекурсии, разбора скобочных структур, вычисления выражений, итеративных обходов графов, механизмов «отмена/повтор» и др. В материале строго определены операции стека и их инварианты, разобраны классические реализации (на массиве и на связном списке), дана амортизированная оценка для динамического массива, описан стек вызовов и активационные записи, приведены эталоны псевдокода и частые ошибки. Связь с ЕГЭ проявляется в задачах на трассировку, анализ сложности, работу со строками и массивами, моделирование автоматов. Завершает текст практикум из пяти упражнений формата «условие → критерии → подсказки».

Понятийный аппарат

Определение (АТД «стек»). Стек – структура, поддерживающая конечное множество значений домена T и операции:

• push(x: T) – поместить элемент на вершину;
• pop() → T – снять и вернуть верхний элемент;
• top() → T (синоним peek) – вернуть верхний элемент без снятия;
• isEmpty() → Bool, size() → Nat.

Дисциплина LIFO. Пусть последовательность операций заканчивается вставкой push(a1), push(a2), …, push(ak). Тогда первые k успешных вызовов pop() вернут элементы в порядке ak, ak-1, …, a1.

Инварианты корректности.

1. Для счётчика элементов n = size() всегда 0 ≤ n ≤ capacity (для массивной реализации).
2. Если isEmpty() = true, то top() и pop() недопустимы (должны бросать ошибку или возвращать специальный статус).
3. После push(x); pop() стек эквивалентен прежнему состоянию.

Сложность по определению АТД. При корректной реализации push/pop/top/isEmpty/size работают за O(1) по времени; память – пропорциональна количеству хранимых элементов.

Формальная спецификация (пред-/постусловия)

Для любой корректной реализации:

• pre(pop) : size() > 0 ; post(pop) : возврат = старый top, size := size − 1.
• pre(push) : (для фиксированной ёмкости) size() < capacity ; post(push) : top = x, size := size + 1.
• pre(top) : size() > 0 ; post(top) : size не меняется.
• isEmpty() ↔ (size() = 0) – логическая эквивалентность.

Реализации и их свойства

1. На массиве (фиксированная ёмкость)
   

   Храним массив A[0..capacity−1] и индекс t – число элементов (также позиция для следующей вставки).

   • push(x): A[t] := x; t := t + 1.

   • pop(): t := t − 1; return A[t].

   • Инвариант: 0 ≤ t ≤ capacity.

   Плюсы: простота, высокая пространственная локальность. Минусы: риск переполнения (overflow).

2. На массиве с динамическим ростом
   

   При попытке push при t = capacity создаём новый массив ёмкости α·capacity (обычно α=2), копируем элементы, переназначаем указатель.

   Амортизированная оценка. Копирование происходит редко; стоимость «дорогих» расширений распределяется по множеству дешёвых вставок ⇒ средняя стоимость push остаётся O(1) амортизированно.

3. На односвязном списке
   

   Храним указатель head на верхний узел Node{value, next}.

   • push(x): head := new Node(x, head).

   • pop(): v := head.value; head := head.next; return v.
     Плюсы: нет переполнения до исчерпания памяти. Минусы: больше накладных расходов на узлы, хуже локальность.

Стек вызовов и активационные записи

Активационная запись (stack frame) – блок данных, создаваемый при вызове процедуры/функции; содержит возвращаемый адрес, сохранённые регистры, параметры, локальные переменные, временные значения. Вызов функции «толкает» новую запись в стек; возврат «снимает» её.

Рекурсия. Каждая рекурсивная глубина создаёт новый кадр.

• Глубина стека ограничивает максимально допустимую глубину рекурсии.
• Хвостовая рекурсия теоретически оптимизируема до итерации (но в учебных средах оптимизация обычно не включена).

Ошибки уровня стека.

• Stack overflow – переполнение из-за «бесконечной» рекурсии или слишком больших локальных объектов.
• Устранение: корректные базовые случаи, перенос крупных структур в кучу.

Алгоритмы на стеке: ключевые паттерны

1. Проверка балансировки скобок. Проходим строку слева направо; открывающие кладём в стек; при закрывающей требуем совпадение типов с вершиной. Стек пуст в конце – строка корректна.

2. Вычисление выражений в ОПЗ (RPN). Числа – push; оператор – снимаем нужное число аргументов, вычисляем, push результата.

3. Преобразование инфикс → постфикс (шунтовочный алгоритм). Стек операторов хранит приоритеты и ассоциативность; выход – очередь/список.

4. Итеративный DFS. В стек кладём вершину; в цикле снимаем, посещаем, кладём непосещённых соседей.

5. Undo/Redo (двойной стек). Основной стек – история действий, вспомогательный – «будущее»; новые действия очищают «будущее».

Псевдокод (учебные эталоны)

1. Динамический стек на массиве
   

   init():

     A := new array[initial_capacity]

     t := 0

   push(x):

     if t = capacity(A):

        B := new array[2*capacity(A)]

        copy A -> B

        A := B

     A[t] := x

     t := t + 1

   pop():

     require t > 0

     t := t - 1

     return A[t]

   top():

     require t > 0

     return A[t-1]

   size(): return t

   isEmpty(): return t = 0

2. Балансировка скобок
   

   isBalanced(s):

     S := empty stack of char

     for each c in s:

       if c in {'(', '[', '{'}: push(S, c)

       else if c in {')', ']', '}':

         if isEmpty(S): return false

         o := pop(S)

         if not matches(o, c): return false

     return isEmpty(S)

   matches(o,c): return (o='(' and c=')') or (o='[' and c=']') or (o='{' and c='}')

3. Оценка RPN
   

   evalRPN(tokens):

     S := empty stack of int

     for t in tokens:

       if t is number: push(S, t)

       else:  // бинарный оператор

         b := pop(S); a := pop(S)

         push(S, apply(t, a, b))

     return pop(S)

4. Итеративный DFS
   

   DFS_iter(G, s):

     S := empty stack of vertex

     visited := set()

     push(S, s)

     while not isEmpty(S):

       v := pop(S)

       if v in visited: continue

       visit(v)

       add v to visited

       for u in neighbors(v) in reverse order:

         if u not in visited: push(S, u)

5. Undo/Redo двумя стеками
   

   do(action):

     apply(action)

     push(UNDO, action)

     clear(REDO)

   undo():

     require not isEmpty(UNDO)

     a := pop(UNDO)

     apply(inverse(a))

     push(REDO, a)

   redo():

     require not isEmpty(REDO)

     a := pop(REDO)

     apply(a)

     push(UNDO, a)

Сложность и амортизированный анализ

• Массив с удвоением. Любая последовательность из m операций push требует не более O(m) копирований в сумме ⇒ средняя стоимость одной вставки – константа.
• Связный список. Всегда O(1) на операцию, но с большей константой из-за аллокации узлов.
• Алгоритмы. Балансировка скобок – O(n) времени и O(n) памяти в худшем случае; оценка RPN – O(n) времени и O(k) памяти (где k – максимальное количество промежуточных результатов).

Типичные ошибки и как их избегать

1. Непроверенный pop/top на пустом стеке. Лечить предусловиями и защитными проверками.
2. Потеря инварианта 0 ≤ t ≤ capacity. Любая операция изменяет t ровно на ±1 и не выходит за границы.
3. Смешение типов скобок. Всегда сопоставляйте по парам; нельзя сравнивать только «форму» (открывающая/закрывающая) без типа.
4. Молчаливое переполнение массива. Для фиксированного буфера – возвращать статус/исключение; лучше использовать динамический рост.
5. Итеративный DFS без пометки посещения до помещения соседей. Может вызвать многократное помещение одной вершины; помечайте сразу после извлечения, а дубликаты пропускайте.

Связь с подготовкой к ЕГЭ по информатике

• Трассировка программ. Прямое моделирование стека операций, вывода и локальных переменных.
• Строковые задачи. Проверка скобочных выражений, удаление вложенных сегментов – естественные задачи на стек.
• Выражения. Перевод инфиксной записи в постфиксную и вычисление – частая экзаменационная тема.
• Графы. Понимание DFS и топологической сортировки (через стек завершений) повышает успеваемость по разделу графов.
• Сложность. Умение аргументировать O(n) для стековых проходов – важный навык для задач повышенной сложности.

Практикум: 5 упражнений (ЕГЭ-ориентированный формат)

Упражнение 1. Трассировка массива-стека
Условие. Имеется пустой динамический стек. Последовательно выполнить операции:
push(3), push(1), push(4), pop(), push(1), push(5), pop(), pop(), push(9)

1. Укажите значение на вершине и размер стека после каждой операции.

2. Запишите содержимое стека (снизу вверх) в конце.
   Критерии. Правильное обновление вершины и счётчика; корректная последовательность значений.
   Подсказки. После pop() вершина – предыдущий элемент; размер уменьшается на 1.

Упражнение 2. Балансировка скобок с несколькими типами
Условие. Для строки
s = "{[(a+b)*c] + (d/[e-f])}"
проведите работу алгоритма §6.2: выпишите содержимое стека после обработки каждого символа-скобки.
Критерии. Точное соответствие открывающих/закрывающих; стек пуст в конце.
Подсказки. Игнорируйте не-скобочные символы; при закрывающей обязательна проверка совпадения типов.

Упражнение 3. Инфикс → постфикс (шунтовочный алгоритм)
Условие. Преобразуйте выражение
A + B*(C - D) + E
в постфиксную форму и вычислите значение при A=2, B=3, C=10, D=4, E=5.
Критерии. Правильный приоритет * над +, корректная обработка скобок, корректное использование стека операторов.
Подсказки. Ожидаемая ОПЗ: A B C D - * + E + ; затем применить стек для вычисления.

Упражнение 4. Рекурсия vs явный стек
Условие. Реализована рекурсивная функция вычисления факториала F(n) со стандартным базовым случаем F(0)=1.

1. Сколько активационных записей будет одновременно на стеке для n=5?

2. Сымитируйте вычисление с явным стеком значений: покажите последовательность push/pop и максимальную высоту стека.
   Критерии. Осознание «глубина = n+1» для входов 0..n; корректная последовательность операций при замене рекурсии на явный стек.
   Подсказки. В явной симуляции удобно хранить пары «текущий k, промежуточный результат».

Упражнение 5. Undo/Redo двумя стеками
Условие. Последовательность действий в текстовом редакторе:
type(A), type(B), type(C), undo, type(D), undo, redo, type(E)
Смоделируйте содержимое стеков UNDO и REDO после каждой операции и укажите итоговое содержимое текста.
Критерии. Новое действие после undo очищает стек REDO; redo возможен только при непустом REDO.
Подсказки. Текст – конкатенация применённых действий; undo добавляет инверсии в REDO.

Заключение

Стек – минималистичная, но чрезвычайно мощная структура, обеспечивающая предсказуемую дисциплину доступа, строгие инварианты и O(1)-операции. Его присутствие на всех уровнях – от аппаратного протокола вызовов до алгоритмов разбора и обходов – делает владение стеком обязательным навыком. Для ЕГЭ владение стековыми приёмами означает уверенность в задачах на строки, выражения, графы и трассировку. Следуя изложенным правилам реализации и проверяя решения через инварианты, можно систематически избегать ошибок и обосновывать сложность. Пять упражнений закрепляют навыки в формах, максимально близких к экзаменационным.