Очередь в Python: реализация и пример

TL;DR

Очередь — линейная структура данных с принципом «первым пришёл — первым вышел» (FIFO). В Python её можно реализовать простым списком (list), но для производительности и многопоточности часто используют collections.deque или queue.Queue. Ниже — пошаговая реализация на list, пояснения, сравнение альтернатив и проверочные сценарии.

Очередь — универсальная структура данных, применимая в планировщиках CPU, обработке задач веб-приложений и многих других системах. Если вы изучаете Python, знание очереди — базовое требование.

Что такое очередь?

Очередь — это линейная структура данных, работающая по принципу FIFO (First-In-First-Out). Элемент, добавленный первым, будет удалён первым.

Базовые операции:

• enqueue — добавить элемент в хвост очереди;
• dequeue — удалить и вернуть элемент из головы очереди;
• print — вывести содержимое очереди;
• front — показать элемент в начале очереди;
• rear — показать элемент в конце очереди.

В Python очередь можно реализовать разными способами. Здесь сначала показан простой вариант на списке (list), затем — альтернативы и рекомендации.

Простой пример: очередь на списке

Ниже — минимальная реализация, локализованная для русскоязычного ввода. Код демонстрирует основные команды: enqueue, dequeue, print, front, rear. Программа работает в цикле до тех пор, пока пользователь не введёт команду, отличную от поддерживаемых.

queue = []

while True:
    command = input("Что вы хотите сделать?\n")

    if command == "enqueue":
        value = int(input("Введите элемент для добавления: "))
        queue.append(value)
    elif command == "dequeue":
        if queue:
            queue.pop(0)
        else:
            print("Очередь пуста")
    elif command == "print":
        print(queue)
    elif command == "front":
        if queue:
            print(queue[0])
        else:
            print("Очередь пуста")
    elif command == "rear":
        if queue:
            print(queue[len(queue) - 1])
        else:
            print("Очередь пуста")
    else:
        break

print(queue)

Важно: в этой версии при вводе неверного значения для int программа выбросит исключение. В разделе “Улучшенная реализация” ниже показан более устойчивый вариант.

Почему использование list.pop(0) — не всегда хорошая идея

• append() на конце списка выполняется за амортизированное O(1).
• pop(0) вынуждает сдвинуть все элементы влево, что даёт O(n) на операцию удаления из головы.

Это значит, что при большом количестве операций dequeue производительность упадёт.

Факт-бокс: ключевые сложности

• Enqueue (list.append): O(1) амортизированное
• Dequeue (list.pop(0)): O(n)
• Enqueue/Dequeue (collections.deque): O(1)

Альтернативные реализации и когда их использовать

1. collections.deque — замена списку для очередей. Поддерживает append и popleft за O(1). Рекомендуется для большинства случаев, когда нужна быстрая очередь.

Пример с deque:

from collections import deque

queue = deque()

while True:
    command = input("Что вы хотите сделать?\n")
    if command == "enqueue":
        value = int(input("Введите элемент для добавления: "))
        queue.append(value)
    elif command == "dequeue":
        if queue:
            queue.popleft()
        else:
            print("Очередь пуста")
    elif command == "print":
        print(list(queue))
    elif command == "front":
        if queue:
            print(queue[0])
        else:
            print("Очередь пуста")
    elif command == "rear":
        if queue:
            print(queue[-1])
        else:
            print("Очередь пуста")
    else:
        break

2. queue.Queue — потокобезопасная очередь из стандартной библиотеки. Используйте для обмена задачами между потоками.

3. Собная реализация на связном списке — полезна для учебных целей или когда нужно точный контроль над памятью и узлами.

Когда реализация на list подходит, а когда нет

Подходит, если:

• количество операций малое;
• очередь небольшая;
• важна простота и понятность кода.

Не подходит, если:

• ожидается много операций dequeue; тогда O(n) для pop(0) будет узким местом;
• нужна потокобезопасность — используйте queue.Queue;
• важна детерминированная производительность — используйте deque.

Улучшенная, более надёжная реализация (обработка ошибок)

Ниже — версия, которая безопасно обрабатывает нечисловой ввод и уведомляет пользователя о пустой очереди:

from collections import deque

queue = deque()

while True:
    command = input("Команда (enqueue, dequeue, print, front, rear, exit):\n")

    if command == "enqueue":
        raw = input("Введите элемент для добавления: ")
        try:
            value = int(raw)
        except ValueError:
            print("Ожидалось целое число. Попробуйте снова.")
            continue
        queue.append(value)
    elif command == "dequeue":
        if queue:
            removed = queue.popleft()
            print("Удалён элемент:", removed)
        else:
            print("Очередь пуста")
    elif command == "print":
        print(list(queue))
    elif command == "front":
        if queue:
            print(queue[0])
        else:
            print("Очередь пуста")
    elif command == "rear":
        if queue:
            print(queue[-1])
        else:
            print("Очередь пуста")
    elif command == "exit":
        break
    else:
        print("Неизвестная команда")

print("Финальная очередь:", list(queue))

Критерии приёмки

• Возможность добавлять и удалять элементы через команды enqueue и dequeue.
• Команды front, rear и print корректно возвращают ожидаемые значения при непустой очереди.
• При пустой очереди операции dequeue/front/rear дают понятное сообщение об ошибке, а не аварийный выход.
• Реализация с deque выполняет dequeue за O(1).

Тесты / сценарии приемки

1. Добавить 3 элемента подряд, затем вызвать print — ожидается список из трёх элементов.
2. Добавить 2 элемента, вызвать dequeue дважды, затем dequeue ещё раз — ожидается сообщение “Очередь пуста”.
3. Проверить front и rear после нескольких операций enqueue/dequeue.
4. Для deque-подхода измерить время при N = 10000 операций enqueue/dequeue — deque будет существеннее быстрее, чем list с pop(0).

Ментальные модели и подсказки

• Представляйте очередь как очередь в магазине: те, кто пришёл раньше, обслуживаются раньше.
• Для сценариев фоновой обработки задач и распределённых систем думайте о очереди как о буфере между производителем и потребителем.

Сравнение вариантов (краткая таблица)

• list + pop(0): простая, но dequeue — O(n).
• collections.deque: быстрые append/popleft — O(1). Рекомендуется.
• queue.Queue: потокобезопасно, имеет блокирующие операции put/get.
• Связный список: учебно и полезно при специфических требованиях.

Краткий глоссарий (1 строка каждый)

• FIFO — порядок «первый пришёл — первый ушёл».
• enqueue — вставить элемент в хвост.
• dequeue — убрать элемент из головы.
• deque — двухконечная очередь из модуля collections.

Роль‑ориентированные чеклисты

• Для студента: реализуйте базовые операции, проведите 5 тестов, объясните сложность.
• Для интервьюера: попросите реализовать и оптимизировать (переход на deque).
• Для разработчика ПО: используйте deque или queue.Queue в зависимости от однопоточной/многопоточной среды.

Резюме

Очередь — базовая и широко применимая структура данных. Для быстрых и надёжных операций в Python чаще всего используют collections.deque. Реализация на list уместна для простых задач и обучения, но имеет ограничения по производительности при частых операциях удаления из головы.

Важное: если ваша система требует потокобезопасности или блокирующих операций, применяйте queue.Queue; для эффективной одно-проходной очереди — collections.deque.