Очередь и Дек - Язык программирования C++ для спортивного программирования
Неделя 10Стек, Очередь, Дек и Задачи на моделирование
Очередь и Дек
Кто первым пришёл, того первым и обслужили: очередь, круговая очередь, только недавние элементы, дек с двумя концами и разворот дека одним флагом.
Теория
Урок 3 из 7
23 мин чтения
Вопросов: 5
В пекарне кто пришёл первым, того первым и обслуживают, а каждый новый покупатель
встаёт в конец очереди. Это и есть очередь: первым пришёл — первым ушёл,
или FIFO. Она противоположна стеку: стек отдаёт самый новый элемент, а очередь —
самый старый.
queue: push в конец, pop из начала
Операция
Что делает
q.push(x)
x встаёт в конец
q.front()
элемент в начале — тот, что уйдёт следующим
q.back()
элемент в конце — тот, что пришёл последним
q.pop()
убирает элемент из начала и ничего не возвращает
q.empty(), q.size()
как у стека
У очереди видны только два конца: q[i] нет. Как и у стека, pop() ничего не
возвращает, а front() или pop() у пустой очереди — ошибка.
Вот очередь в пекарне в виде задачи:
В первой строке — n, дальше идут n команд. come name: покупатель встаёт
в конец очереди. serve: покупателя из начала очереди обслуживают, и он
уходит — выведите name is served; если никто не ждёт, ничего не происходит.
В конце выведите, сколько покупателей ещё ждут.
Ввод
дальше
Практика: Очередь и Дек
Четыре задачи: обычная очередь, круговая очередь, окно из последних чисел и дек, который всё время разворачивают.
Для 7 команд come Ali, come Zara, come Timur, serve, come Nodira,
serve, serve программа печатает:
Нодира пришла после Тимура, поэтому она всё ещё в очереди.
По очереди: круговая очередь
Очередь — это ещё и способ честно что-то поделить. Компьютер с одним процессором
и многими программами даёт каждой программе короткий ход — не больше q
единиц времени; программа, которая не успела закончить, уходит в конец
очереди и ждёт следующего хода. Это называется круговой очередью (round
robin).
Каждая задача — пара: её номер и сколько работы осталось. Пройдите по шагам три
задачи при q = 2:
Круговая очередь: первая задача работает q единиц и уходит в конец
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 queue<pair<int, int>> jobs;
9 jobs.push({1, 4});
10 jobs.push({2, 1});
11 jobs.push({3, 2});
12 int q = 2, t = 0;
13 while (!jobs.empty()) {
14 pair<int, int> j = jobs.front();
15 jobs.pop();
16 int run = min(q, j.second);
17 t += run;
18 j.second -= run;
19 if (j.second > 0) {
20 jobs.push(j);
21 } else {
22 cout << j.first << " " << t << "\n";
23 }
24 }
25 return 0;
26}
Пустая очередь
строка 8
Каждая задача — пара {номер задачи, сколько работы осталось}. На панели начало очереди слева.
jobs (начало → конец)0 ячеек
j (задача, осталось)2 ячеек
—
—
0
1
q—t—run—
нажми пуск
1 / 38
Целиком задача такая:
В очереди стоят задачи с номерами от 1 до n, и задаче i нужно p_i
единиц работы. Ход длится не больше q единиц. В первой строке — n и q,
во второй — числа p_i. Каждый раз, когда задача заканчивается, выведите её
номер и время, когда она закончилась.
Ввод
Вывод
Для 3 3 и объёмов работы 5 2 7 программа печатает 2 5, 1 10 и 3 14:
задача 2 заканчивается в момент 5, задача 1 — в 10, а задача 3 — в 14. Часы —
это long long: если задач 200 000 и каждой нужно до 10⁹ единиц, общее время
намного превышает то, что помещается в int.
Запустите кухню с одним поваром и посмотрите, как от длины хода зависит, кто
поест первым:
Кухня с круговой очередьюпопробуй!
Только недавние
Иногда важны только последние пришедшие:
На сервер приходят n запросов, их секунды даны по возрастанию. После каждого
запроса выведите, сколько запросов пришло за последние 10 секунд, включая этот:
для запроса в секунду t всё, что пришло в секунду t − 10 или раньше, уже
слишком старое.
Ввод
Вывод
Последние 10 секунд — это окно, которое со временем сдвигается вперёд.
Храните запросы из окна в очереди. Запросы приходят по возрастанию времени,
поэтому старые всегда стоят в начале — убирайте их, пока в начале не
окажется недавний:
Для запросов в секунды 1 3 8 11 12 25 программа печатает 1 2 3 3 4 1. В
секунду 11 уходит запрос из секунды 1, в секунду 25 — все остальные. Каждый
элемент кладётся один раз и убирается не больше одного раза, поэтому вся работа
занимает около 2n шагов, каким бы широким ни было окно.
Первое отрицательное в каждом окне
Окном может быть и отрезок из соседних чисел списка:
Даны n чисел и k. Для каждого окна из k соседних чисел — позиции с 1 по
k, потом со 2 по k + 1 и так далее — найдите первое отрицательное число в
нём или 0, если его нет.
Ввод
Вывод
В очереди не обязательно держать всё — только то, о чём вы будете спрашивать.
Кладите в очередь только позиции отрицательных чисел: по позиции, в отличие
от значения, видно, выехало ли число из окна. Перед ответом для окна, которое
кончается на позиции i, уберите позиции меньше i − k + 1: они выехали из
окна. Теперь в начале стоит самое старое отрицательное число, ещё оставшееся
внутри, — то есть первое в окне, а пустая очередь означает, что отрицательных в
окне нет.
Для 4 -2 5 -7 3 и k = 3 в очередь попадают позиции 2 и 4. У окон 4 -2 5 и
-2 5 -7 в начале очереди позиция 2: ответ -2. Для 5 -7 3 позиция 2 уже
выехала из окна и убирается, и ответ — -7.
Дек: оба конца
Дек (deque, от double-ended queue — «очередь с двумя концами») умеет
добавлять и убирать с обоих концов, а ещё обращаться к любому элементу по
индексу:
Операция
Что делает
d.push_front(x), d.push_back(x)
добавляет x в начало или в конец
d.pop_front(), d.pop_back()
убирает первый элемент или последний
d.front(), d.back()
читает оба конца
d[i], d.size(), d.empty()
как у вектора
Каждая из этих операций занимает один шаг. vector так в начале не умеет:
вставка в его начало сдвигает все элементы.
Дек может работать стеком (один конец) или очередью (кладём в конец, берём из
начала), но по-настоящему он нужен, когда важны оба конца: карты, которые могут
встать на любой край ряда, или ряд, из которого берут то слева, то справа.
Карты на оба краяпопробуй!
Разворот бесплатно
Некоторые задачи то и дело говорят «разверните весь ряд». Вот одна из них:
Ряд чисел сначала пуст, дальше идут до 200 000 команд. left x ставит x на
левый край ряда, right x — на правый, а flip разворачивает весь ряд.
Выведите ряд в конце.
Ввод
Вывод
Ряд — это дек. Но reverse(d.begin(), d.end()) проходит по всем элементам,
поэтому 200 000 разворотов дека из 200 000 элементов — это 4·10¹⁰ шагов, слишком
медленно.
Не разворачивайте дек — запомните, что он развёрнут. Заведите флаг rev.
Пока он false, «слева» означает начало, а «справа» — конец. Пока он true, ряд
читается с конца, поэтому стороны меняются местами: «добавить слева» становится
push_back, «убрать справа» — pop_front, «посмотреть на левый край» — back().
Разворот стоит одного шага, rev = !rev, а по-настоящему дек переворачивается
не больше одного раза — при печати:
Для right 1, right 2, left 3, flip, left 4, right 5 программа
печатает 4 2 1 3 5.
Проверьте себя
Один ход круговой очереди
Возьмите задачу из начала очереди и вызовите pop.
Дайте ей поработать min(q, сколько осталось) единиц и передвиньте часы на столько же.
Если работа ещё осталась, верните задачу в конец через push. Иначе она закончена: запишите время.
А вы знали?
Ваш компьютер прямо сейчас работает по круговой очереди. Открытых программ у него
гораздо больше, чем ядер процессора, поэтому операционная система даёт каждой
квант времени в несколько миллисекунд и переходит к следующей. Переключение
настолько быстрое, что кажется, будто всё работает одновременно.
queue<int> q; // пустая очередь целых чисел
проверь себя1 балл
С пустой queue<int> q выполняют push(4), push(9), pop(), push(1), push(6), pop(). Чему теперь равно q.front()?
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
Круговая очередь с ходами не длиннее q = 3 единиц: задаче 1 нужно 5 единиц, задаче 2 — 2, часы начинают с 0. В какой момент закончит задача 1?
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
В поликлинике пациентов принимают в том порядке, в котором они пришли. В каком контейнере держать ожидающих?
Выберите один ответ
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
Что лежит в d от начала к концу?
Выберите один ответ
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
Дек хранит 1 2 3 от начала к концу, а флаг rev равен true, так что ряд читается как 3 2 1. Какой вызов поставит 0 на левый край ряда?
Выберите один ответ
Войдите, чтобы ответить и сохранить прогресс.Войти
7
come Ali
come Zara
come Timur
serve
come Nodira
serve
serve
Ali is served
Zara is served
Timur is served
1 still waiting
Ali is served
Zara is served
Timur is served
1 still waiting
3 3
5 2 7
2 5
1 10
3 14
6
1 3 8 11 12 25
1 2 3 3 4 1
7 3
4 -2 5 -7 3 8 9
-2 -2 -7 -7 0
6
right 1
right 2
left 3
flip
left 4
right 5
4 2 1 3 5
#include <bits/stdc++.h>using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; queue<string> line; for(int i = 0; i < n; i++){ string cmd; cin >> cmd; if(cmd == "come"){ string name; cin >> name; line.push(name); // встаёт в конец} else if(!line.empty()){ cout << line.front()<< " is served\n"; line.pop(); // уходит из начала}} cout << line.size()<< " still waiting\n"; return 0;}
#include <bits/stdc++.h>using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n; long long q; cin >> n >> q; queue<pair<int, long long>> jobs; // (номер задачи, сколько работы осталось) for(int i = 1; i <= n; i++){ long long p; cin >> p; jobs.push({i, p});} long long t = 0; // часы while(!jobs.empty()){ pair<int, long long> j = jobs.front(); jobs.pop(); long long run = min(q, j.second); // в этот ход не больше q единиц t += run; j.second -= run; if(j.second> 0){ jobs.push(j); // не готово: в конец очереди} else{ cout << j.first<< " "<< t << "\n";}} return 0;}
#include <bits/stdc++.h>using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; queue<int> recent; // запросы за последние 10 секунд, самый старый первым for(int i = 0; i < n; i++){ int t; cin >> t; recent.push(t); while(recent.front()<= t - 10){ recent.pop(); // слишком старый: он вышел из окна} cout << recent.size()<< " ";} cout << "\n"; return 0;}