Стек - Язык программирования C++ для спортивного программирования
Неделя 10Стек, Очередь, Дек и Задачи на моделирование
Стек
Стопка, до которой можно дотронуться только сверху: push, top и pop, вектор или строка в роли стека, проверка скобок, постфиксный калькулятор и стек, который знает свой минимум.
Теория
Урок 1 из 7
20 мин чтения
Вопросов: 5
На неделе 9 вы познакомились со стеком вызовов: каждый новый вызов кладётся
наверх, работает только верхний, а последний сделанный вызов возвращается первым.
Такой способ хранить вещи — стопка, до которой можно дотронуться только сверху, —
полезен далеко не только для вызовов функций, и в C++ он есть в готовом виде.
Представьте стопку тарелок. Чистую тарелку кладут наверх, и следующую берут тоже
сверху. Нижняя тарелка ждёт, пока не уберут все тарелки над ней. Последним
пришёл — первым ушёл — программисты пишут это как LIFO, — а стопка, которая так
работает, называется стеком.
stack: push, top, pop
Операция
Что делает
st.push(x)
кладёт x наверх
st.top()
верхний элемент — он остаётся в стеке
st.pop()
снимает верхний элемент и ничего не возвращает
st.empty()
true, если в стеке ничего нет
st.size()
сколько в нём элементов
Каждая из этих операций занимает один шаг, каким бы большим ни был стек. Два
правила избавят от многих бед:
pop()ничего не возвращает. Чтобы воспользоваться верхним элементом,
сначала прочитайте его через top(), потом вызовите pop().
Никогда не вызывайте top() или pop() у пустого стека. C++ вас не
остановит: программа упадёт или молча прочитает мусор. Сначала проверьте
, если не уверены.
дальше
Практика: Стек
Четыре задачи на стек: скобки, исчезающие буквы, постфиксный калькулятор и стек со своим минимумом.
Посмотрите по шагам, как стек наполняется и опустошается:
Стопка тарелок: последней пришла — первой ушла
C++
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5 ios_base::sync_with_stdio(false);
6 cin.tie(NULL);
7
8 stack<int> st;
9 st.push(7);
10 st.push(2);
11 st.push(9);
12 while (!st.empty()) {
13 cout << st.top() << " ";
14 st.pop();
15 }
16 cout << "\n";
17 return 0;
18}
Пустой стек
строка 8
В st пока ничего нет. На панели дно стека слева, а вершина справа.
st (дно → вершина)0 ячеек
нажми пуск
1 / 15
Что положили, то и выходит — но в обратном порядке, поэтому развернуть список —
самая простая работа для стека:
Для 5 и 4 8 15 16 23 программа печатает 23 16 15 8 4.
Как напечатать стек по порядку
В некоторых задачах в конце нужен весь стек, по порядку. Вот такая задача:
Дана строка — клавиши, которые нажимал человек. Буква печатает саму себя;
# — это backspace: он стирает последнюю набранную букву, а если текст пуст,
ничего не делает. Выведите текст, который остался. Для cay#t ответ — cat.
Ввод
Вывод
Текст ведёт себя как стек: набранная буква ложится наверх, а backspace снимает
верхнюю. Но у стека видна только вершина, поэтому в конце буквы снимаются с него
задом наперёд — последняя набранная первой.
Стек переворачивает всё, что через него проходит, поэтому второй стек
перевернёт буквы обратно. Перелейте первый стек во второй — top(), push() в
другой стек, pop(), — и наверху окажется первая набранная буква. Теперь,
снимая буквы со второго стека, получаем текст по порядку:
Для cay#t набираются буквы c, a и y, # стирает y, затем идёт t: в
стеке лежат c a t, наверху t. После переливания в другом стеке лежат t a c,
наверху c, и программа печатает cat. Проверка empty() нужна, когда
backspace идёт первым: для ##hi двум # нечего стирать, и программа печатает
hi. Без этой проверки pop() на пустом стеке сломал бы программу.
Пары, которые исчезают
В некоторых задачах две одинаковые соседние буквы
исчезают вместе, а буквы по обе стороны от них становятся соседями и тоже могут
исчезнуть. Стек сам справляется со всей цепной реакцией: сравнивайте каждую новую
букву с вершиной и, если они равны, снимайте вершину вместо того, чтобы класть
букву.
В xyyxz исчезают два y, из-за чего встречаются два x, и они тоже исчезают:
остаётся z. Когда пара исчезает, новая вершина — это как раз та буква, которая
только что стала следующим соседом. Чтобы напечатать оставшиеся буквы по
порядку, перелейте стек во второй, как в программе с backspace.
Проверка скобок
Дана строка из скобок (, ), [, ], { и }. Она правильная, если
каждая открывающая скобка закрыта скобкой того же вида и пары правильно
вложены: ([]{()}) — правильная, а ([)] — нет. Выведите YES, если строка
правильная, и NO, если нет.
Ввод
Вывод
Первой должна закрыться та скобка, которую открыли последней, — а
«последняя» и есть вершина стека.
Для ([]{()}) программа печатает YES. Строка может сломаться ровно тремя
способами — по одному на каждую проверку:
Строка
Где ломается
([)]
) приходит, когда на вершине [: не тот вид
())
вторая ) приходит, когда стек пуст: закрывать нечего
(()
строка кончается, а ( всё ещё в стеке: её не закрыли
Теперь стек — это вы. Кладите, снимайте и останавливайте каждую неправильную
строку ровно на той скобке, где она ломается:
Будьте стекомпопробуй!
Один вид скобок: хватит счётчика
Если скобки бывают только ( и ), все элементы стека — одна и та же (. Тогда
важен только размер стека, а его можно хранить в int:
В конце broken считает ), которым не нашлось пары, а open — (, которые так
и не закрыли. Строка правильная, когда оба счётчика равны нулю; для ))((() оба
равны 2.
Постфиксный калькулятор
Мы пишем 3 + 4: операция стоит между числами. В постфиксной записи
операция стоит после них: 3 4 +. Выглядит странно, но такой записи не нужны
ни скобки, ни правила о том, какое действие выполняется первым, — всё говорит
порядок токенов. (6 - 2) * 3 — это 6 2 - 3 *, а 5 + (1 + 2) * 4 — это
5 1 2 + 4 * +.
Стек вычисляет такую запись за один проход:
число кладётся в стек;
операция снимает два последних числа и кладёт результат. Вершина — это
более позднее число y, под ним лежит более раннее x, а результат — это
x op y. Для - порядок важен: 6 2 - — это 4, а не −4.
В конце единственное число в стеке и есть ответ.
Постфиксный калькулятор: числа ждут в стеке, операция забирает два
C++
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5 ios_base::sync_with_stdio(false);
6 cin.tie(NULL);
7
8 vector<string> toks = {"6", "2", "-", "3", "*"};
9 stack<long long> st;
10 for (string tok : toks) {
11 if (tok == "+" || tok == "-" || tok == "*") {
12 long long y = st.top();
13 st.pop();
14 long long x = st.top();
15 st.pop();
16 if (tok == "+") {
17 st.push(x + y);
18 } else if (tok == "-") {
19 st.push(x - y);
20 } else {
21 st.push(x * y);
22 }
23 } else {
24 st.push(stoll(tok));
25 }
26 }
27 cout << st.top() << "\n";
28 return 0;
29}
Токены
строка 8
6 2 - 3 * — это постфиксная запись (6 - 2) * 3: каждая операция стоит после двух своих чисел.
toks5 ячеек
"6"
"2"
"-"
"3"
"*"
0
1
2
3
4
st (дно → вершина)0 ячеек
tok—y—x—
нажми пуск
1 / 31
Теперь то же самое в виде задачи:
В первой строке — m, во второй — m токенов постфиксной записи через
пробел. Токен — это целое число, возможно отрицательное, или одна из операций
+, - и *. Выведите значение выражения.
Ввод
Вывод
Читайте каждый токен как string. Токен — операция, только если он в точности
равен "+", "-" или "*"; всё остальное — числа, в том числе -3: он
начинается со знака минус, но это число, а не операция. stoll(tok) превращает
текст в long long:
Для 9 токенов 5 1 2 + 4 * + -3 - программа печатает 20: 5 + (1 + 2) · 4 — это
17, а 17 − (−3) — это 20. Храните в стеке long long: нескольких умножений
хватит, чтобы выйти за пределы int.
Стек, который знает свой минимум
В некоторых задачах у стека снова и снова спрашивают самый маленький элемент:
Дано q команд. push x кладёт x в стек; pop снимает верхний элемент,
а если стек пуст, ничего не делает; min печатает самый маленький элемент
в стеке или empty, если элементов нет.
Ввод
Вывод
Команд min могут быть тысячи, а добавления и снятия всё время меняют стек.
Просматривать весь стек ради каждой из них слишком долго.
Хитрость: храните вместе с каждым элементом наименьшее значение от него и до
дна. Когда вы кладёте x, это min(x, минимум, записанный у старой вершины).
Когда снимаете, ничего исправлять не нужно: элементы ниже не менялись, поэтому
минимум, записанный у новой вершины, по-прежнему верен. Ответ — всегда
st.top().second.
После push 6, push 9 и push 2 записанные минимумы — 6, 6 и 2, поэтому
min печатает 2. После одного pop он печатает 6; когда ничего не
осталось — empty; а после push 7 — 7.
Проверьте себя
Проверка скобок стеком
Открывающая скобка: положите её в стек. Она ждёт свою пару.
Закрывающая скобка: на вершине стека должна лежать её пара. Если стек пуст или на вершине скобка другого вида, строка ломается прямо здесь.
Иначе снимите вершину: пара сложилась, и ждать теперь начинает скобка под ней.
В конце стек должен быть пуст. Всё, что в нём осталось, — скобки, которые так и не закрыли.
А вы знали?
Постфиксную запись называют ещё обратной польской записью — в честь польского
логика Яна Лукасевича, который в 1920-х годах писал операции перед числами,
чтобы обходиться без скобок. С 1968 года компания Hewlett-Packard выпускала
калькуляторы, работавшие в постфиксной записи: чтобы сложить 3 и 4, нажимали 3,
ENTER, 4, + — а внутри стек делал ровно то же, что программа из этого урока.
stack<int> st; // пустой стек целых чисел
проверь себя1 балл
С пустым stack<int> st выполняют push(5), push(8), pop(), push(3), push(1), pop(). Чему теперь равно st.top()?
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
int x = st.pop(); снимает верхний элемент со стека и сохраняет его в x.
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
Чему равно постфиксное выражение 4 2 5 * + 1 -?
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
Стек хранит пары (значение, наименьшее значение отсюда и до дна). В него кладут 5, 3, 8 и 1, а потом дважды снимают. Чему теперь равно st.top().second?
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
Какая из этих скобочных строк правильная?
Выберите один ответ
Войдите, чтобы ответить и сохранить прогресс.Войти
cay#t
cat
([]{()})
YES
9
5 1 2 + 4 * + -3 -
20
11
push 6
push 9
push 2
min
pop
min
pop
pop
min
push 7
min
2
6
empty
7
#include <bits/stdc++.h>using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; stack<int> st; for(int i = 0; i < n; i++){ int x; cin >> x; st.push(x); // самое новое число кладётся наверх} while(!st.empty()){ cout << st.top()<< " "; // смотрим на вершину... st.pop(); // ...потом снимаем её} cout << "\n"; return 0;}
#include <bits/stdc++.h>using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); string keys; cin >> keys; stack<char> text; // уже набранные буквы, последняя — наверху for(char c : keys){ if(c == '#'){ if(!text.empty()){ text.pop(); // backspace: снимаем верхнюю букву}} else{ text.push(c); // буква ложится наверх}} stack<char> poured; // переливание ещё раз переворачивает порядок while(!text.empty()){ poured.push(text.top()); text.pop();} while(!poured.empty()){ cout << poured.top(); // теперь наверху первая набранная буква poured.pop();} cout << "\n"; return 0;}
stack<char> st; // буквы, которые ещё осталисьfor(char c : s){ if(!st.empty() && st.top() == c){ st.pop(); // c и вершина исчезают вместе} else{ st.push(c);}}
#include <bits/stdc++.h>using namespace std;bool matches(char open, char close){ return(open == '(' && close == ')') ||(open == '[' && close == ']') ||(open == '{' && close == '}');}int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); string s; cin >> s; stack<char> st; bool ok = true; for(char c : s){ if(c == '(' || c == '[' || c == '{'){ st.push(c); // открывающая скобка ждёт в стеке} else if(st.empty() || !matches(st.top(), c)){ ok = false; // закрывать нечего или не тот вид break;} else{ st.pop(); // пара сложилась}} if(!st.empty()){ ok = false; // какие-то скобки так и не закрыты} cout <<(ok ? "YES" : "NO")<< "\n"; return 0;}
int open = 0, broken = 0;for(char c : s){ if(c == '('){ open++; // ещё одна ( ждёт} else if(open > 0){ open--; // эта ) закрывает ждущую (} else{ broken++; // этой ) нечего закрывать}}
#include <bits/stdc++.h>using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int m; cin >> m; stack<long long> st; for(int i = 0; i < m; i++){ string tok; cin >> tok; if(tok == "+" || tok == "-" || tok == "*"){ long long y = st.top(); // более позднее число st.pop(); long long x = st.top(); // более раннее число st.pop(); if(tok == "+"){ st.push(x + y);} else if(tok == "-"){ st.push(x - y);} else{ st.push(x * y);}} else{ st.push(stoll(tok)); // число: текст -> long long}} cout << st.top()<< "\n"; return 0;}
#include <bits/stdc++.h>using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int q; cin >> q; stack<pair<int, int>> st; // (значение, наименьшее значение отсюда до дна) for(int i = 0; i < q; i++){ string cmd; cin >> cmd; if(cmd == "push"){ int x; cin >> x; int low = x; if(!st.empty()){ low = min(x, st.top().second);} st.push({x, low});} else if(cmd == "pop"){ if(!st.empty()){ st.pop(); // нижние элементы по-прежнему знают свой минимум}} else{ if(st.empty()){ cout << "empty\n";} else{ cout << st.top().second<< "\n";}}} return 0;}