Структура данных очередь (queue) в Python
В этом уроке вы реализуете эффективную очередь по правилу «первым пришёл, первым ушёл» с помощью collections.deque.
Введение
Какую задачу это решает
Задания на печать, обращения в поддержку и сообщения между программами нужно обрабатывать в порядке поступления. Очередь сохраняет этот порядок, а правильный инструмент для неё в Python остаётся быстрым даже с миллионами элементов.
Пример из жизни
Очередь похожа на очередь у билетной кассы. Новые люди встают в конец, а первым обслуживают того, кто впереди. Никто не лезет вперёд, поэтому всех обслуживают в порядке прихода.
deque(["first", "second"])🚶🚶 Двое уже ждутqueue.append("third")🚶 Новый человек встаёт в конецqueue.popleft()🎫 Обслуживают того, кто впередиlist(queue)👀 Кто ещё ждётОчередь - коллекция «первым пришёл, первым ушёл» (FIFO): элементы добавляются в конец и удаляются из начала.
Главное
deque(["first", "second"])создаёт очередь, в которой уже два элемента.queue.append("third")добавляет элемент в конец.queue.popleft()удаляет и возвращает элемент из начала, здесь"first".dequeбыстро удаляет из начала; список пришлось бы сдвигать целиком.
Когда это нужно?
- Обработка задач или запросов в порядке поступления.
- Поиск в ширину в графах и сетках.
- Буферы между производителями и потребителями, например сообщений или событий.
Когда это не нужно
- Первым должен выходить самый свежий элемент: используйте стек.
- У элементов есть приоритеты: используйте
heapqдля очереди с приоритетом. - Очередь делят несколько потоков:
queue.Queueсам управляет блокировками.
Как это работает
Делайте enqueue и dequeue и убедитесь, что элементы выходят в том же порядке, в каком пришли.
Пример кода
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.
Упражнения для практики
Попробуйте изменить код по подсказкам ниже. Если менять код и смотреть на результат, урок запомнится гораздо лучше, чем при простом чтении.
- Проверьте работу на пустом списке, списке из одного элемента и списке с повторами.
- Выводите состояние после каждого шага, чтобы увидеть алгоритм в действии.
- Измерьте время работы на 100, 1 000 и 10 000 элементах и сравните с другим решением.
Частые ошибки
Список и pop(0)
pop(0) сдвигает каждый оставшийся элемент, и длинные очереди становятся медленными.
queue = ["first", "second"]
queue.pop(0)
queue = deque(["first", "second"])
queue.popleft()
Закончили этот урок?
Отметьте его как изученный, чтобы следить за прогрессом.
Попрактикуйтесь на задаче
Примените материал этого урока к реальной задаче. Каждая задача запускается в браузере, с мгновенными тестами и разбором от ИИ.
- Course Schedule Order Order courses so every prerequisite comes first. Сложно
- Can We Split Into Two Teams? Decide whether people can be assigned to two teams so that each listed pair is on opposite teams. Средне