Алгоритмы на Python

Структура данных очередь (queue) в Python

В этом уроке вы реализуете эффективную очередь по правилу «первым пришёл, первым ушёл» с помощью collections.deque.

  • Средний
  • Чтение: 2 мин
  • Примеров для запуска: 1

Введение

Какую задачу это решает

Задания на печать, обращения в поддержку и сообщения между программами нужно обрабатывать в порядке поступления. Очередь сохраняет этот порядок, а правильный инструмент для неё в Python остаётся быстрым даже с миллионами элементов.

Пример из жизни

Очередь похожа на очередь у билетной кассы. Новые люди встают в конец, а первым обслуживают того, кто впереди. Никто не лезет вперёд, поэтому всех обслуживают в порядке прихода.

От очереди в кассу к коду
deque(["first", "second"])🚶🚶 Двое уже ждут
queue.append("third")🚶 Новый человек встаёт в конец
queue.popleft()🎫 Обслуживают того, кто впереди
list(queue)👀 Кто ещё ждёт
Первым пришёл, первым ушёл: порядок прихода - это порядок обслуживания.
Одним предложением

Очередь - коллекция «первым пришёл, первым ушёл» (FIFO): элементы добавляются в конец и удаляются из начала.

Главное

  1. deque(["first", "second"]) создаёт очередь, в которой уже два элемента.
  2. queue.append("third") добавляет элемент в конец.
  3. queue.popleft() удаляет и возвращает элемент из начала, здесь "first".
  4. deque быстро удаляет из начала; список пришлось бы сдвигать целиком.

Когда это нужно?

  • Обработка задач или запросов в порядке поступления.
  • Поиск в ширину в графах и сетках.
  • Буферы между производителями и потребителями, например сообщений или событий.

Когда это не нужно

  • Первым должен выходить самый свежий элемент: используйте стек.
  • У элементов есть приоритеты: используйте heapq для очереди с приоритетом.
  • Очередь делят несколько потоков: queue.Queue сам управляет блокировками.

Как это работает

Делайте enqueue и dequeue и убедитесь, что элементы выходят в том же порядке, в каком пришли.

Пример кода

Запустить код →
main.py
from collections import deque

queue = deque(["first", "second"])
queue.append("third")

print("served:", queue.popleft())
print("waiting:", list(queue))
Получить кнопку запуска для этого примера

Результат выполнения

served: first
waiting: ['second', 'third']

Разбор кода

deque позволяет добавлять элементы справа через append() и забирать слева через popleft(), обе операции за O(1). В обычном списке удаление первого элемента стоит O(n), потому что все следующие элементы приходится сдвигать, поэтому для очереди подходит именно deque.

Измените значения и запустите программу в онлайн-компиляторе Python CodeUtility без локальной установки Python.

Упражнения для практики

Попробуйте изменить код по подсказкам ниже. Если менять код и смотреть на результат, урок запомнится гораздо лучше, чем при простом чтении.

  1. Проверьте работу на пустом списке, списке из одного элемента и списке с повторами.
  2. Выводите состояние после каждого шага, чтобы увидеть алгоритм в действии.
  3. Измерьте время работы на 100, 1 000 и 10 000 элементах и сравните с другим решением.
Запустить в компиляторе Python →

Частые ошибки

Список и pop(0)

pop(0) сдвигает каждый оставшийся элемент, и длинные очереди становятся медленными.

Ошибка
queue = ["first", "second"]
queue.pop(0)
Исправление
queue = deque(["first", "second"])
queue.popleft()

Закончили этот урок?

Отметьте его как изученный, чтобы следить за прогрессом.

Попрактикуйтесь на задаче

Примените материал этого урока к реальной задаче. Каждая задача запускается в браузере, с мгновенными тестами и разбором от ИИ.

Все задачи