Queues and Deques - Забони барномасозии C++ барои барномасозии рақобатӣ
Week 10Stacks, Queues, Deques and Simulation Problems
Queues and Deques
First come, first served: the queue, taking turns with round robin, keeping only the recent arrivals, the deque with both ends, and reversing a deque with one flag.
Назария
Дарси 3 аз 7
Хониш: 24 дақиқа
Саволҳо: 5
At a bakery, whoever came first is served first, and everyone who arrives joins
the end of the line. That is a queue: first in, first out, or FIFO.
It is the stack's opposite. A stack hands back the newest element; a queue
hands back the oldest.
queue: push at the back, pop at the front
Operation
What it does
q.push(x)
x joins at the back
q.front()
the element at the front — the next to leave
q.back()
the element at the back — the last to arrive
q.pop()
removes the front element and gives back nothing
q.empty(), q.size()
as for a stack
A queue shows only its two ends: there is no q[i]. As with a stack, pop()
returns nothing, and front() or pop() on an empty queue is a bug.
Here is the bakery line as a problem:
The first line holds n, then come n commands. come name: a customer
joins the end of the line. serve: the customer at the front is served and
leaves — print name is served; if nobody is waiting, nothing happens. At
the end, print how many customers are still waiting.
навбатӣ
Practice: Queues and Deques
Four problems: a plain queue, round robin, a window of recent numbers and a deque that keeps being reversed.
For the 7 commands come Ali, come Zara, come Timur, serve,
come Nodira, serve, serve, it prints:
Nodira arrived after Timur, so she is still in line.
Taking turns: round robin
A queue is also how to share something fairly. A computer with one processor
and many programs gives each program a short turn of at most q units of
time; a program that hasn't finished goes to the back of the queue and
waits for its next turn. This is called round robin.
Each job is a pair: its number and its work left. Step through three jobs with
q = 2:
Round robin: the front job works for q units, then goes to the back
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}
An empty queue
сатр 8
Each job is a pair {job number, work left}. The panel shows the front of the queue on the left.
jobs (front → back)0 катак
j (job, work left)2 катак
—
—
0
1
q—t—run—
пахш кун
1 / 38
As a full problem:
Jobs numbered 1 to n stand in a queue, and job i needs p_i units of
work. A turn lasts at most q units. The first line holds n and q, the
second the p_i. Each time a job finishes, print its number and the time it
finished.
Input
Output
For 3 3 and the work 5 2 7, it prints 2 5, 1 10 and 3 14: job 2
finishes at time 5, job 1 at 10, and job 3 at 14. The clock is
a long long: with 200 000 jobs of up to 10⁹ units each, the total time goes
far past what an int holds.
Run a kitchen with one cook, and see how the length of a turn changes who eats
first:
The round-robin kitchenсанҷида бин!
Only the recent ones
Sometimes only the latest arrivals matter:
A server gets n requests, at seconds given in increasing order. After each
request, print how many requests arrived in the last 10 seconds, this one
included: for a request at second t, everything from second t − 10 or
earlier is too old.
Input
Output
The last 10 seconds are a window that slides forward as time goes on. Keep
the requests inside it in a queue. Requests arrive in order of time, so the old
ones are always at the front — pop them until the front is recent again:
For requests at seconds 1 3 8 11 12 25, it prints 1 2 3 3 4 1. At second 11
the request from second 1 leaves; at second 25, all the others do. Every element
is pushed once and popped at most once, so the whole run takes about 2n steps,
however wide the window is.
The first negative in every window
A window can also be a run of neighbouring numbers in a list:
You are given n numbers and k. For every window of k neighbouring
numbers — positions 1 to k, then 2 to k + 1, and so on — find the first
negative number in it, or 0 if it has none.
Input
Output
The queue doesn't have to hold everything — only the elements you will ask
about. Push only the positions of the negative numbers: a position, unlike a
value, tells you whether it has slid out of the window. Before answering for the
window that ends at position i, pop the positions smaller than i − k + 1:
they have slid out of it. Now the front is the oldest negative still inside,
which is the first one in the window — and an empty queue means the window has
none.
For 4 -2 5 -7 3 and k = 3, the queue gets positions 2 and 4. The windows
4 -2 5 and -2 5 -7 both start with position 2 at the front: -2. For
5 -7 3, position 2 has slid out and is popped, and the answer is -7.
The deque: both ends
A deque (say "deck": it is short for double-ended queue) can add and remove
at both ends, and reach any element by its index:
Operation
What it does
d.push_front(x), d.push_back(x)
adds x at the front, or at the back
d.pop_front(), d.pop_back()
removes the front element, or the back one
d.front(), d.back()
reads the two ends
d[i], d.size(), d.empty()
as for a vector
Each of these takes one step. A vector can't do that at the front: inserting
at its beginning shifts every element along.
A deque can be a stack (use one end) or a queue (push at the back, pop at the
front), but it earns its place when both ends matter: cards that may go to
either end of a row, or a row you take from on the left or on the right.
Cards to both endsсанҷида бин!
Reversing for free
Some problems keep saying "reverse the whole row". Here is one:
A row of numbers starts empty, and up to 200 000 commands follow. left x
puts x at the left end of the row, right x puts it at the right end, and
flip reverses the whole row. Print the row at the end.
Input
Output
The row is a deque. But reverse(d.begin(), d.end()) walks through every
element, so 200 000 reverses of a 200 000-element deque take 4·10¹⁰ steps — far
too slow.
Don't reverse it: remember that it is reversed. Keep a flag rev. While it
is false, left means the front and right means the back. While it is true,
the row is read from the back, so the two sides swap: "add on the left" becomes
push_back, "remove from the right" becomes pop_front, and "look at the left
end" becomes back(). A flip costs one step, rev = !rev, and the deque is
turned round for real at most once — when it is printed:
Four commands: put 1 on the right, put 2 on the left, flip the row, put 3 on the left.
cmd4 катак
"right"
"left"
"flip"
"left"
0
1
2
3
val4 катак
—
—
—
—
0
1
2
3
d (front → back)0 катак
rev—i—toLeft—x—
пахш кун
1 / 37
For right 1, right 2, left 3, flip, left 4, right 5, it prints
4 2 1 3 5.
Check your understanding
One turn of round robin
Take the job at the front, and pop it.
Let it work for min(q, work left) units, and move the clock on by as much.
If it still has work left, push it to the back. Otherwise it has finished: record the time.
Did you know?
Your computer is running round robin right now. It has far more programs open
than processor cores, so the operating system gives each one a time slice of a
few milliseconds and then moves on to the next. The switching is so fast that
everything seems to run at once.
queue<int> q; // an empty queue of ints
худро санҷ1 хол
An empty queue<int> q gets push(4), push(9), pop(), push(1), push(6), pop(). What is q.front() now?
Барои ҷавоб додан ва нигоҳ доштани пешрафт ворид шавед.Ворид шудан
худро санҷ1 хол
Round robin with turns of at most q = 3 units: job 1 needs 5 units, job 2 needs 2, and the clock starts at 0. At what time does job 1 finish?
Барои ҷавоб додан ва нигоҳ доштани пешрафт ворид шавед.Ворид шудан
худро санҷ1 хол
Patients at a clinic are seen in the order they arrived. Which container keeps the waiting patients?
Як ҷавобро интихоб кунед
Барои ҷавоб додан ва нигоҳ доштани пешрафт ворид шавед.Ворид шудан
худро санҷ1 хол
What does d hold, from front to back?
Як ҷавобро интихоб кунед
Барои ҷавоб додан ва нигоҳ доштани пешрафт ворид шавед.Ворид шудан
худро санҷ1 хол
A deque holds 1 2 3 from front to back, and the flag rev is true, so the row reads 3 2 1. Which call puts 0 at the row's left end?
Як ҷавобро интихоб кунед
Барои ҷавоб додан ва нигоҳ доштани пешрафт ворид шавед.Ворид шудан
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); // joins at the back} else if(!line.empty()){ cout << line.front()<< " is served\n"; line.pop(); // leaves from the front}} 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; // (job number, work left) for(int i = 1; i <= n; i++){ long long p; cin >> p; jobs.push({i, p});} long long t = 0; // the clock while(!jobs.empty()){ pair<int, long long> j = jobs.front(); jobs.pop(); long long run = min(q, j.second); // at most q units this turn t += run; j.second -= run; if(j.second> 0){ jobs.push(j); // not finished: back of the line} 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; // requests of the last 10 seconds, oldest first for(int i = 0; i < n; i++){ int t; cin >> t; recent.push(t); while(recent.front()<= t - 10){ recent.pop(); // too old: it has left the window} cout << recent.size()<< " ";} cout << "\n"; return 0;}