Co to jest kolejka i gdzie jest używana?

Question

Accepted Answer

**Kolejka** to kolekcja **FIFO** (First-In, First-Out): elementy są dodawane na **końcu** i usuwane z **przodu**, jak szereg ludzi. ## 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' ``` Zwykła Python `list` powoduje, że `pop(0)` jest operacją **O(n)**, więc użyj `deque` dla **O(1)** na obu końcach. | Operation | Time (deque) | |---|---| | enqueue | O(1) | | dequeue | O(1) | | peek front | O(1) | ## Common uses - **Task / job scheduling** — przetwarzaj pracę w kolejności przybycia. - **Breadth-first search (BFS)** — odwiedzaj węzły poziom po poziomie. - **Buffering** — producer/consumer pipelines, print spoolers, request queues. ## Dlaczego to ważne Kolejki wymuszają uczciwość i porządek, co jest krytyczne dla harmonogramów, systemów przesyłania wiadomości i BFS. Gdy praca musi być obsługiwana "w kolejności, w której przybyła," kolejka jest naturalnym wyborem.