Kaj je vrsta čakalne vrste in kje se uporablja?

Question

Accepted Answer

**Vrsta čakalne vrste** je kolekcija **FIFO** (First-In, First-Out): elementi se dodajo na **konec** in odstranjujejo s **sprednjega dela**, kot je vrsta ljudi. ## Operacije ```text enqueue(1) enqueue(2) enqueue(3) dequeue()->1 front ->[1][2][3]<- back front ->[2][3]<- back ``` ## Primer ```python from collections import deque queue = deque() queue.append('a') # enqueue (back) queue.append('b') first = queue.popleft() # dequeue (front) -> 'a' ``` Navaden Python `list` naredi `pop(0)` operacijo **O(n)**, zato za **O(1)** na obeh koncih uporabite `deque`. | Operacija | Čas (deque) | |---|---| | enqueue | O(1) | | dequeue | O(1) | | peek front | O(1) | ## Običajne uporabe - **Razporejanje nalog / opravil** — obdelava dela v vrstnem redu prihoda. - **Breadth-first search (BFS)** — obisk vozlišč raven za ravnijo. - **Medpomnenje** — proizvod/porabnik cevovodi, tiskalni nadzor, vrste zahtevkov. ## Zakaj je to pomembno Vrste čakalne vrste zagotavljajo pravičnost in urejenost, kar je kritično za razporejevalce, sisteme sporočanja in BFS. Kadar mora biti delo obdelano "v vrstnem redu prihoda," je vrsta čakalne vrste naravna izbira.