Hva er en queue og hvor brukes den?

Question

Accepted Answer

En **queue** er en **FIFO** (First-In, First-Out) samling: elementer legges til på **baksiden** og fjernes fra **forsiden**, som en kø med mennesker. ## Operations ```text enqueue(1) enqueue(2) enqueue(3) dequeue()->1 front ->[1][2][3]<- back front ->[2][3]<- back ``` ## Example ```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` gjør `pop(0)` til en **O(n)** operasjon, så bruk `deque` for **O(1)** på begge ender. | Operation | Time (deque) | |---|---| | enqueue | O(1) | | dequeue | O(1) | | peek front | O(1) | ## Common uses - **Task / job scheduling** — behandle arbeid i ankomstrekkefølge. - **Breadth-first search (BFS)** — besøk noder nivå for nivå. - **Buffering** — producer/consumer pipelines, print spoolers, request queues. ## Hvorfor det er viktig Queues oppfører rettferdighet og rekkefølge, noe som er kritisk for schedulers, messaging-systemer og BFS. Når arbeid må håndteres "i den rekkefølgen det ankom," er en queue det naturlige valget.