Понятие очереди. Простая очередь

Очередь – это структура данных, реализующая по принципу «первый пришел – первый ушел, последний пришел – последний ушел»[32]. Т.е. новые элементы добавляются в конец очереди, а удаление элементов происходит от начала очереди.

Рис. 24. Модель очереди FIFO

Операции с очередями в языке C++ реализуются с помощью STL-контейнера, подключаемого в заголовочном файле queue. Рассмотрим применение основных операций с очередями на примере:

#include <iostream>

#include <queue>           // заголовочный файл очереди

using namespace std;

int main(){

queue<string> Crimea;  // пустая очередь Crimea (тип string)

// добавляем в очередь имена городов (тип string)

Crimea.push("Симферополь");

Crimea.push("Ялта");

Crimea.push("Евпатория");

Crimea.push("Феодосия");

Crimea.push("Керчь");

Crimea.push("Севастополь");

cout << "Всего элементов в очереди: " << Crimea.size() << endl;

cout << "Первый и последний: " << Crimea.front() << " и "

<< Crimea.back() << endl;

while(!Crimea.empty()){ //вывод элементов очереди по порядку

   cout << Crimea.front() << " ";

   Crimea.pop();      // удаляем один элемент в очереди

}

}

В результате работы программы будет выведено

Всего элементов в очереди: 6

Первый и последний: Симферополь и Севастополь

Симферополь Ялта Евпатория Феодосия Керчь Севастополь

Приоритетная очередь

Приоритетная очередь является разновидностью обычной очереди с одной лишь разницей, что элементы в ней автоматически сортируются. При этом в свойствах очереди отсутствуют ссылки front() и back(). Вместо них применяется свойство top() – ссылка на начальный элемент приоритетной очереди.

#include <iostream>

#include <queue>   // заголовочный файл очереди

using namespace std;

int main(){

priority_queue<float> continent; // создаем приоритетную очередь

// вставка в очередь площадей континентов (млн. кв. км.)

continent.push(17.82); // Южная Америка

continent.push(13.66); // Антарктида

continent.push(53.89); // Евразия

continent.push(7.69); // Австралия

continent.push(24.2); // Северная Америка

cout << "Всего элементов в очереди: " << continent.size() << endl;

cout << "Площадь континентов по убыванию: ";

// выгружаем элементы очереди по одному, в порядке их приоритета

while(!continent.empty()) {

   cout << continent.top() << " ";

   continent.pop();

}

}

В результате работы программы будет выведено

Всего элементов в очереди: 5

Площадь континентов по убыванию: 53.89 24.2 17.82 13.66 7.69

Задача №153.  Школьный бал

Финалом выпускного бала станет исполнение школьного вальса. Для этого необходимо создать как можно больше традиционных танцевальных пар, причем в каждой паре юноша не может быть ростом ниже партнёрши. В массиве A[1..N] рост всех юношей, а в массиве B[1..M] – девушек. Какое наибольшее количество танцевальных пар можно создать при указанных выше ограничениях?

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

В першой строке находятся числа N і M, во второй N значений A[i] (i=1..N), в третьей – M значений B[j] (j=1..M). Все числа натуральные, не превышающие 10000.

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

Одно число - максимально возможное количество пар.

Пример

Ввод	Вывод
3 4 7 3 8 5 5 6 7	2

Решение

#include <queue>

#include <iostream>

using namespace std;

int n, m, tmp, cnt;

int main(){

priority_queue<int> a, b;

cin >> n >> m;

while(n--){      // очередь с убыванием роста юношей

   cin >> tmp;

   a.push(tmp);

}

while(m--){      // очередь с убыванием роста девушек

   cin >> tmp;

   b.push(tmp);

}

while(b.size() && a.size()){

   if(a.top() >= b.top()){

       cnt++;

       a.pop();

   }

   b.pop();

}

cout << cnt;

}

Задача №154.  TopCoder (acmp.ru)

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

Некоторые из вас, наверное, слышали о сайте http://www.topcoder.com, на котором часто проводятся различные соревнования по программированию.

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

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

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

Первая строка содержит целое число n (1 ≤ n ≤ 100) - число комнат. Далее следуют n описаний итоговых результатов в комнатах.

Результаты в i-ой комнате заданы в следующем формате. Первая строка содержит целое число n_i (1 ≤ n_i ≤ 20)- количество участников в i-ой комнате. Следующие n_i строк содержат информацию о выступлениях участников. j+1-ая строка описания результатов в i-ой комнате содержит информацию об участнике, занявшем в i-ой комнате j-ое место: разделенные одним пробелом вещественное число totalⁱ_j (-5000 ≤ totalⁱ_j ≤ 10000) и строку nameⁱ_j - соответственно количество набранных участником баллов и его имя. Имя участника имеет длину от 1 до 25 и может содержать только буквы латинского алфавита, цифры и символ подчеркивания. При этом первый символ имени не является цифрой. Все вещественные числа заданы с двумя знаками после десятичной точки.

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

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

В первой строке выведите N - суммарное число участников. На следующих N строках выведите информацию о выступлении участников. (k+1)-ая строка описания суммарных результатов должна содержать информацию об участнике, занявшем k-ое место: разделенные одним пробелом вещественное число total_k с двумя знаками после десятичной точки и строку name_k - соответственно количество набранных участником баллов и его имя.

Не забудьте, что участники должны быть упорядочены по невозрастанию набранных ими баллов.

Пример

Ввод	Вывод
2 6 909.94  Savior 439.51  tywok 130.52  LimberG 0.00  BryanChen 0.00  angsa -75.00  The_Hedgehog 5 867.15  Ying 448.12  natori 195.32  aubergineanode 0.00  shalinmangar -25.00  Excilus	11 909.94  Savior 867.15  Ying 448.12  natori 439.51  tywok 195.32  aubergineanode 130.52  LimberG 0.00  angsa 0.00  shalinmangar 0.00  BryanChen -25.00  Excilus -75.00  The_Hedgehog

Решение

#include <iostream>

#include <iomanip>

#include <queue>

using namespace std;

 

int main(){

int n, k;

float p;

string s;

priority_queue<pair<float, string> > q;

cin >> n;

while(n--){      // записываем данные участников в очередь

   cin >> k;

   while(k--){

       cin >> p >> s;

       q.push(make_pair(p, s));

   }

}

 

cout << q.size() << endl << fixed << setprecision(2);

 

while(!q.empty()){ // извлекаем данные из очереди

   cout << q.top().first << ' ' << q.top().second << endl;

   q.pop();

}

}

Задача №155.  Бегуны

Даны положительные числа a₁, a₂, …a_N. Числа – это измеренные в сотых долях секунды результаты спортсменов в беге на 100 м. Составить команду из K лучших бегунов для участия в олимпиаде.

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

В первой строке через пробел два целых положительных числа N и K. N ≤ 1000, K ≤ N

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

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

Гарантируется, что результаты всех бегунов различны

Пример

Ввод	Вывод
6 3 11.77 12.34 12.14 11.15 11.16 11.40	4 5 6

Решение

(Первое решение – приоритетная очередь) Данные бегуна представляют собой структуру из двух чисел – результата бегуна (с плавающей точкой) и его номера (целое). Воспользуемя для их хранения стандартным контейнером pair.

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

#include <iostream>

#include <queue>          // заголовочный файл очереди

using namespace std;

int main() {

                     // создаем приоритетную очередь

priority_queue<pair<float, int> >  rq;

 

int n, k, i;

float time;

cin >> n >> k;

for(i = 0; i < n; i++){ // записываем результаты в очередь

   cin >> time;

   rq.push(make_pair(-time, i + 1));

}

while(k--){           // забираем первые k элементов

   cout << rq.top().second << ' ';

   rq.pop();

}     

}

(Второе решение – частичная сортировка) Будем выбирать наименьшее значение из всех, обменивая его с начальным, затем наименьшее из оставшихся и т. д.

#include <iostream>

using namespace std;

int main(){

pair<float, int> r[1000];

int n, k;

cin >> n >> k;

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

   cin >> r[i].first;

   r[i].second = i + 1;

}

for(int i = 0, imin; i < k; i++){

   imin = i;

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

       if(r[imin].first > r[j].first) imin = j;

   swap(r[imin], r[i]);

   cout << r[i].second << ' ';

}

}

Сложность такого алгоритма будет O(K×N). Это, пожалуй, наиболее рациональный алгоритм по времени выполнения, если в задаче могут использоваться большие значения величины N и малые величины K. При описанных в условии ограничениях проще всего было бы реализовать решение третьим способом (сложность O(N×logN):

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

pair<float, int> r[1000];

int n, k, i;

cin >> n >> k;

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

   cin >> r[i].first;

   r[i].second = i + 1;

}

sort(r, r + n);

for(i = 0; i < k; i++)

   cout << r[i].second << ' ';

}

Дек

Дек (deque) — это сокращенная фраза «double-ended-queue», что, в переводе с английского, означает — двусторонняя очередь. Контейнер deque очень похож на контейнер — vector. Как и vector, deque является динамическим массивом.

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

Для использования дека нужно подключить заголовочный файл — <deque>:

#include <deque>

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

#include <iostream>

#include <deque>   // заголовочный файл дека

#include <iterator> // заголовок итераторов

using namespace std;

int main(){

int dsize;

cout << "Введите размер поезда (>=2): ";

cin >> dsize;

deque<int> train(dsize); // создаем дек и резервируем память

cout << "Номера вагонов от 3 до " << 2 + dsize;

for(int i = 0; i < train.size(); i++) train[i]=3+i;

cout << "\n Убираем вагон сзади";

train.pop_back();

cout << "\n Убираем вагон спереди";

train.pop_front();

cout <<"\n Добавляем спереди вагон №1";

train.push_front(1);

cout << "\n Добавляем сзади вагон №100";

train.push_back(100);

cout << "\n Поезд: ";

if (!train.empty()) // если дек не пуст, выводим его элементы

   copy(train.begin(),

        train.end(),

        ostream_iterator<int>(cout," "));

}

Лучше понять практическое использование деков поможет следующая задача.

Задача №156.  Полка

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

У Андрея есть младший брат Ванечка, который очень любит смотреть мультики. Ванечка вечно разбрасывал по дому и терял свои DVD с мультиками. Поэтому на день рождения Андрей подарил брату длинную полку для того, чтобы Ванечка ставил на нее свои диски. Чтобы на полке был порядок, Андрей просил Ванечку соблюдать простой порядок:

· если на полке нет ни одного диска, то Ванечка просто ставит его;

· если диск есть, то Ванечка ставит диск либо справа, либо слева от уже расставленных;

· забирает диски он так же, то есть снимает только с правого или левого края.

И теперь Андрей хочет узнать, выполнил Ванечка его инструкции или нет.

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

В первой строке входного файла INPUT.TXT указано целое число N (1 ≤ N ≤ 10000) - количество операций, которые выполнил Ванечка. Далее в N строках находится информация об операциях. Каждая операция постановки диска на полку описывается парой чисел. Первое из них (1 или 2) показывает, что диск ставится с левого края или с правого края соответственно. Второе целое число (от 0 до 10000) обозначает номер диска. Операции снятия диска с полки описывается одним числом 3 или 4, обозначающим с левого и правого края полки соответственно снимается диск.

В начальный момент полка пуста. Гарантируется, что последовательность операций корректна, нет команд снятия диска с пустой полки.

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

В выходной файл OUTPUT.TXT для каждой операции снятия диска с полки выведите его номер.

Примеры

№	INPUT.TXT	OUTPUT.TXT
1	5 1  1 2  2 1  3 3 4	3 2
2	2 1  1 3	1

Решение

#include <fstream>

#include <deque>

using namespace std;

 

int main() {

ifstream cin("input.txt");

ofstream cout("output.txt");

int n, op, disk;

cin >> n;

deque<int> shelf;               // дек, имитирующий полку

while(n--){

     cin >> op;

     if(op < 3){               // поставитьдиск

           cin >> disk;

           if(op == 1) shelf.push_front(disk);

           else shelf.push_back(disk);

     } else {                  //снять диск

           if(op == 3) {

                disk = shelf.front();

                shelf.pop_front();

           } else {

                disk = shelf.back();

                shelf.pop_back();

           }

           cout << disk << ' ';

     }

}

}

Задача №157.  Игра в числа (acmp.ru)

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

Игра в числа ведётся на одномерном массиве целых положительных чисел. Перед началом, жеребьёвкой определяется, кто будет ходить первым (первый игрок), а кто – вторым (второй игрок). Процесс игры состоит в том, что игроки по очереди (сначала первый игрок, затем второй, следом опять первый и так далее) вычёркивают числа из массива. Вычеркнуть можно только число, находящееся в конце или начале оставшегося массива. При этом всегда вычёркивается максимальное число из этих двух. Если первое и последнее числа массива равны, то вычёркивается первое. Игра продолжается до того момента, пока не будут вычеркнуты все числа. Каждое вычеркнутое число идёт в актив тому игроку, который его вычеркнул. После окончания игры каждый игрок суммирует вычеркнутые им числа. Победителем объявляется тот, кто наберет больше очков.

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

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

В первой строке находится одно целое число N – количество чисел в массиве (1 ≤ N ≤ 10⁴). Во второй строке находятся N целых положительных чисел из диапазона [1, 32000], разделённых пробелом.

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

Выведите два числа, разделенные двоеточием. Первое число – количество очков, набираемых первым игроком при игре на этом массиве, второе число – для второго.

Примеры

№	Ввод	Вывод
1	5 4  4  1  5  4	9:9
2	1 1234	1234:0

Решение

#include <iostream>

#include <deque>                     // описание дека

usingnamespacestd;

intn, x, y, s[2];

intmain(){

deque<int> dq;       // создаём пустой дек

cin >> n;                 // и заполняе его числами

for(; n; n--){

     cin >> x;

     dq.push_back(x);

}

do{                       // считываем числа

     x = dq.front();

     y = dq.back();

     if(y > x) dq.pop_back();

     else dq.pop_front();

     s[n] += max(x, y);   // добавляем теущему игроку

     n ^= 1;              // меняем номер игрока 0 или 1

} while (dq.size());

cout << s[0] << ':' << s[1];

}

Стеки