Vad är en kö och var används den?

Question

Accepted Answer

En **kö** är en **FIFO** (First-In, First-Out) samling: element läggs till i **slutet** och tas bort från **framsidan**, som en rad människor. ## Operationer ```text enqueue(1) enqueue(2) enqueue(3) dequeue()->1 front ->[1][2][3]<- back front ->[2][3]<- back ``` ## Exempel ```python from collections import deque queue = deque() queue.append('a') # enqueue (back) queue.append('b') first = queue.popleft() # dequeue (front) -> 'a' ``` En vanlig Python `list` gör `pop(0)` till en **O(n)** operation, så använd `deque` för **O(1)** på båda ändar. | Operation | Tid (deque) | |---|---| | enqueue | O(1) | | dequeue | O(1) | | peek front | O(1) | ## Vanliga användningar - **Schemaläggning av uppgifter / jobb** — bearbeta arbete i ankomstordning. - **Bredd-först-sökning (BFS)** — besök noder nivå för nivå. - **Buffering** — producent/konsument-pipelines, skrivarköer, förfrågningsköer. ## Varför det är viktigt Köer säkerställer rättvisa och ordning, vilket är kritiskt för schemaläggare, meddelandesystem och BFS. När arbete måste hanteras "i den ordning det anlände," är en kö det naturliga valet.