Навбатҳо

Навбатҳо

push, front, back, pop ва empty-ро дар навбат истифода баред, бифаҳмед, ки чаро ҷузъи қадимтарин аввал хизмат мекунад, нубатҳоро бо навбати даврӣ тақсим кунед ва тирезаи лағжандаро нигоҳ доред.

Назария

Дарси 4 аз 5

Хониш: 18 дақиқа

Саволҳо: 5

Навбат дар нонвойхона

Навбат баръакси стек кор мекунад. Ҳар касе ки меояд, ба охири навбат меистад ва аввалӣ хизмат карда мешавад. Аввалин омад, аввалин рафт, ба забони англисӣ FIFO. Стек ҷузъи навтаринро медиҳад. Навбат ҷузъи қадимтаринро медиҳад.

q.push(x) x-ро ба охир мегузорад.
q.front() ҷузъи аввал аст, ки навбатӣ мебарояд.
q.back() ҷузъи охир аст, ки охир омад.
q.pop() ҷузъи аввалро мебардорад ва ҳеҷ чиз намегардонад.
q.empty() ва q.size() мисли стек кор мекунанд.

Навбат танҳо ду канорашро нишон медиҳад: q[i] нест. Мисли стек, front() ё pop() барои навбати холӣ хато аст.

n фармон дода мешавад. come name: муштарӣ ба навбат меистад. serve: муштарии аввал меравад ва барнома name is served чоп мекунад (агар касе интизор набошад, ҳеҷ чиз намешавад). Дар охир чоп кунед, ки чанд муштарӣ ҳанӯз интизоранд.

Барои come Ali, come Zara, serve, come Timur он Ali is served ва 2 waiting чоп мекунад.

Навбат ба навбат: round robin

Навбат манбаъро низ одилона тақсим мекунад. Компютери дорои як протсессор бисёр барномаҳоро иҷро мекунад. Ҳар барнома як нӯбати кӯтоҳ мегирад, на зиёда аз q воҳиди вақт. Барномае, ки тамом нашудааст, ба охири навбат меравад. Ин навбати даврӣ (round robin) номида мешавад.

Як нӯбат: аввалин корро аз навбат pop кунед, бигзор он min(q, work left) воҳид кор кунад ва соатро пеш баред. Агар кор монда бошад, онро ба охир push кунед. Вагарна он тамом шуд: вақтро нависед.

Ҳар кор як ҷуфт аст: рақами он ва кори мондааш. Се корро бо q = 2 қадам ба қадам бубинед:

Навбати даврӣ: кори аввал q воҳид кор мекунад, баъд ба охир меравад

C++

1#include <bits/stdc++.h>

2using namespace std;

4int main() {

5 ios_base::sync_with_stdio(false);

6 cin.tie(NULL);

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 << " "

23 << t << "\n";

24 }

25 }

26 return 0;

27}

Навбати холӣ

сатр 8

Ҳар кор як ҷуфти {рақами кор, кори монда} аст. Панел аввали навбатро аз тарафи чап нишон медиҳад.

корҳо (аввал → охир)0 катак

j (кор, кори монда)2 катак

—

q—t—run—

1 / 38

Навбат дар нонвойхона

Навбат ба навбат: round robin

Машқ: навбатҳо

Танҳо наверо нигоҳ доштан

Аввалин манфӣ дар ҳар тиреза

Худатон иҷро кунед

Худро санҷед

Вазифаи хонагӣ

Хулоса