Очередь (queue): структура данных FIFO, операции и реализация на Python
Очередь как структура данных простыми словами: принцип FIFO, операции за O(1), почему list.pop(0) медленный, collections.deque, кольцевая очередь и применение в BFS и планировщиках.
Коротко
| Вопрос | Ответ |
|---|---|
| Что это | Структура данных, где элементы выходят в том же порядке, что и вошли |
| Принцип | FIFO — first in, first out: первым пришёл, первым ушёл |
| Операции | Добавить в конец, забрать из начала, посмотреть первый — всё за O(1) |
| Чем пользоваться в Python | collections.deque: append и popleft |
| Чем не пользоваться | list.pop(0) — это O(n) на каждое извлечение |
| Где встречается | Обход графа в ширину, планировщики, буферы, очереди сообщений |
Если нужен обзор сразу двух структур, он есть в статье про стек и очередь. Здесь разбираем только очередь, зато подробно: как она устроена внутри, на чём её строить и где чаще всего ошибаются.
Что такое очередь
Очередь — это список с двумя концами, у каждого из которых своя роль. В один конец элементы только добавляют, из другого только забирают. Вставить что-то в середину или вытащить третий по счёту элемент нельзя.
Отсюда главное свойство: кто раньше встал в очередь, тот раньше из неё выйдет. Это и называют принципом FIFO (first in, first out).
забираем отсюда добавляем сюда
↓ ↓
┌─────┬─────┬─────┬─────┐
│ Аня │ Боря│ Вика│ Гена│ ← Даша встаёт в конец
└─────┴─────┴─────┴─────┘
голова хвост
(head) (tail)
Аналогия та же, что в названии: касса в магазине. Аня пришла первой, её первой и обслужат. Даша пришла последней и встаёт в хвост.
Очередь — абстрактный тип данных. Это значит, что слово «очередь» описывает поведение (какие есть операции и что они обещают), а не то, как данные лежат в памяти. Хранить элементы можно в массиве, в связном списке, в кольцевом буфере — ниже разберём все три варианта.
Чем очередь отличается от стека
У стека один рабочий конец: куда положили, оттуда и забрали, поэтому последний элемент выходит первым (LIFO). У очереди концов два, и порядок сохраняется.
| Положили 1, 2, 3 | Забираем |
|---|---|
| Стек | 3, 2, 1 |
| Очередь | 1, 2, 3 |
Обе структуры относятся к линейным: элементы выстроены в ряд, у каждого один сосед слева и один справа. Как они соотносятся с деревьями, графами и хеш-таблицами, смотрите в обзоре структур данных.
Операции очереди
Набор небольшой, названия зависят от языка и учебника.
| Операция | Что делает | В Python (deque) | Сложность |
|---|---|---|---|
| enqueue (push, offer) | Добавить элемент в хвост | q.append(x) | O(1) |
| dequeue (pop, poll) | Забрать элемент из головы | q.popleft() | O(1) |
| peek (front) | Посмотреть первый, не забирая | q[0] | O(1) |
| is_empty | Проверить, пуста ли очередь | not q | O(1) |
| size | Узнать количество элементов | len(q) | O(1) |
Всё работает за константное время — в этом и ценность структуры. Поиск элемента по значению возможен, но это O(n), и если он вам нужен часто, очередь выбрана зря.
Как это выглядит в коде:
from collections import deque queue = deque() queue.append('Аня') # enqueue queue.append('Боря') queue.append('Вика') print(queue[0]) # Аня — peek, очередь не меняется print(queue.popleft()) # Аня — dequeue print(queue.popleft()) # Боря print(len(queue)) # 1 print(bool(queue)) # True — в очереди ещё есть Вика
Очередь в Python: почему не список
Первое, что приходит в голову, — обычный list: добавляем через append, забираем через pop(0). Работает правильно, но медленно.
Что не так с list.pop(0)
Список в Python — это динамический массив: элементы лежат в памяти подряд, без дырок. Когда вы удаляете нулевой элемент, место освобождается в начале, и интерпретатору приходится сдвинуть все остальные элементы на одну позицию влево.
до: [ A | B | C | D | E ]
pop(0): ↓
после: [ B | C | D | E ] ← B, C, D, E переехали
Один pop(0) стоит O(n), где n — текущая длина списка. Если так разобрать всю очередь из n элементов, сдвигов наберётся
то есть вместо ожидаемых .
На маленьких данных этого не видно, поэтому ошибка легко доживает до продакшена или до большого теста в задаче. Проверим на цифрах:
from collections import deque from timeit import timeit def drain_list(n): q = list(range(n)) while q: q.pop(0) def drain_deque(n): q = deque(range(n)) while q: q.popleft() for n in (10_000, 100_000, 400_000): t_list = timeit(lambda: drain_list(n), number=1) t_deque = timeit(lambda: drain_deque(n), number=1) print(f'{n:>7}: list {t_list:.3f} c, deque {t_deque:.4f} c')
У меня на ноутбуке (Python 3.9) получилось так:
10000: list 0.005 c, deque 0.0004 c
100000: list 0.668 c, deque 0.0036 c
400000: list 11.616 c, deque 0.0145 c
Ваши числа будут другими, но картина та же: у deque время растёт пропорционально n, у списка — заметно быстрее. На 400 тысячах элементов разница уже в сотни раз.
collections.deque
deque — двусторонняя очередь из стандартной библиотеки. Добавление и удаление с любого конца у неё стоит O(1), потому что внутри не один сплошной массив, а цепочка блоков фиксированного размера: чтобы убрать первый элемент, достаточно подвинуть указатель на начало, остальные элементы никуда не едут.
Для обычной очереди нужны только два метода: append (в хвост) и popleft (из головы). Остальные возможности — работа с обоих концов, maxlen, rotate — разобраны в статье про дек.
Плата за быстрые концы — медленная середина: q[i] для элемента в глубине дека работает за O(n). Для очереди это не проблема, в середину ей лазить и не положено.
Если хочется, чтобы код говорил словами предметной области и случайно не позвал pop() с неправильного конца, оберните дек в класс:
from collections import deque class Queue: def __init__(self): self._items = deque() def enqueue(self, item): self._items.append(item) def dequeue(self): if not self._items: raise IndexError('dequeue from empty queue') return self._items.popleft() def peek(self): if not self._items: raise IndexError('peek from empty queue') return self._items[0] def __len__(self): return len(self._items) q = Queue() for x in (1, 2, 3): q.enqueue(x) print(q.dequeue(), q.peek(), len(q)) # 1 2 2
На собеседовании и в олимпиадных задачах обёртку обычно не пишут — используют deque напрямую.
queue.Queue — это про потоки
В стандартной библиотеке есть ещё модуль queue с классом Queue. Название сбивает с толку: кажется, что это и есть «правильная» очередь. На деле она предназначена для обмена данными между потоками: умеет блокировать поток, пока очередь пуста или переполнена, и тратит время на блокировки.
import threading from queue import Queue tasks = Queue(maxsize=100) results = [] lock = threading.Lock() def worker(): while True: item = tasks.get() # ждёт, пока появится задача if item is None: # сигнал «работы больше нет» break with lock: results.append(item * item) threads = [threading.Thread(target=worker) for _ in range(3)] for t in threads: t.start() for n in range(10): tasks.put(n) for _ in threads: tasks.put(None) for t in threads: t.join() print(sorted(results)) # [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
Правило простое: в однопоточном алгоритме — collections.deque, между потоками — queue.Queue, между корутинами — asyncio.Queue.
Как очередь устроена внутри
Пользоваться готовым деком достаточно для работы. Но на собеседовании могут попросить написать очередь руками, и тогда нужно понимать два классических способа.
На связном списке
Храним указатели на первый и последний узел. Добавление цепляет новый узел к хвосту, извлечение отцепляет голову. Ничего не сдвигается, обе операции — O(1).
class Node: def __init__(self, value): self.value = value self.next = None class LinkedQueue: def __init__(self): self.head = None # отсюда забираем self.tail = None # сюда добавляем self.size = 0 def enqueue(self, value): node = Node(value) if self.tail is None: self.head = node else: self.tail.next = node self.tail = node self.size += 1 def dequeue(self): if self.head is None: raise IndexError('dequeue from empty queue') node = self.head self.head = node.next if self.head is None: self.tail = None self.size -= 1 return node.value
Обратите внимание на строку self.tail = None в dequeue. Когда из очереди забрали последний элемент, обнулить нужно оба указателя. Если про хвост забыть, следующий enqueue прицепит новый узел к уже удалённому, а head останется None — элемент потеряется.
Минус этого варианта — память: на каждый элемент создаётся отдельный объект-узел со ссылкой, и лежат они в памяти вразброс.
Кольцевая очередь на массиве
Второй способ — массив фиксированного размера и индекс головы. Вместо того чтобы сдвигать элементы после извлечения, сдвигаем сам индекс. А когда индекс доходит до конца массива, он перескакивает на начало — отсюда название «кольцевая» (циклическая) очередь.
class CircularQueue: def __init__(self, capacity): self.data = [None] * capacity self.capacity = capacity self.head = 0 # индекс первого элемента self.size = 0 def enqueue(self, value): if self.size == self.capacity: raise OverflowError('queue is full') tail = (self.head + self.size) % self.capacity self.data[tail] = value self.size += 1 def dequeue(self): if self.size == 0: raise IndexError('dequeue from empty queue') value = self.data[self.head] self.data[self.head] = None self.head = (self.head + 1) % self.capacity self.size -= 1 return value
Вся магия в операции % capacity: она заворачивает индекс обратно в начало массива. Посмотрим на очередь из четырёх ячеек:
enqueue A, B, C, D [ A | B | C | D ] head = 0, size = 4
dequeue → A, B [ . | . | C | D ] head = 2, size = 2
enqueue E, F [ E | F | C | D ] head = 2, size = 4
E и F легли в освободившиеся ячейки в начале массива. Логический порядок при этом не нарушился: читаем от head по кругу и получаем C, D, E, F.
Хранить size отдельно — самый простой способ отличить пустую очередь от полной. Если держать два индекса, head и tail, то в обоих случаях они совпадают, и приходится выкручиваться: жертвовать одной ячейкой или заводить флаг. Подробности и варианты поведения при переполнении — в статье про кольцевой буфер.
Кольцевая очередь хороша там, где размер известен заранее и не хочется выделять память на ходу: буфер клавиатуры, сетевые пакеты, аудиопоток, логи последних N событий.
Сравнение реализаций
| Реализация | enqueue | dequeue | Память | Когда брать |
|---|---|---|---|---|
list + pop(0) | O(1) аморт. | O(n) | Компактно | Никогда, если очередь не крошечная |
| Связный список | O(1) | O(1) | Узел и ссылка на элемент | Учебные задачи, размер неизвестен |
| Кольцевой массив | O(1) | O(1) | Фиксированный массив | Размер ограничен сверху |
collections.deque | O(1) | O(1) | Блоки, растёт по мере нужды | Почти всегда в Python |
Есть и третий, экзотический способ — собрать очередь из двух стеков. В работе он нужен редко, зато это популярная задача на интервью: очередь на двух стеках.
Где применяется очередь
Обход графа в ширину (BFS)
Главное алгоритмическое применение. Поиск в ширину обходит вершины «слоями»: сначала стартовую, потом всех её соседей, потом соседей соседей. Очередь гарантирует именно такой порядок: вершины ближнего слоя попали в неё раньше, значит, и обработаются раньше.
Из этого следует полезное свойство: в невзвешенном графе BFS находит кратчайший путь по числу рёбер.
from collections import deque def shortest_path(graph, start, goal): queue = deque([start]) dist = {start: 0} while queue: node = queue.popleft() if node == goal: return dist[node] for neighbor in graph[node]: if neighbor not in dist: dist[neighbor] = dist[node] + 1 queue.append(neighbor) return -1 graph = { 'A': ['B', 'C'], 'B': ['A', 'D'], 'C': ['A', 'D', 'E'], 'D': ['B', 'C', 'F'], 'E': ['C', 'F'], 'F': ['D', 'E'], } print(shortest_path(graph, 'A', 'F')) # 3
Если заменить очередь на стек, получится обход в глубину, и кратчайший путь он уже не гарантирует. Разница разобрана в статье про DFS и BFS.
Здесь цена list.pop(0) особенно высока: на графе в сотни тысяч вершин линейный BFS превращается в квадратичный и не проходит по времени.
Планировщики задач
Когда исполнителей меньше, чем работы, задачи ставят в очередь. Простейшая схема — round-robin: каждой задаче дают фиксированный квант времени, и если она не успела закончиться, её отправляют в хвост.
from collections import deque def round_robin(tasks, quantum): queue = deque(tasks) order = [] while queue: name, remaining = queue.popleft() order.append(name) remaining -= quantum if remaining > 0: queue.append((name, remaining)) return order print(round_robin([('A', 5), ('B', 2), ('C', 4)], quantum=2)) # ['A', 'B', 'C', 'A', 'C', 'A']
Задача B уложилась в один квант, C понадобилось два, A — три, и при этом никто не ждал слишком долго. Планировщики настоящих операционных систем устроены сложнее и учитывают приоритеты, но идея «отработал своё — иди в конец» лежит в основе многих из них.
По той же логике работают очередь печати, пул потоков веб-сервера и цикл событий в JavaScript и asyncio: готовые к выполнению колбэки ждут своей очереди в буквальном смысле.
Буферы и скользящие окна
Очередь сглаживает разницу в скорости между тем, кто производит данные, и тем, кто их потребляет: клавиатура и программа, сеть и видеоплеер, датчик и обработчик.
Частный случай — «последние k элементов». Новый элемент заходит в хвост, самый старый выпадает из головы. Так решается задача про дубликаты на расстоянии не больше k: держим в очереди окно из последних k чисел, а рядом — множество для быстрой проверки.
from collections import deque def contains_nearby_duplicate(nums, k): window = deque() seen = set() for x in nums: if x in seen: return True window.append(x) seen.add(x) if len(window) > k: seen.remove(window.popleft()) return False print(contains_nearby_duplicate([1, 2, 3, 1], 3)) # True print(contains_nearby_duplicate([1, 2, 3, 1, 2, 3], 2)) # False
Очередь здесь отвечает на вопрос «кого выкидывать следующим», множество — на вопрос «встречался ли уже такой». Время O(n), память O(k).
Очереди сообщений
В бэкенде очередь вырастает до отдельного сервиса: RabbitMQ, Kafka, Amazon SQS. Один сервис кладёт сообщение («отправь письмо», «пересчитай отчёт»), другой забирает, когда освободится. Отправителю не нужно ждать результата, а всплеск нагрузки не роняет обработчик — сообщения просто копятся.
Идея та же, FIFO, но появляются вопросы, которых нет у структуры в памяти: что делать, если обработчик упал посреди работы, как не обработать сообщение дважды, сохраняется ли порядок при нескольких потребителях. Об этом — в статье про очереди сообщений.
Разновидности очереди
Под словом «очередь» иногда имеют в виду родственные структуры. Полезно их различать.
| Структура | Чем отличается от обычной очереди |
|---|---|
| Дек | Добавлять и забирать можно с обоих концов |
| Очередь с приоритетом | Первым выходит не самый старый, а самый «важный»; операции O(log n) |
| Кольцевая очередь | Фиксированный размер, место переиспользуется по кругу |
| Монотонная очередь | Поддерживает элементы в отсортированном порядке, даёт максимум окна за O(1) |
Очередь с приоритетом, строго говоря, уже не FIFO: порядок прихода в ней не важен. Она строится на куче, а не на массиве с двумя концами, и в Python живёт в модуле heapq.
Типичные ошибки
list.pop(0)илиlist.insert(0, x)в цикле. Самая частая. Код проходит маленькие тесты и падает по времени на больших.pop()вместоpopleft(). У декаpop()забирает элемент справа, и очередь молча превращается в стек. BFS при этом становится обходом в глубину и выдаёт неверные расстояния.- Извлечение из пустой очереди.
deque().popleft()бросаетIndexError. Проверяйтеif queue:или стройте цикл какwhile queue:. queue.Queueв однопоточном алгоритме. Работает, но медленнее дека из-за блокировок. А вызовget()на пустой очереди не бросит исключение, а подвесит программу навсегда.- Пометка «посещено» при извлечении, а не при добавлении. В BFS это приводит к тому, что одна вершина попадает в очередь много раз. Отмечайте вершину в момент
append, как в примере выше. - Забытый хвост в связном списке. После удаления последнего элемента нужно обнулить и
head, иtail. - Путаница пустой и полной кольцевой очереди. Если хранить только два индекса, оба состояния выглядят одинаково. Проще всего завести счётчик
size.
Что спрашивают на собеседованиях
Отдельная задача «реализуйте очередь» попадается, но чаще очередь оказывается инструментом внутри другой задачи. К чему стоит быть готовым:
- Объяснить, что такое FIFO и чем очередь отличается от стека.
- Сказать, почему
list.pop(0)работает за O(n) и чем его заменить. - Написать очередь на связном списке или кольцевом массиве без готовых библиотек.
- Реализовать очередь на двух стеках и объяснить амортизированную O(1).
- Написать BFS: кратчайший путь в лабиринте, обход дерева по уровням, число островов.
- Найти максимум в скользящем окне — это уже монотонная очередь.
В других языках готовые очереди тоже есть: ArrayDeque в Java, std::queue в C++. В JavaScript встроенной очереди нет, а Array.prototype.shift() страдает от той же проблемы, что и pop(0), поэтому на больших данных очередь пишут сами — на индексе головы или связном списке.
Что запомнить
- Очередь — это FIFO: добавляем в хвост, забираем из головы, порядок сохраняется.
- Все основные операции должны стоить O(1). Если это не так, выбрана неудачная реализация.
- В Python очередь — это
collections.dequeсappendиpopleft.list.pop(0)— O(n). queue.Queueнужна для потоков, а не для алгоритмов.- Внутри очередь строят на связном списке или на кольцевом массиве.
- Видите «кратчайший путь в невзвешенном графе», «по уровням», «обработать в порядке поступления» — почти наверняка нужна очередь.