Стек и другие структуры данных

• Стек
• Правильные скобочные последовательности
• Обратная польская запись
• Стек в рекурсии
• Задача о наибольшем прямоугольнике
• Очередь и дек
• Односвязные и двусвязные списки

Стек

Мы уже знаем, что такое стек. Это структура данных, которая хранит элементы упорядоченно и умеет отвечать на две операции за $O(1)$:

• push(x) - положить элемент x в конец стека
• pop() - снять и вернуть элемент, лежащий в конце стека

То есть это структура данных, где действия происходят только с элементом, лежащим в конце. Выполняется принцип FILO (First In - Last Out) - последним вынется тот элемент, который мы положили первым, если сначала положить все элементы, а потом все вынуть.

Часто для удобства у стека еще есть операции * size() - размер стека * empty() - проверка на пустоту * clear() - очистить стек

Как стек удобно использовать динамический массив: * в Питоне это list, причем push = append, pop = pop * в C++ это vector, причем push = push_back, а операция pop заменяется на две - back возвращает последний элемент, а pop_back вынимает его

a = []
a.append(5)
a.append(3)
a.append(10)
print(a.pop())
a.append(12)
print(a.pop())

10
12

Правильные скобочные последовательности

Есть несколько определений Правильной скобочной последовательности - ПСП.

1. Неформальное определение

ПСП - это строка из открывающих и закрывающих скобок, который получается из арифметических выражений удалением всего, кроме скобок.

Например: из выражения $(1+2)\ast (3+100\ast (3/2))$ получается ПСП $()(())$. А вот $)(())$ не получится из никакого выражения.

2. Явное определение

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

Например: $((())())$ - ПСП, так как разбивает на вот такие непересекающиеся пары: $\mathbf{\text{(}}\underset{―}{(}\overline{(}\overline{)}\underset{―}{)}\mathit{\text{()}}\mathbf{\text{)}}$. А вот строку $(()$ нельзя разбить на пары - там нечетное число скобок.

3. Рекурсивное определение

• пустая строка - это ПСП
• если $A$ - это ПСП, то $(A)$ - это тоже ПСП
• если $A$ и $B$ - это ПСП, то $AB$ - это тоже ПСП

Например: пустая строка - ПСП, значит $()$ - ПСП, значит $(())$ - ПСП, значит $(())()$ - ПСП, значит $((())())$ - ПСП. А вот $())(()$ не получится по этим правилам никак.

4. Определение через баланс ПСП - это строка из открывающих и закрывающих скобок. Давайте определим баланс на префиксе длины $n$ как разница числа открывающих и закрывающих скобок на этом префиксе. Тогда в ПСП должны выполняться два свойства:

• любой баланс больше или равен 0
• баланс всей строки равен 0

То есть на любом префиксе открывающих скобок не меньше, чем закрывающих, а во всей строке их равное число.

Оказывается, именно последним определением удобно пользоваться, чтобы определить, является ли строка ПСП. А именно, давайте пройдемся слева направо и будем прибавлять $+1$, если встретим открывающую скобку, и $-1$, если встретим закрывающую скобку. И достаточно проверить, что баланс всегда неотрицателен, и равен нулю в конце.

Еще можно определить ПСП с разными видами скобок. Например, $([](\{\}))$ - это ПСП, а $[(])$ - нет. В явное определение надо просто добавить, что скобки в одной паре должны быть одного вида. В рекурсивное определение нужно добавить правила вида “если $A$ - это ПСП, то $[A]$ - это тоже ПСП” для всех видов скобок.

А вот определение через баланс так легко не обобщается, а ведь мы именно его хотим использовать для алгоритма проверки на ПСП. Для расширения придется использовать стек:

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

Например: строка $\{[([])()]\}$. В ходе алгоритм стек будет меняться так:

• пустой
• $\{$
• $\{[$
• $\{[($
• $\{[([$
• $\{[($ - убранная $[$ подходит $]$
• $\{[$ - убранная $($ подходит $)$
• $\{[($
• $\{[$ - убранная $($ подходит $)$
• $\{$ - убранная $[$ подходит $]$
• $\{\{$
• $\{$ - убранная $\{$ подходит $\}$
• пустой - убранная $\{$ подходит $\}$

Все убранные скобки подошли встреченным закрытым, а в конце стек пустой - а значит это ПСП.

А вот строка $[]$ - это не ПСП: * пустой * $[$ * $[\{$ * ошибка, так как $\{$ в конце стека не подходит $]$

Такой алгоритм работает за $O(N)$ - так как мы проходимся по массиву и каждый раз делаем одну из операций со стеком - либо push, либо pop.

Обратная польская запись

Стек также часто используют для вычислений в каком-нибудь сложном порядке. Например, интересно, как именно компьютер вычисляет выражение $(1+2)\ast (100\ast (3/2)+3)+4$. Его вычислять сложно, давайте перепишем его в другом формате, в котором его вычислять проще:

$[1,2,+,100,3,2,/,\ast ,3,+,\ast ,4,+]$

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

Например для этого выражения стек будет вести себя так: * [] * $[1]$ * $[1,2]$ * $[3]$ * $[3,100]$ * $[3,100,3]$ * $[3,100,3,2]$ * $[3,100,1.5]$ * $[3,150]$ * $[3,150,3]$ * $[3,153]$ * $[459]$ * $[459,4]$ * $[463]$

То, что осталось в конце в стеке - это и есть результат.

Стек в рекурсии

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

А именно, представьте, что вы вызываете функцию f(n), и внутри нее вызывается другая функция g(n). Но ведь когда g(n) перестанет выполняться, вам нужно продолжить выполнять f(n). А значит все это время, пока вы вычисляете g(n), вам нужно хранить информацию о всех аргументах и локальных переменных внутри функции f(n), и даже место, где вы там остановились. Удобно хранить всю эту информацию в стеке - когда вы вызываете функцию, все содержимое прошлой функции сохраняется в стек, а когда функция перестает выполняться - прошлая функция снимает со стека последнюю функцию, и продолжает ее выполнять.

Именно поэтому все задачи на рекурсию можно решить и без рекурсии, и возможно это даже будет быстрее. Достаточно лишь написать while, который вынимает функцию вместе со всей информацией про ее выполенени с верха стека, выполняет её до следующего шага, где нужно вызвать другую функцию, кладет на верх стека обновленную функцию и новую вызванную функцию. И так, пока стек не станет пустым.

Кстати, стек рекурсии ограничен в некоторых языках прогрмамирования (например, питон), и его нужно поднимать:

import sys
sys.setrecursionlimit(10000)

В C++ стек рекурсии ограничен лишь вашей оперативной памятью.

Пример задачи на рекурсию, которую теоретически можно переписать под стек - это Ханойские башни.

Условие. > У вас есть три стержня (= стека), на первом находятся $N$ дисков, причем чем диск ниже, тем он шире. Можно переносить верхний диска одного стержня на верх другого стержня, если только под ним не будет находиться меньший по ширине диск. Нужно вывести последовательность операций, после которой все диски перенесутся на третий стержень.

Решение. > Достаточно делать как в динамическом программировании - формализовать задачу и свести ее к предыдущим. Давайте функция hanoi(n, from, to, middle) будет выводить все операции с переносом $n$ стержней с верха стержня $from$ на стержень $to$, при условии, что их можно еще пользоваться стержнем $middle$ (и при этом на стержнях $to$ и $middle$ все диски шире, чем эти $n$, чтобы их можно было класть сверху). Тогда на самом деле эта операция разбивается на такие: * hanoi(n - 1, from, middle, to) - перенести $n-1$ диск на средний стержень * print(from + ” -> ” + to) - перенести самый широкий диск на финальный стержень * hanoi(n - 1, middle, to, from) - перенести $n-1$ диск со среднего стержаня на финальный

Алгоритм работает за $O(2^n)$, так как вызывает два таких же алгоритма для $n-1$.

Задача о наибольшем прямоугольнике

Условие. > У вас есть гистограмма - набор прямоугольников шириной $1$ и высотой $N$, идущих слева направо вплотную, причем они все “стоят” на земле - их нижняя координата $y$ равна $0$. Пример гистограммы:

Задача - найти наибольший по площади прямоугольник, лежащий внутри такой клеточной гистограммы.

Решение. Заметим, что нижняя граница наибольшего прямоугольника - это всегда $y=0$. Наибольший прямоугольник должно быть невозможно рашсирить ни в одну из сторон. Давайте просто переберем все такие прямоугольники и выберем из них максимальный по площади.

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

Строить её нужно так: давайте рассмотрим новый столбец. Если его высота больше, чем у последнего в стеке (предыдущего столбца), то просто кладём его в стек, и на этом всё. Если его высота меньше или равна, чем у последнего, то нужно вынимать столбцы с конца стека, пока высота нового столбца не будет наконец больше, чем у последнего в стеке. В конце нужно просто вынуть все столбцы из стека (для этого удобно просто в конец положить фиктивный столбец высоты ноль).

При вынимании столбца из стека нужно посчитать площадь максимального прямоугольника, который включает этот столбец. Высоту мы уже знаем, надо определить его площадь. Заметим, что его левая координата - это индекс столбца, который лежит перед этим столбцом в стеке (это самый правый столбец, который левее удаляемого и при этом ниже по высоте) плюс один. А правая координата - это та, которую мы сейчас рассматриваем (раз нам нужно удалить этот столбец).

Как это работает? Наибольший прямоугольник упирается верхом хотя бы в один столбец, а значит когад мы его будем удалять, мы учтем этот прямоугольник.

Так можно за $O(N)$ найти площадь максимального прямоугольника в такой гистограмме.

Заметим, что к этой задаче можно свести задачу поиска максимального белого прямоугольника в прямоугольнике с черными и белыми прямоугольниками - нужно для каждой клетки посчитать, сколько клеток поряд наверх из нее - это белые клетки (с помощью простого динамического программирования), и после этого перебрать $N$ строк и решить задачу для гистограммы, низ которой является этой строкой - все высоты как раз мы теперь знаем.

Так мы решим эту задачу за $O(N^2)$ - а это размер прямоугольника, так что быстрее и не получится.

Очередь и дек

Очередь - это структура данных, которая тоже хранит упорядоченные элементы с такими операциями за $O(1)$: * push(x) - положить элемент в конец очереди * pop() - вынуть и вернуть элемент из начала очереди

Выполняется принцип FIFO (First In - First Out) - кто первый пришел, тот первый и ушел. Очередь удобно использовать для моделирования реальных очередей, ведь они позволяют честно распределить что-то - кто первый пришел, тот первый и получил. Также очередь часто используют для алгоритмов с несколькими независимыми процессами - удобно хранить очередь задач, которые нужно выполнить, и процесс, когда освобождется, берет из очереди самую ранее добавленную задачу и берется ее выполнять.

Дек - это структура данных, которая тоже хранит упорядоченные элементы с такими операциями за $O(1)$: * push_back(x) - положить элемент в конец дека * push_front(x) - положить элемент в начало дека * pop_back() - вынуть и вернуть элемент из конца дека * pop_front() - вынуть и вернуть элемент из начала дека

То есть очередь и стек можно реализовать с помощью дека. Чаще всего удобно вместо очереди использовать именно дек.

Обратите внимание, что дек не умеет обращаться к элементу по его номеру, он умеет работать только с крайними элементами.

В Питоне есть collections.deque:

from collections import deque
d = deque()
d.append(5)
d.append(100)
d.appendleft(10)
print(d.pop())
d.append(1000)
print(d.pop())
print(d.popleft())
print(d.popleft())

100
1000
10
5

В C++ также есть deque, но, как и в векторе, pop_back и pop_front не возвращают объект.

#include <deque>
...
deque<int> d;
d.push_back(1);
d.push_back(2);
d.push_front(10);
cout << d.back();
d.pop_back();
cout << d.front();
d.pop_front();
cout << d.front();
d.pop_front();

Односвязные и двусвязные списки

Осторожно: эти списки никак не связаны со списками из питона (которые на самом деле динамические массивы).

Проблема стека: нельзя добавлять и удалять элементы в середине.

Давайте хранить массив $values$ с нужными нам элементами, и для каждого элемента еще хранить (в структуре или в отдельном массиве $next$) индекс следующего элемента. И, конечно, хранить индекс самого первого элемента $start$. Будем называть такую структуру данных односвязным списком.

Чтобы пройтись по всему односвязному списку, нужно начать с индекса первого элемента и постепенно переходить по индексу следующего элемента ($i$ -> $next[i]$), пока $next[i]\ne i$.

Тогда если у нас есть индекс какого-то элемента $index$, мы за $O(1)$ можем вставить после него еще один - нужно добавить в массив справа еще один элемент, пусть он получил индекс $new$, и сделать $next[new]=next[index],next[index]=new$.

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

Задание

Решите как можно больше задач из контеста https://informatics.msk.ru/mod/statements/view.php?id=33318