Что такое очередь и где она используется?

Question

Accepted Answer

**Очередь** — это коллекция **FIFO** (First-In, First-Out): элементы добавляются в **конец** и удаляются из **начала**, как очередь людей. ## 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' ``` Обычный Python `list` делает `pop(0)` операцией **O(n)**, поэтому используйте `deque` для **O(1)** на обоих концах. | Operation | Time (deque) | |---|---| | enqueue | O(1) | | dequeue | O(1) | | peek front | O(1) | ## Common uses - **Task / job scheduling** — обработка работ в порядке поступления. - **Breadth-first search (BFS)** — посещение узлов уровень за уровнем. - **Buffering** — producer/consumer pipelines, print spoolers, request queues. ## Почему это важно Очереди обеспечивают справедливость и упорядоченность, что критично для планировщиков, систем обмена сообщениями и BFS. Когда работа должна быть обработана "в порядке её поступления," очередь — естественный выбор.