- Стек
- Правильные скобочные последовательности
- Обратная польская запись
- Стек в рекурсии
- Задача о наибольшем прямоугольнике
- Очередь и дек
- Односвязные и двусвязные списки
Мы уже знаем, что такое стек. Это структура данных, которая хранит элементы упорядоченно и умеет отвечать на две операции за
- 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
Есть несколько определений Правильной скобочной последовательности - ПСП.
- Неформальное определение
ПСП - это строка из открывающих и закрывающих скобок, который получается из арифметических выражений удалением всего, кроме скобок.
Например: из выражения
- Явное определение
ПСП - это строка из открывающих и закрывающих скобок, в которой все скобки можно разделить на пары, где первая скобка - открывающая, а вторая - закрывающая, открывающая идет раньше закрывающей, и никакие две пары не пересекаются.
Например:
- Рекурсивное определение
- пустая строка - это ПСП
- если
$A$ - это ПСП, то$(A)$ - это тоже ПСП - если
$A$ и$B$ - это ПСП, то$AB$ - это тоже ПСП
Например: пустая строка - ПСП, значит
- Определение через баланс
ПСП - это строка из открывающих и закрывающих скобок. Давайте определим баланс на префиксе длины
$n$ как разница числа открывающих и закрывающих скобок на этом префиксе. Тогда в ПСП должны выполняться два свойства:
- любой баланс больше или равен 0
- баланс всей строки равен 0
То есть на любом префиксе открывающих скобок не меньше, чем закрывающих, а во всей строке их равное число.
Оказывается, именно последним определением удобно пользоваться, чтобы определить, является ли строка ПСП. А именно, давайте пройдемся слева направо и будем прибавлять
Еще можно определить ПСП с разными видами скобок. Например, $()$ - это ПСП, а
А вот определение через баланс так легко не обобщается, а ведь мы именно его хотим использовать для алгоритма проверки на ПСП. Для расширения придется использовать стек:
ПСП - это такая строка из открывающих и закрывающих скобок разного типа, если построении стека открытых скобок при прохождении по строке не возникает ошибки, а в конце стек пустой. А именно, давайте заведем пустой стек, пройдемся слева направо и будем класть в конец стека открывающую скобку, если мы ее встретили, и вынимать её, если встретили закрывающую - при этом надо проверить, что вынимаемся открытая скобка того же типа, что и встреченная закрывающая.
Например: строка
- пустой
${$ ${[$ ${[($ ${[([$ -
${[($ - убранная$[$ подходит$]$ -
${[$ - убранная$($ подходит$)$ ${[($ -
${[$ - убранная$($ подходит$)$ -
${$ - убранная$[$ подходит$]$ ${{$ -
${$ - убранная${$ подходит$}$ - пустой - убранная
${$ подходит$}$
Все убранные скобки подошли встреченным закрытым, а в конце стек пустой - а значит это ПСП.
А вот строка
- пустой
$[$ $[{$ - ошибка, так как
${$ в конце стека не подходит$]$
Такой алгоритм работает за
Стек также часто используют для вычислений в каком-нибудь сложном порядке. Например, интересно, как именно компьютер вычисляет выражение
Такой список чисел и операций называют обратной польской записью. Она вычисляется так: нужно проходить слева направо и
- если встречается число - кладем его в стек
- если встречается операция - снимаем с конца стека два числа, применяем к ним эту операцию, и кладем результат в стек
Например для этого выражения стек будет вести себя так:
- []
$[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$ диск со среднего стержаня на финальный
Алгоритм работает за
Условие.
У вас есть гистограмма - набор прямоугольников шириной
$1$ и высотой$N$ , идущих слева направо вплотную, причем они все "стоят" на земле - их нижняя координата$y$ равна$0$ . Пример гистограммы:
| ■ | |||||||||
| ■ | ■ | ||||||||
| ■ | ■ | ■ | |||||||
| ■ | ■ | ■ | ■ | ||||||
| ■ | ■ | ■ | ■ | ■ | |||||
| ■ | ■ | ■ | ■ | ■ | ■ | ||||
| ■ | ■ | ■ | ■ | ■ | ■ | ■ | |||
| ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ||
| ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | |
| ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ |
Задача - найти наибольший по площади прямоугольник, лежащий внутри такой клеточной гистограммы.
Решение.
Заметим, что нижняя граница наибольшего прямоугольника - это всегда
Давайте идти слева направо по вертикальным прямоугольникам гистограммы и хранить такую "лесенку" - в стеке будут лежать пройденные столбики (индекс и высота), но только те, которые нужны, чтобы столбцы строго возрастали, и при этом лесенка заканчивалась последним рассмотренным столбцом.
Строить её нужно так: давайте рассмотрим новый столбец. Если его высота больше, чем у последнего в стеке (предыдущего столбца), то просто кладём его в стек, и на этом всё. Если его высота меньше или равна, чем у последнего, то нужно вынимать столбцы с конца стека, пока высота нового столбца не будет наконец больше, чем у последнего в стеке. В конце нужно просто вынуть все столбцы из стека (для этого удобно просто в конец положить фиктивный столбец высоты ноль).
При вынимании столбца из стека нужно посчитать площадь максимального прямоугольника, который включает этот столбец. Высоту мы уже знаем, надо определить его площадь. Заметим, что его левая координата - это индекс столбца, который лежит перед этим столбцом в стеке (это самый правый столбец, который левее удаляемого и при этом ниже по высоте) плюс один. А правая координата - это та, которую мы сейчас рассматриваем (раз нам нужно удалить этот столбец).
Как это работает? Наибольший прямоугольник упирается верхом хотя бы в один столбец, а значит когад мы его будем удалять, мы учтем этот прямоугольник.
Так можно за
Заметим, что к этой задаче можно свести задачу поиска максимального белого прямоугольника в прямоугольнике с черными и белыми прямоугольниками - нужно для каждой клетки посчитать, сколько клеток поряд наверх из нее - это белые клетки (с помощью простого динамического программирования), и после этого перебрать
Так мы решим эту задачу за
Очередь - это структура данных, которая тоже хранит упорядоченные элементы с такими операциями за
- push(x) - положить элемент в конец очереди
- pop() - вынуть и вернуть элемент из начала очереди
Выполняется принцип FIFO (First In - First Out) - кто первый пришел, тот первый и ушел. Очередь удобно использовать для моделирования реальных очередей, ведь они позволяют честно распределить что-то - кто первый пришел, тот первый и получил. Также очередь часто используют для алгоритмов с несколькими независимыми процессами - удобно хранить очередь задач, которые нужно выполнить, и процесс, когда освобождется, берет из очереди самую ранее добавленную задачу и берется ее выполнять.
Дек - это структура данных, которая тоже хранит упорядоченные элементы с такими операциями за
- 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();
Осторожно: эти списки никак не связаны со списками из питона (которые на самом деле динамические массивы).
Проблема стека: нельзя добавлять и удалять элементы в середине.
Давайте хранить массив
Чтобы пройтись по всему односвязному списку, нужно начать с индекса первого элемента и постепенно переходить по индексу следующего элемента (
Тогда если у нас есть индекс какого-то элемента
Часто бывает удобно хранить еще предыдущий элемент помимо следующего, чтобы можно было проходить по списку справа налево, и добавлять элемент перед каким-нибудь. Такой список называется двусвязным.
Решите как можно больше задач из контеста https://informatics.msk.ru/mod/statements/view.php?id=33318