Очереди: FIFO и честный порядок

Цели урока

• Понять принцип FIFO и почему он важен для корректности систем
• Реализовать очередь на связном списке и кольцевом буфере
• Знать разницу между list.pop(0) O(n) и deque.popleft() O(1)
• Применить очередь в алгоритме BFS

Предварительные знания

• Стеки и принцип LIFO

• Стеки: LIFO и трюк со скобками

2020 год, NHS (британская система здравоохранения) строит систему записи на вакцинацию. Миллионы запросов в день. Принцип один - кто первым записался, тот первым получает слот. FIFO. Любое нарушение порядка - скандал и недоверие к системе. Queue - это не просто структура данных, это гарантия честного порядка.

• **HTTP-серверы**: Nginx обрабатывает входящие соединения в FIFO-порядке
• **Kafka**: сообщения в партиции строго FIFO - ключевое свойство для event sourcing
• **CPU планировщик**: FCFS (First Come First Served) - очередь процессов
• **Стриминг**: ring buffer для аудио/видео предотвращает пропуски

Исторический контекст

Концепция очереди в программировании формализована в 1960-х при создании операционных систем. Дейкстра и его коллеги разрабатывали алгоритмы планирования для THE (Technische Hogeschool Eindhoven) OS - первой ОС с многозадачностью. Очереди готовых процессов стали фундаментом. BFS как алгоритм описан Муром в 1959 году для решения задачи кратчайшего пути в лабиринте.

FIFO - First In, First Out

2020 год, пандемия. Миллионы людей звонят на горячие линии - запросы выстраиваются в очередь. Первый позвонивший - первым получает оператора. Никакого VIP-доступа, никакого прерывания. FIFO (First In, First Out) - принцип честного порядка. Именно его реализует структура данных Queue.

FIFO (First In, First Out) - кто первым встал в очередь, тот первым выйдет. Данные обрабатываются в порядке поступления, без исключений.

Операции: enqueue, dequeue, front

Три фундаментальные операции очереди - все должны выполняться за O(1). Если хотя бы одна из них O(n), структура данных непригодна для production-использования.

• **enqueue(x)** - добавить элемент в конец очереди (back)
• **dequeue()** - удалить и вернуть элемент из начала (front)
• **front() / peek()** - посмотреть первый элемент без удаления

dequeue() на пустой очереди - ошибка. Проверяйте isEmpty() перед dequeue(), или ловите исключение. В production это одна из самых частых причин краша.

Реализация: массив vs связный список

Наивная реализация на обычном массиве ломается на dequeue(): чтобы убрать первый элемент, нужно сдвинуть все остальные - это O(n). При 1000 RPS на сервере это катастрофа. Два решения: связный список или кольцевой буфер.

Связный список идеален для очереди: enqueue в tail O(1), dequeue из head O(1). Никаких сдвигов.

Кольцевая очередь - массив без сдвигов

Гениальная идея: не сдвигать элементы, а двигать указатели front и back по кольцу. Массив фиксированного размера, back двигается вперёд при enqueue, front - при dequeue. Когда back доходит до конца - заворачивается на начало. Это ring buffer - основа TCP/IP стеков и audio-буферов.

Ring buffer используется в: TCP/IP receive buffer, audio/video стриминге (буферизация), логах фиксированного размера (хранят последние N записей), сетевых картах.

BFS - обход графа с очередью

LinkedIn считает 'степени связи' - 1st, 2nd, 3rd. Алгоритм за этим: BFS (Breadth-First Search). Сначала все прямые контакты (уровень 1), потом их контакты (уровень 2). Именно FIFO-очередь обеспечивает обход по уровням - кладём всех соседей текущего узла, берём из очереди по порядку.

Почему очередь, а не стек? FIFO гарантирует обход по уровням: сначала все на расстоянии 1, потом на расстоянии 2. Именно это даёт BFS свойство нахождения кратчайшего пути в невзвешенном графе.

Реализуй очередь с помощью collections.deque: ```python from collections import deque class Queue: def __init__(self): pass def enqueue(self, item): pass def dequeue(self): pass def is_empty(self): pass ```

from collections import deque class Queue: def __init__(self): self.data = deque() def enqueue(self, item): self.data.append(item) # O(1) def dequeue(self): if self.is_empty(): raise IndexError("Queue is empty") return self.data.popleft() # O(1)! def is_empty(self): return len(self.data) == 0

Реализуй очередь с помощью двух стеков: ```python class QueueFromStacks: def __init__(self): self.stack_in = [] # Для enqueue self.stack_out = [] # Для dequeue def enqueue(self, item): pass def dequeue(self): pass ```

class QueueFromStacks: def __init__(self): self.stack_in = [] self.stack_out = [] def enqueue(self, item): self.stack_in.append(item) def dequeue(self): if not self.stack_out: while self.stack_in: self.stack_out.append(self.stack_in.pop()) if not self.stack_out: raise IndexError("Queue is empty") return self.stack_out.pop()

Найди кратчайший путь в лабиринте с помощью BFS: ```python def shortest_path(maze, start, end): # maze - 2D массив: 0 = проход, 1 = стена # start, end - кортежи (row, col) # Вернуть длину кратчайшего пути или -1 pass # maze = [ # [0, 0, 1, 0], # [1, 0, 0, 0], # [0, 0, 1, 0] # ] # shortest_path(maze, (0,0), (2,3)) -> 5 ```

from collections import deque def shortest_path(maze, start, end): rows, cols = len(maze), len(maze[0]) queue = deque([(start[0], start[1], 0)]) visited = {start} directions = [(0, 1), (0, -1), (1, 0), (-1, 0)] while queue: row, col, dist = queue.popleft() if (row, col) == end: return dist for dr, dc in directions: nr, nc = row + dr, col + dc if (0 <= nr < rows and 0 <= nc < cols and maze[nr][nc] == 0 and (nr, nc) not in visited): visited.add((nr, nc)) queue.append((nr, nc, dist + 1)) return -1

Связанные темы

Очередь - основа для важных алгоритмов:

• Дек — Двусторонняя очередь - операции с обоих концов за O(1)
• BFS — Обход графа в ширину, кратчайшие пути в невзвешенном графе
• Priority Queue / Heap — Очередь с приоритетом - выходит не первый, а с наивысшим приоритетом

Ключевые идеи

• FIFO: первый вошёл - первый вышел. Основа справедливого порядка в системах
• Операции enqueue, dequeue, front - все O(1) при правильной реализации
• list.pop(0) - O(n); collections.deque.popleft() - O(1). Используйте deque
• Ring buffer: кольцевая очередь на массиве без сдвигов, O(1) все операции
• BFS требует очередь для обхода по уровням - замените на стек и получите DFS

Вопросы для размышления

• Почему для реализации очереди связный список лучше обычного массива?
• Как бы устроить 'приоритетную очередь' - где выходит не первый, а самый важный?
• Если заменить очередь в BFS на стек - что получится и почему?

Связанные уроки

• ds-03-stacks
• ds-05-deque
• alg-12-bfs
• ds-14-heaps-intro
• os-04-scheduling
• alg-01-big-o