: numsystems, : stack, : Top
Язык программирования C++ содержит библиотеку STL (Standart template library, стандартная
библиотека шаблонов). В библиотеку STL входят шаблоны для реализации стеков, деков, очередей
для произвольных типов данных. Например, чтобы создать стек целых чисел необходимо использовать
тип stack<int>
, для создания стека строк – stack<string>
, для создания стека
объектов типа Person
– stack<Person>
.
Рассмотрим подробнее стеки, очереди, деки в STL. Описание шаблонов stack
, queue
, deque
содержится в одноименных заголовочных файлах, то есть для использования этих структур необходимо
подключить один из трех заголовочных файлов:
#include<stack> #include<queue> #include<deque>
После этого можно создавать объекты на основе данных шаблонов:
stack<int> S; // Стек объектов типа int queue<double> Q; // Очередь объектов типа double deque<string> D; // Дек объектов типа string
После этого с объявленными объектами можно выполнять операции, например:
S.push(3); // Положить в стек S число 3 Q.size(); // Узнать размер очереди Q D.pop_front(); // Удалить элемент из начала дека D
Рассмотрим более подробно список методов, присущих шаблонам
stack<type>
, queue<type>
, deque<type>
(type
T – это тип данных, хранящихся в соответствующей структуре).
Обратите внимание, что методы удаления pop
, pop_front
и pop_back
в
STL не возвращают значения. Кроме того, реализации стека, очереди, дека в STL не содержат
проверок на возникновение ошибок, то есть за некорректую работу программы при вызове
операций на пустом стеке отвечает сам пользователь.
Метод очистки clear
существует только у дека.
stack<type>
queue<type>
deque<type>
Во всех задачах этого листка (кроме "Пробы пера") данные читаются из файла и выводятся в файл.
Решите задачу I предыдущего листка, используя стандартный deque<int>
.
Решение сдайте как задачу I в предыдущий контест.
Входной файл: ain.txt
Выходной файл: aout.txt
Программа на вход получает список школьников следующего вида:
9 Иванов 10 Петров 11 Сидоров 9 Григорьев 9 Сергеев 10 Яковлев
В каждой строке сначала записан номер класса (число, равное 9, 10 или 11), затем (через пробел) – фамилия. Необходимо вывести список по классам: сначала всех учащихся 9 класса, затем – 10, затем – 11. Внутри одного класса порядок вывода должен быть таким же, как на входе:
9 Иванов 9 Григорьев 9 Сергеев 10 Петров 10 Яковлев 11 Сидоров
Входной файл: bin.txt
Выходной файл: bout.txt
В игре в пьяницу карточная колода раздается поровну двум игрокам. Далее они вскрывают по одной верхней карте, и тот, чья карта старше, забирает себе обе вскрытые карты, которые кладутся под низ его колоды. Тот, кто остается без карт – проигрывает.
Для простоты будем считать, что все карты различны по номиналу, а также, что самая младшая карта побеждает самую старшую карту ("шестерка берет туза").
Игрок, который забирает себе карты, сначала кладет под низ своей колоды карту первого игрока, затем карту второго игрока (то есть карта второго игрока оказывается внизу колоды).
Напишите программу, которая моделирует игру в пьяницу и определяет, кто выигрывает. В игре участвует 10 карт, имеющих значения от 0 до 9, большая карта побеждает меньшую, карта со значением 0 побеждает карту 9. Программа получает на вход две строки: первая строка содержит 5 карт первого игрока, вторая строка содержит 5 карт второго игрока. Карты перечислены сверху вниз, то есть каждая строка начинается с той карты, которая будет открыта первой.
Программа должна определить, кто выигрывает при данной раздаче и вывести слово first
или second
,
после чего вывести количество ходов, сделанных до выигрыша.
Если на протяжении 106 ходов игра не заканчивается, программа должна вывести слово
botva
.
Пример:
Вход Выход 1 3 5 7 9 second 5 2 4 6 8 0
Входной файл: cin.txt
Выходной файл: cout.txt
Рассмотрим последовательность, состоящую из круглых, квадратных и фигурных скобок.
Программа дожна определить, является ли данная скобочная последовательность правильной.
Если последовательность правильная, то программа должна вывести строку yes
, иначе
строку no
.
Примеры
Вход Выход ([{}]) yes ([)] no ()() yes ())( no
Формальное определение. Пустая последовательность явлется правильной. Если A
–
правильная, то последовательности (A)
, [A]
, {A}
– правильные.
Если A
и B
– правильные последовательности, то последовательность AB
–
правильная.
Указание: заведите стек, в который будут помещаться все открывающиеся скобки.
Входной файл: din.txt
Выходной файл: dout.txt
В постфиксной записи (или обратной польской записи) операция записывается после двух операндов.
Например, сумма двух чисел A
и B
записывается как A B +
. Запись
B C + D *
обозначает привычое нам (B + C) * D
, а запись A B C + D * +
означает A + (B + C) * D
. Достоинство постфиксной записи в том, что она не требует
скобок и дополнительных соглашений о приоритете операторов для своего чтения.
Дано выражение в постфиксой записи, содержащее однозначные числа, операции +
, -
, *
.
Вычислите значение записанного выражения.
Пример
Ввод Вывод 8 9 + 1 7 - * -102
Входной файл: ein.txt
Выходной файл: eout.txt
На складе хранятся контейнеры с товарами N различных видов. Все контейнеры составлены в N стопок. В каждой стопке могут находиться контейнеры с товарами любых видов (стопка может быть изначально пустой).
Автопогрузчик может взять верхний контейнер из любой стопки и поставить его сверху в любую стопку. Необходимо расставить все контейнеры с товаром первого вида в первую стопку, второго вида – во вторую стопку и т.д.
Программа должна вывести последовательность действий автопогрузчика или сообщение о том, что задача решения не имеет.
В первой строке входных данных записано одно натуральное число N, не превосходящее 500. В следующих N строках описаны стопки контейнеров: сначала записано число ki – количество контейнеров в стопке, а затем ki чисел виды товара в контейнерах в данной стопке, снизу вверх. В каждой стопке вначале не более 500 контейнеров (в процессе переноса контейнеров это ограничение может быть нарушено).
Программа должна вывести описание действий автопогрузчика: для каждого действия напечатать два числа из какой стопки брать контейнер и в какую стопку класть. (Обратите внимание, что минимизировать количество операций автопогрузчика не требуется.) Если задача не имеет решения, необходимо вывести одно число 0. Если контейнеры изначально правильно размещены по стопкам, то разрешается оставлять выходной файл пустым.
Пример
Ввод Вывод 3 1 2 4 1 2 3 2 1 3 0 1 2 0
Объяснение примера. Изначально в первой стопке лежат четыре контейнера – снизу контейнер с товаром первого вида, над ним – с товаром второго вида, над ним третьего, и сверху еще один контейнер с товаром второго вида. Вторая и третья стопки – пусты.