Түрүүлж ирсэн нь түрүүлж гардаг Queue бүтэц. Дэлгүүрийн дараалал шиг ажиллана.

Pre-IntermediateХугацаа: O(n)Санах ой: O(n)
HackerRank дээр бодох

Эхлээд жижиг бодлого

Командууд: push 4, push 7, pop, pop, pop. Эхлээд 4, дараа нь 7 дугаартай хүүхэд ирж зогсоно.

Эхний pop 4-ийг, хоёр дахь нь 7-г хэвлэнэ. Гурав дахь pop ирэхэд Queue хоосон тул "empty" гэж хэвлэнэ. Эцэст нь Queue-гийн хэмжээ 0. Гаралт: 4, 7, empty, 0.

Энгийн аргаас санаа руу

Queue-г энгийн array ашиглан хийж болно: шинэ хүүхдийг төгсгөлд нэмнэ. Гэхдээ урдаас нь гаргах бүрт бүх хүүхдийг нэг байр урагшлуулбал нэг pop O(n) болно. n = 100 000 командад тэрбум гаруй шилжүүлэлт гарч болно.

Гол санаа: хэнийг ч хөдөлгөх хэрэггүй. Хамгийн урд хэн байгааг, хамгийн ард хаана нэмэхийг л санахад хангалттай. C++-ийн queue<int> үүнийг хийж өгдөг тул push, front, pop бүгд O(1).

Нэр томьёо ба тэмдэглэгээ

Queue
Түрүүлж орсон нь түрүүлж гардаг бүтэц (FIFO). C++-д queue<int> q;.
q.push(x)
x-ийг Queue-гийн ард нэмнэ.
q.front()
Хамгийн урд байгаа элементийг харна. Queue-гээс гаргахгүй.
q.pop()
Хамгийн урд байгаа элементийг гаргана. Утгыг нь буцаадаггүй.
q.empty(), q.size()
Хоосон эсэх ба хэдэн элемент байгааг хэлнэ.
q
n = 7

Зайрмагны машины өмнө хүүхдүүд дараалж зогсоно. Хүүхэд бүр өөрийн дугаартай. Түрүүлж ирсэн нь түрүүлж зайрмагаа авна. Ийм дарааллыг Queue гэдэг.

Алхам 1 / 12
Хурд
  • Сая ирсэн
  • Зайрмагаа авч буй
  • Хоосон Queue
Слайд 1 / 7

Зайрмагны дараалал

Зайрмагны машины өмнө хүүхдүүд дараалж зогсож байна. Түрүүлж ирсэн нь түрүүлж авна. Queue яг ингэж ажилладаг.

queue-basics.cpp
#include <bits/stdc++.h>
using namespace std;
int n;
queue<int> q;
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
string op;
cin >> op;
if (op == "push") {
int x;
cin >> x;
q.push(x);
} else if (q.empty()) {
cout << "empty\n";
} else {
cout << q.front() << '\n';
q.pop();
}
}
cout << q.size() << '\n';
return 0;
}

Юунд хэрэгтэй вэ?

Queue-тэй ажиллаж сурна: ард нь нэмэх (push), урд байгааг харах (front), урдаас нь гаргах (pop). BFS зэрэг олон алгоритм Queue ашигладаг.

Яаж ажилладаг вэ?

1. Эхний мөрөнд командын тоо n. 2. "push x": x дугаартай хүүхэд Queue-гийн ард зогсоно: q.push(x). 3. "pop": хамгийн урд байгаа хүүхдийн дугаарыг хэвлээд (q.front()), түүнийг Queue-гээс гаргана (q.pop()). 4. Queue хоосон үед pop ирвэл "empty" гэж хэвлэнэ. 5. Эцэст нь Queue-д үлдсэн хүүхдийн тоог хэвлэнэ (q.size()).

Яагаад зөв, хэр хурдан бэ?

Queue элементүүдийг ирсэн дарааллаар нь хадгалж, үргэлж хамгийн эрт ирснийг нь эхэлж гаргадаг. Тиймээс pop бүр яг тэр мөчид хамгийн удаан хүлээсэн хүүхдийн дугаарыг хэвлэнэ.

Команд бүр O(1) хугацаатай тул n команд O(n) хугацаанд дуусна. n = 1 000 000 бол сая орчим үйлдэл. Санах ой нь Queue-д нэгэн зэрэг байгаа элементийн тоотой тэнцүү.

Түгээмэл алдаа

  • q.pop() утга буцаана гэж бодох. Эхлээд q.front()-ыг хэвлээд, дараа нь q.pop() хийнэ.
  • Хоосон Queue дээр q.front() дуудах. Үргэлж q.empty()-г эхлээд шалга.
  • q.size() нь unsigned тоо буцаадаг. q.size() - 1 хоосон Queue дээр маш том тоо болно.

Хязгаарын тохиолдол

  • Бүх команд pop: хоосон тул бүгдэд "empty", эцэст нь 0.
  • Бүх команд push: юу ч хэвлэхгүй, эцэст нь n хэвлэнэ.
  • Ижил дугаар хоёр удаа push хийвэл Queue-д хоёр тусдаа элемент болж орно.

Өөрийгөө шалга

  1. push 1, push 2, push 3, pop гэсэн командын гаралт юу вэ?

    Хариу харах

    1, дараа нь 2. Эхлээд 1 хэвлэгдэнэ, эцэст нь Queue-д 2 элемент үлдэнэ.

  2. Stack ба Queue-гийн гол ялгаа юу вэ?

    Хариу харах

    Stack сүүлд орсныг, Queue эхэлж орсныг нь эхэлж гаргадаг.

Гурван дадлага

Hint-ээ нээхээс өмнө өөрөө оролдоорой.

  1. 1.push 5, push 3, pop, push 8, push 2, pop, pop командын дараа Queue-д юу үлдэх вэ?

    Hint харах

    Pop бүр урд байгааг гаргана.

    Хариу ба тайлбар

    Хэвлэгдэх нь 5, 3, 8. Queue-д зөвхөн 2 үлдэж, эцэст нь 1 хэвлэнэ.

  2. 2.queue ашиглахгүйгээр array ба хоёр index-ээр Queue хий.

    Hint харах

    head нь урд байгаагийн, tail нь дараагийн чөлөөтэй байрын index.

    Хариу ба тайлбар

    push: a[tail++] = x;. front: a[head]. pop: head++;. Хоосон эсэх: head == tail. Хэмжээ: tail - head. Array-н хэмжээг нийт push-ийн тоогоор авна.

  3. 3.n хүүхэд тойрч зогсжээ. Урд байгаа хүүхдийг ард нь шилжүүлж, хоёр дахь хүүхэд бүрийг тоглоомоос гаргана. n = 5 бол хэн үлдэх вэ?

    Hint харах

    Queue-д 1-ээс n хүртэл хий. Нэг алхамд front-ийг ард нь шилжүүлээд, дараагийн front-ийг гаргана.

    Хариу ба тайлбар

    Гарах дараалал нь 2, 4, 1, 5 тул 3 дугаартай хүүхэд үлдэнэ. Queue-д ганц элемент үлдтэл давтана. Хугацаа O(n).

Жишээ

Оролт

7
push 5
push 3
pop
push 8
push 2
pop
pop

Гаралт

5
3
8
1

Одоо өөрөө бодоод үз

Бодлого

Хичээл

Энэ сэдвийн хичээл удахгүй нэмэгдэнэ.