Очереди в Python: понимание FIFO и LIFO с практическими примерами

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

Очередь — это структура данных, хранящая элементы в линейном порядке. Элементы добавляются в конец и удаляются из начала, следуя принципу First-In, First-Out (FIFO — первым пришёл, первым ушёл). У очереди два логических конца: front (фронт) и rear (хвост) — enqueue (вставка) в хвост, dequeue (удаление) из фронта.

В этом уроке вы узнаете:

• Как работает модуль queue в Python.
• Типы очередей, доступные в Python.
• Как установить и импортировать модуль.
• Ключевые методы объектов Queue и LifoQueue.
• Практические примеры для FIFO и LIFO очередей.
• Пакетные операции, сортировка и разворот очередей.

Как работает модуль Queue

Поведение аналогично физической очереди: первый в очереди — первый обслужен. В структуре данных очереди элемент, поставленный в очередь первым, будет извлечён первым.

Точка rear — где вставляются новые элементы (например, значение 7). Точка front — где элементы покидают очередь; удаление первого элемента даёт значение 1.

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

Типы очередей в Python

Модуль queue в Python предлагает два основных класса очередей:

• FIFO Queue — используйте Queue(). Самый старый элемент всегда удаляется первым.
• LIFO Queue — используйте LifoQueue(). Наиболее недавно добавленный элемент возвращается первым.

Начало работы: импорт модуля

Python поставляется с модулем queue по умолчанию; внешняя установка не требуется.

import queue

Создание FIFO очереди:

q1 = queue.Queue()

Создание LIFO очереди:

q1 = queue.LifoQueue()

Ключевые методы

Оба Queue и LifoQueue предоставляют один и тот же базовый API:

• put(item) — поставить элемент в очередь (enqueue).
• get() — извлечь и вернуть следующий элемент (dequeue).
• empty() — возвращает True, если очередь пуста.
• full() — возвращает True, если очередь достигла максимального размера.
• qsize() — возвращает текущее количество элементов.

Пример FIFO очереди

Вставка одного элемента

import queue
q1 = queue.Queue()
q1.put(10)  # добавить 10 в очередь

Вставка нескольких элементов с лимитом размера

q1 = queue.Queue(maxsize=5)  # максимум 5 элементов
for i in range(1, 6):
    q1.put(i)
print(q1.full())  # → True

Вывод:

True

Извлечение элемента

item = q1.get()
print('Dequeued item:', item)

Вывод:

Dequeued item: 10

Пример LIFO очереди

Вставка одного элемента

q1 = queue.LifoQueue()
q1.put(10)

Извлечение элемента

item = q1.get()
print('Dequeued from LIFO:', item)

Вывод:

Dequeued from LIFO: 10

Пакетные операции

FIFO — вставка 20 чисел

q1 = queue.Queue()
for i in range(20):
    q1.put(i)

FIFO — извлечение всех

while not q1.empty():
    print('Value:', q1.get())

Вывод:

Value: 0
Value: 1
...
Value: 19

LIFO — вставка 20 чисел

q1 = queue.LifoQueue()
for i in range(20):
    q1.put(i)

LIFO — извлечение всех

while not q1.empty():
    print('Value:', q1.get())

Вывод:

Value: 19
Value: 18
...
Value: 0

Сортировка очереди (пузырьковая сортировка)

q1 = queue.Queue()
for item in [11, 5, 4, 21, 3, 10]:
    q1.put(item)

n = q1.qsize()
for i in range(n):
    x = q1.get()
    for j in range(n-1):
        y = q1.get()
        if x > y:
            q1.put(y)
        else:
            q1.put(x)
        x = y
    q1.put(x)

while not q1.empty():
    print(q1.queue[0], end=' ')
    q1.get()

Вывод:

3 4 5 10 11 21

Разворот очереди с рекурсией

def reverse_queue(src, dest):
    item = src.get()
    if not src.empty():
        reverse_queue(src, dest)
    dest.put(item)
    return dest

q1 = queue.Queue()
for item in [11, 5, 4, 21, 3, 10]:
    q1.put(item)

q2 = queue.Queue()
reverse_queue(q1, q2)
while not q2.empty():
    print(q2.queue[0], end=' ')
    q2.get()

Вывод:

10 3 21 4 5 11

Краткое резюме

• Python queue.Queue реализует FIFO; queue.LifoQueue — LIFO.
• Используйте put() для вставки и get() для извлечения.
• Оба класса предоставляют empty(), full() и qsize() для проверки состояния.
• Можно задать максимальный размер FIFO очереди; попытка put() сверх лимита заблокируется, пока не освободится место.
• Сортировка и разворот возможны стандартными алгоритмами, хотя встроенный deque из collections часто даёт больше гибкости.