Очередь (Queue) — это линейная структура данных, реализующая принцип FIFO (First-In, First-Out): первый добавленный элемент будет первым удален.
Основные операции:
- enqueue (помещение в очередь): добавление элемента в конец очереди.
- dequeue (извлечение из очереди): удаление элемента из начала очереди.
- peek (или front): получение значения элемента в начале очереди без его удаления.
- is_empty: проверка, пуста ли очередь.
- size: получение текущего количества элементов в очереди.
Реализации:
- Список (List): Неэффективно для больших очередей из-за O(n) при удалении с начала (смещении элементов).
python
- collections.deque: Двусвязный список, оптимизированный для быстрого добавления/удаления с обоих концов. O(1) для enqueue и dequeue.
python
- queue.Queue: Потокобезопасная реализация для многопоточных приложений. Использует
collections.deque внутри. Методы put() и get() потокобезопасны.
python
Применение:
- Обработка запросов сервером.
- Буферизация данных.
- Реализация алгоритмов (например, поиск в ширину - BFS).
- Потокобезопасное взаимодействие между потоками (с помощью
queue.Queue).