Mi az a sor (queue) és hol használják?

Question

Accepted Answer

A **sor (queue)** egy **FIFO** (First-In, First-Out) gyűjtemény: elemek a **hátulhoz** kerülnek hozzáadásra és az **elejéről** kerülnek eltávolításra, mint egy sorban álló emberek. ## Műveletek ```text enqueue(1) enqueue(2) enqueue(3) dequeue()->1 front ->[1][2][3]<- back front ->[2][3]<- back ``` ## Példa ```python from collections import deque queue = deque() queue.append('a') # enqueue (back) queue.append('b') first = queue.popleft() # dequeue (front) -> 'a' ``` Egy egyszerű Python `list` az `pop(0)` műveletet **O(n)** összetettségűvé teszi, ezért használj `deque`-t az **O(1)** összetettséghez mindkét végpontban. | Művelet | Idő (deque) | |---|---| | enqueue | O(1) | | dequeue | O(1) | | peek front | O(1) | ## Gyakori felhasználási esetek - **Feladat / munka ütemezés** — munka feldolgozása az érkezési sorrend szerint. - **Szélességi keresés (BFS)** — csomópontok szintenkénti bejárása. - **Pufferelés** — termelő/fogyasztó folyamatok, nyomtatási sorok, kérés sorok. ## Miért fontos A sorok méltányosságot és sorrendiséget érvényesítenek, amely kritikus fontosságú az ütemezőknek, üzenetküldési rendszereknek és a BFS-nek. Havalaha munka "az érkezési sorrend szerint" kell kezelni, a sor a természetes megoldás.