Понятие стека. Основные действия со стеком

Стек (англ. stack — стопка; читается стэк) — список элементов, организованных по принципу «последним пришёл — первым вышел»[33].

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

Рис. 25. Обработка стека

Задачи со стеками

Задача №158.  Спичрайтер Йоды

(Время: 1 сек. Память: 16 Мб)

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

Это относится и к главе Ордена джедаев магистру Йоде, известному нам своими подвигами в «Звездных войнах». На первый взгляд может показаться, что спичрайтеру Йоды приходится тяжелее других: все-таки речь магистра своеобразна и ее изучение требует серьезных усилий. На самом деле все несколько проще. Спичрайтеру Йоды достаточно сначала придумать речь для обычного человека, после чего поменять порядок слов в каждом предложении на обратный. В силу того, что алгоритм преобразования обычной речи в речь магистра Йоды достаточно однообразен, спичрайтер решил автоматизировать этот процесс и попросил Вас написать программу, которая будет преобразовывать речь, составленную им для обычного человека в речь для Йоды.

Входные данные

В единственной строке входного файла INPUT.TXT задана речь, составленная спичрайтером. Речь состоит из предложений, отделенных друг от друга точками (точка ставится сразу после последнего слова в предложении). Каждое предложение состоит из слов. Предложение содержит, по крайней мере, одно слово. Соседние слова разделены ровно одним пробелом. Слово – непустая последовательность строчных латинских букв. Строка не содержит лишних пробелов. Гарантируется, что строка не пуста и ее длина не превосходит 20000 символов.

Выходные данные

В выходной файл OUTPUT.TXT выведите преобразованную для Йоды речь в соответствии с форматом входных данных. Следует строго соблюдать формат вывода речи, описанный во входных данных.

Пример

INPUT.TXT	OUTPUT.TXT
you should solve this problem. its easy.	problem this solve should you. easy its.

Решение

#include <fstream>

#include <stack>

using namespace std;

int main() {

ifstream cin("input.txt");

ofstream cout("output.txt");

string s;

stack<string> q;

while (cin >> s){

   int i = s.length() - 1;

   if(s[i] == '.'){

       cout << s.substr(0, i);

       while(q.size()){

           cout << ' ' << q.top();

           q.pop();

       }

       cout << ". ";

   } else q.push(s);

}

}

Задача №159.  Белка и бамбук (e-olymp)

(СПбГУ, 2010)

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

Бамбук — это трубка, один конец которой закрыт, а с другого конца можно класть или вынимать жёлуди. Диаметр трубки достаточно мал, поэтому если положить в неё жёлуди в определённом порядке, вынимать их можно только в обратном порядке.

Когда белка находит жёлудь, она сразу кладёт его в бамбук. Кроме того, время от времени голод заставляет белку достать один жёлудь из бамбука и съесть его; из-за устройства бамбука это будет тот из желудей в нём, который белка нашла позже всего.

Белка очень любит копить жёлуди в бамбуке. Поэтому каждый раз, когда приходится доставать из бамбука очередной жёлудь, она испытывает печаль. Однако мы знаем, как можно её утешить! Жёлуди характеризуются для белки качеством — целым числом от 1 до 10⁶. Когда белка достала очередной жёлудь, ей будет приятно знать, каково максимальное значение качества для всех желудей, которые в бамбуке ещё остались. Ваша задача состоит в том, чтобы снабдить её такой информацией.

Входные данные

В первой строке ввода содержится одно целое число n — количество событий (1 ≤ n ≤ 100000). Каждая из следующих n строк содержит по числу, описывающему событие. Если число положительное, то оно означает, что белка нашла жёлудь и положила его в свой бамбук. Если же число равно нулю, то оно означает, что белка проголодалась и вынула один жёлудь из бамбука. Числа во входном файле целые и не превосходят 10⁶. Гарантируется, что после первого же запроса бамбук никогда не пуст.

Выходные данные

Для каждого доставания жёлудя из бамбука выведите одно целое число — максимальное значение качества для всех желудей, оставшихся в этот момент в бамбуке.

Пример

Ввод	Вывод
8 3 2 4 0 4 3 0 0	3 4 3

Решение

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

Например,

желуди (в порядке добавления)	3	2	1	4	2	4	5	1
состояние стека	3	3	3	4	4	4	5	5

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

#include <iostream>

#include <stack>

using namespace std;

int n, squirrel; 

int main() {

cin >> n >> squirrel;

stack<int> stk;

stk.push(squirrel);

for(int i = 1; i < n; i++){

   cin >> squirrel;

   if(!squirrel){

       stk.pop();

       cout << stk.top() << endl;

   } else stk.push(max(squirrel,stk.top()));

}

}

То же самое решение с реализацией стека через массив

#include <iostream>

using namespace std;

int n, stk = 1, squirrel, a[100001]; 

int main() {

cin >> n >> a[0];

for (int i = 1; i < n; i++){

   cin >> squirrel;

   if (!squirrel) cout << a[--stk - 1] << endl;

   else a[stk] = max(squirrel, a[stk++ - 1]);

}

}

Задача №160.  Рельсы

В городе PopPush находится известная железнодорожная станция. Страна, где расположен город, невероятно холмистая. Станция была построена в прошлом веке. К сожалению, в то время средства для постройки были крайне ограничены, поэтому удалось построить только одну железнодорожную колею. Более того, выяснилось, что станция может быть только тупиковой (см. рисунок), и из-за отсутствия свободного места может иметь только одну колею.

Рис. 26. Иллюстрация к задаче "Рельсы"

Местная традиция гласит, что каждый поезд, приходящий со стороны A продолжает свое движение в направлении B, при этом его вагоны перестанавливаются в некотором порядке. Предположим, что каждый поезд, приходящий из направления A, имеет n ≤ 1000 вагонов, пронумерованных в возрастающем порядке 1, 2, ..., n. Ответственный за реорганизацию вагонов должен знать, возможно ли перевезти их в направлении B в порядке a₁, a₂, ..., a_n. Помогите ему написать программу, которая определит, возможна ли такая перестановка вагонов. Вагоны можно отсоединять от поезда до того как они попадут на станцию и можно их отдельно передвигать пока все они не буду находиться в направлении B. На станции в любой момент времени может находиться любое количество вагонов. Но если вагон зашел на станцию, он уже не может вернуться на колею в направлении A, а также если он уже выехал в направлении B, то уже не может вернуться на станцию.

Входные данные

Состоит из нескольких тестов. Каждый тест кроме последнего описывает один поезд и возможно несколько требований для его реорганизации. Первая строка теста содержит целое число n. Каждая из следующих строк теста содержит перестановку 1, 2, ..., n. Последняя строка блока содержит 0.

Последний тест состоит из единственной строки, содержащей 0.

Выходные данные

Для каждой входной строки, содержащей перестановку чисел, следует вывести Yes, если можно совершить указанную перестановку вагонов, и No иначе. После вывода ответов на все перестановки каждого теста следует вывести пустую строку. Для последнего нулевого теста ничего выводить не следует.

Пример

Ввод	Вывод
5 1  2  3  4  5 5  4  1  2  3 0 6 6  5  4  3  2  1 0 0	Yes No   Yes

Решение

Обозначим за t номер последнего прошедшего вагона. Все вагоны от t до текущего рассматриваемого нужно поместить в стек. Если текущий рассматриваемый вагон находится вверху стека, то он просто проходит станцию и извлекается из стека. Если в стеке находится вагон с номером, большим чем текущий, то перестановка невозможна.

#include <iostream>

#include <stack>

#define SIZE 1001

using namespace std;

int n, m, a[SIZE];

bool validation(){

stack<int> stk;

int t = 1;

for(int i = 0; i < n; i++){

   if(!stk.empty() && a[i]==stk.top()) { // пропускаем вагон

       stk.pop();                    // через станцию

       continue;

   }

   if(!stk.empty()  &&  a[i] < stk.top()) return false;

   while(a[i] > t) stk.push(t++);   

   t++;

}

return true;

}

int main() {

do{

   cin >> n;

   if(!n) return 0;

   do{

       cin >> a[0];

       if(!a[0]){

           cout << "\n";

           break;

       }

       for(int i = 1; i < n; i++) cin >> a[i];

       cout << (validation() ? "Yes\n" : "No\n");

   } while (n);

} while(n);

}

Задача №161.  Персистентный стек

Лимит времени 1 секунда. Лимит использования памяти 64 MB.

Персистентными структурами данных мы будем называть такие структуры, что при всяком их изменении остается доступ ко всем предыдущим версиям этой структуры. Очевидно, что как один из вариантов (не самый лучший, конечно) можно рассматривать полное копирование всей структуры при каждом изменении. Это чрезвычайно неэффективно как по памяти, так и по времени работы. Данный способ можно применять лишь  на стадии тестирования более сложной организации структуры.

Реализуйте персистентный стек.

Входные данные

Первая строка содержит количество действий n (1 ≤ n ≤ 200000). В строке номер i + 1 содержится описание действия i:

t  m - добавить в конец стека номер t (0 ≤ t < i) число (0 < m ≤ 1000);

t  0 - удалить последний элемент стека номер t (0 ≤ t < i). Гарантируется, что стек t не пустой.

В результате действия i, описанного в строке i + 1, создаётся стек номер i. Изначально имеется пустой стек с номером ноль.

Все входные числа целые.

Выходные данные

Для каждой операции удаления выведите удалённый элемент в отдельной строке.

Входные данные	Выходные данные
8 0  1 1  5 2  4 3  2 4  3 5  0 6  6 1  0	3 1

Решение

Реализовано на основе массива

#include <iostream>

#define SIZE 200001

int main() {

int stk[SIZE], ptr[SIZE], n, t, m;

std::cin >> n;

stk[0] = ptr[0] = 0;

for (int i = 1; i < n + 1; i++){

   std::cin >> t >> m;

   if (m){

       stk[i] = m;

       ptr[i] = t;

   } else{

       std::cout << stk[t] << "\n";

       stk[i] = stk[ptr[t]];

       ptr[i] = ptr[ptr[t]];

   }

}

}

Функции

До сих пор мы писали программы единым, функционально неделимым, кодом. Алгоритм программы находился в главной функции, причём других функций в программе не было. Мы писали маленькие программы, поэтому не было потребности в объявлении своих функций. Для написания больших программ, опыт показывает, что лучше пользоваться функциями. Программа будет состоять из отдельных фрагментов кода, под отдельным фрагментом кода понимается функция.

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

Перед вызовом функция должна быть обязательно описана. Описание функции состоит из заголовка и тела функции:

 

тип имя_функции (список_переменных){

тело_функции

}

 

Заголовок функции содержит:

1. тип возвращаемого функцией значения, он может быть любым. Если функция не возвращает значения, указывают тип void;

2. имя_функции, с которым она будет вызываться;

3. список_переменных — перечень передаваемых в функцию аргументов, которые отделяются друг от друга запятыми; для каждой переменной из списка указывается тип и имя;

Тело функции представляет собой последовательность описаний и операторов, заключенных в фигурные скобки.

Пример использования функции:

#include <iostream>

using namespace std;

 

void example_function(){  // описание функции

cout << "Hello, world" << endl;

}

 

int main(){

example_function(); // Вызов функции

return 0;

}

Аргумент функции — это значение, которое будет использовать вызываемая функция.

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

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

int f(int x = 5) { // функция f имеет пар-р x, по умолчанию равный 5

return x + 3;

}

Оператор return используется для возвращения вычисляемого функцией значения.

Задача №162.  Дробь (acmp.ru)

(Время: 1 сек. Память: 16 Мб)

Вася учится в третьем классе и сейчас он проходит тему «Простые дроби с натуральными числителем и знаменателем». Оказывается, что дробь называется правильной, если ее числитель меньше знаменателя, и несократимой, если числитель и знаменатель являются взаимно простыми. Вася очень любит математику и поэтому дома он решает много задач. В данный момент Вася ищет наибольшую правильную несократимую дробь, у которой сумма числителя и знаменателя равна N.

Требуется написать программу, которая поможет Васе решить эту задачу.

Входные данные

Одно целое число N (3 ≤ N ≤ 2∙10⁹).

Выходные данные

Два числа – числитель и знаменатель найденной дроби, разделенные пробелом.

Примеры

№	Ввод	Вывод
1	3	1 2
2	10	3 7

Решение

У правильной дроби числитель не может быть больше знаменателя и их НОД должен быть равен 1. Наибольшая правильная дробь получается при наибольшем числителе и наименьшем знаменателе.

#include <iostream>

int gcd(int x, int y){    // вспомогательная функция для

do{                         // определения НОД двух чисел

   if(x > y) x %= y; // по алгоритму Евклида

   else y %= x;

} while(x * y);

return x + y;

}

int main(){

int n, i;

std::cin >> n;

for(i = n / 2; gcd(i, n - i) > 1; i--);

   std::cout << i << ' ' << n - i;

}

Функция для определения НОД двух чисел по алгоритму Евклида уже реализована в библиотеке algorithm.

#include <iostream>

#include <algorithm> //функция __gcd(unsigned a, unsigned b)

int main(){

std::cout << std::__gcd(100,24);

return 0;

}

Данная программа выведет 4.

 

Задача №163.  Камень, ножницы, бумага

Рис. 27. Иллюстрация к задаче "Камень, ножницы, бумага"

Камень, ножницы, бумага — популярная игра на руках, известная во многих странах мира. Иногда используется как методика случайного выбора персоны для какой-либо цели (наряду с бросанием монеты, вытягиванием соломинок и т. п.).

Напомним Вам правила игры. Обычно, играют двое. Игроки считают вместе вслух «Камень… Ножницы… Бумага… Раз… Два… Три», одновременно качая кулаками. На счёт «Три» они одновременно показывают при помощи руки один из трёх знаков: камень, ножницы или бумагу. Знаки изображены на картинке. Победитель определяется по следующим правилам:

· Камень побеждает ножницы («камень затупляет или ломает ножницы»)

· Ножницы побеждают бумагу («ножницы разрезают бумагу»)

· Бумага побеждает камень («бумага накрывает или заворачивает камень»)

· Если игроки показали одинаковый знак, то засчитывается ничья.

Требуется написать программу, которая по жестам игроков будет определять исход игры.

Входные данные

В двух строках входного файла INPUT.TXT записаны жесты первого и второго игроков соответственно. Жест каждого игрока определяется строкой «rock», «scissors» или «paper», которые соответственно обозначают «камень», «ножницы» или «бумага» - возможные знаки, которые могут показать игроки.

Выходные данные

В выходной файл OUTPUT.TXT выведите «first», если побеждает первый игрок, «second» – в случае победы второго игрока и «draw», если игра завершилась в ничью.

Примеры

№	INPUT.TXT	OUTPUT.TXT
1	paper rock	first
2	rock paper	second
3	scissors scissors	draw

Решение

Опишем вспомогательную функцию, которая по предмету будет возвращать его номер. Например, для камня – 2, для ножниц – 1 и для бумаги соответственно 0.

#include <fstream>

usingnamespace std;

int p(string s){

return (s=="rock" ? 2 : (s=="scissors" ? 1 : 0));

}

int main(){

string s1, s2;

ifstream cin("input.txt");

ofstream cout("output.txt");

cin >> s1 >> s2;

int d = p(s1) - p(s2);

cout << (!d ? "draw" : (d==1 || d==-2 ? "first" : "second"));

}

Рассмотрим чуть более сложную модификацию этой задачи

Задача №164.  Спок и ножницы

Из двух названий предметов укажите того, кто выигрывает. Если названия совпадают, выведите “draw” (без кавычек)

Решение

Пронумеруем предметы по часовой стрелке, начиная от любого из них, например, камня

0 - камень

1 - ящерица

2 - Спок

3 - ножницы

4 - бумага

Для того, чтобы по названию предмета возвращать его номер, воспользуемся ассоциативным массивом map.

#include <iostream>

#include <map>

#define N 5

using namespace std;

 

string name[N] = {"stone", "lizard", "spock", "scissors", "paper"},

s1, s2;

map<string, int> v;

 

string winner(string x, string y) {

if(x==y) return "draw";

int a = v[x], b = v[y];

int num = (a - b) % 2 ? (a > b ? b : a) : (a > b ? a : b);

return name[num];

}

 

int main() {

for(int i = 0; i < N; i++)

   v[name[i]] = i;

   

cin >> s1 >> s2;

cout << winner(s1, s2);

}

Задача №165.  Римские числа

Лимит времени 0, 1 секунда

Лимит использования памяти 64 MiB

Посчитать сумму двух натуральных чисел A и B, записанных в римской системе счисления. Ответ также записать в римской системе счисления.

M = 1000, D = 500, C = 100, L = 50, X = 10, V = 5, I = 1. Все числа – не превышают 2000.

Входные данные

В строке записано два числа в римской системе счисления, между которыми стоит знак + .

Выходные данные

Единственное число – сумма чисел, записанное также в римской системе счисления. Числа в римской системе счисления записаны большими латинскими буквами.

Пример

Ввод	Вывод
III+IV	VII

Решение

#include <iostream>

#define DIGITS 13

using namespace std;

 

string r[DIGITS] = {"M", "CM","D", "CD", "C", "XC", "L",

               "XL", "X", "IX", "V", "IV", "I"};

int a[DIGITS] = {1000, 900, 500, 400, 100, 90, 50,

            40, 10, 9, 5, 4, 1};

 

int arab(string s){  // переход к арабским цифрам

int n = 0;

for(int i = 0; i < DIGITS; i++)

   while(r[i] == s.substr(0, r[i].length())){

       n += a[i];

       s.erase(0, r[i].length());

   }

return n;

}

 

string rome(int n){  // переход к римским цифрам

string s = "";

int i = 0;

for(int i = 0; n > 0; i++)

   while(n >= a[i]){

       s.append(r[i]);

       n -= a[i];

   }

return s;

}

 

main(){

string a, b;

cin >> a;

int k = a.find("+"); // найти позицию +

b = a.substr(k + 1); // всё, что после – число b в римской записи

a.erase(k);      // удаляем из a + и всё после него

cout << rome(arab(a) + arab(b)) << endl;

return 0;

}

Задача №166.  Счастливый билет – 2 (acmp.ru)

(Время: 1 сек. Память: 16 Мб)

Билет называется счастливым, если его можно разрезать прямой линией на две части таким образом, что оказавшиеся на них числа имеют одинаковые цифровые корни. Чтобы вычислить цифровой корень числа, его цифры складывают, если в результате получится число большее или равное 10, то цифры складывают снова и так далее, пока не получится число от 0 до 9 – это и есть цифровой корень. Например, билет с номером 0015420 является счастливым, так как, разрезав его на части с числами 0015 и 420 имеем у этих чисел одинаковые цифровые корни.

Требуется написать программу, которая определит, является ли счастливым билет с заданным номером.

Входные данные

Номер счастливого билета. Номер может начитаться с нулей и содержит не более 100 цифр.

Выходные данные

Выведите «YES», если билет счастливый и «NO» иначе.

Примеры

№	Ввод	Вывод
1	0015420	YES
2	00100	NO

Решение

Для каждой цифры числа с номером i найдем величину A_i – сумму всех цифр до i-ой включительно. Таким образом задача сведётся к проверке цифровых корней чисел A_i и A_n-i, где n –номер последней цифры.

#include <iostream>

using namespace std;

intn, a[101];

int root(int r){                     // нахождение цифрового

do{                       // корня числа r

     int s = 0;

     while(r){

           s += r % 10;

           r /= 10;

     }

     r = s;

} while(r > 9);

return r;

}

int main(){

string s;

cin >> s;

for(n = 0; s[n]; n++)           // находим суммы цифр до текущей

a[n] = (n ? a[n-1] : 0) + s[n] - '0';

--n;

for(int i = 0; i < n; i++) //проверяем цифровые корни

     if(root(a[i]) == root(a[n] - a[i])){

           cout << "YES";

           return 0;

     }

cout << "NO";

}

Задача №167.  Покер

Имеется 5 целых чисел. Среди них:

· если одинаковы 5, то вывести "Impossible", иначе

· если одинаковы 4, то вывести "Four of a Kind", иначе

· если одинаковы 3 и 2, то вывести "Full House", иначе

· если есть 5 последовательных, то вывести "Straight", иначе

· если одинаковы 3, то вывести "Three of a Kind", иначе

· если одинаковы 2 и 2, то вывести "Two Pairs", иначе

· если одинаковы 2, то вывести "One Pair", иначе

· вывести "Nothing".

Входные данные

5 целых чисел от 1 до 13, разделенных пробелом.

Выходные данные

Вывести результат тип карточной комбинации у игрока.

Примеры

№	INPUT.TXT	OUTPUT.TXT
1	1  3  9  3  2	One Pair
2	1  5  5  4  4	Two Pairs
3	1  5  2  4  3	Straight
4	10  11  12  13  1	Nothing

Решение

Использование функций при решении данной задачи существенно упрощает его ход и делает код более читабельным. Заведём вспомогательные функции целочисленную count() – счетчик карт одного типа с заданным количеством (т.е. двоек, троек и т.д.) и логическую straight() для определения соответствующей комбинации.

#include <iostream>

using namespace std;

int k, card[13] = {0,}; // массив карт

 

int count(int c){    // счетчик карт с заданным количеством

int r = 0;

for(int i = 0; i < 13; i++)

   if(card[i] == c) r++;

return r;

}

 

bool straight(){          //проверка стрейта

int r = 0;

for(int i = 0; i < 12; i++)

   if(card[i+1] == 1   &&  card[i] == 1) r++;

return r == 4;

}

 

int main(){

for(int i = 5; i--;){

   cin >> k;

   card[--k]++;

}

if(count(5)) cout << "Impossible";    //анализ игры

else if(count(4)) cout << "Four of a Kind";

else if(count(3) && count(2)) cout << "Full House";

else if(straight()) cout << "Straight";

else if(count(3)) cout << "Three of a Kind";

else if(count(2)==2) cout << "Two Pairs";

else if(count(2)) cout << "One Pair";

else cout << "Nothing";

}