Очередь — структура данных, в которой элементы добавляются с одного конца и
удаляются с другого.
Главное правило очереди:
FIFO = First In, First Out
То есть:
первый добавленный элемент удаляется первым
У очереди есть два конца:
front -> начало, откуда элементы удаляются
back -> конец, куда элементы добавляются
Пример:
enqueue(7)
enqueue(3)
enqueue(9)
enqueue(1)
Состояние очереди:
front back
7 3 9 1
Если выполнить:
dequeue()
то будет удалён 7, потому что он был добавлен первым.
Термины
queue -> очередь
front -> первый элемент
back -> последний элемент
size -> количество элементов в очереди
enqueue(x) -> добавить x в конец очереди
dequeue() -> удалить и вернуть первый элемент
peek() -> посмотреть первый элемент без удаления
isEmpty() -> проверить, пуста ли очередь
Очередь задаётся тремя вещами:
1. набор элементов
2. порядок добавления элементов
3. два конца: front для удаления и back для добавления
Структура очереди
Структура отвечает на вопрос:
Что внутри и как расположено?
У очереди есть:
элементы
начало
конец
порядок добавления
размер
Очередь можно представить как горизонтальную последовательность:
front back
↓ ↓
[7] -> [3] -> [9] -> [1]
Новые элементы добавляются в конец. Удаляются из начала.
Свойства
Короткая карта свойств очереди как структуры:
front -> точка удаления элементов
back -> точка добавления элементов
FIFO -> первым вошёл, первым вышел
упорядоченность -> порядок элементов имеет значение
размер -> количество элементов в очереди
пустота -> очередь может не содержать элементов
ограниченный доступ -> доступен только первый элемент
Конкретная очередь содержит конечное число элементов:
size = n
пустая очередь = size == 0
непустая очередь = size > 0
Для непустой очереди существуют начало и конец:
front(queue)
back(queue)
Если в очереди один элемент, начало и конец указывают на один и тот же элемент:
queue = [7]
front = 7
back = 7
Важно отделять свойства очереди от характеристик конкретной очереди:
свойство: у очереди есть начало
характеристика: первый элемент этой очереди = 7
свойство: у очереди есть размер
характеристика: размер этой очереди = 4
FIFO
Очередь работает по правилу:
First In, First Out
Если элементы добавлены в таком порядке:
7, 3, 9, 1
то удаляться они будут в том же порядке:
7, 3, 9, 1
Ограниченный доступ
В отличие от массива, очередь не даёт произвольный доступ по индексу как
базовую операцию.
arr[i] -> обычная операция массива
queue[i] -> не базовая операция очереди
Очередь скрывает внутренние позиции и даёт работать с началом и концом:
enqueue
dequeue
peek
Пустота
Очередь может быть пустой:
queue = []
size = 0
Для пустой очереди нельзя корректно выполнить:
dequeue()
peek()
если реализация явно не задаёт специальное поведение для этих случаев.
Базовые операции
Создание
queue = []
Обычно:
O(1)
Enqueue
Добавить элемент в конец очереди:
enqueue(queue, x)
Пример:
queue = [7, 3, 9]
enqueue(1)
queue = [7, 3, 9, 1]
Обычно:
O(1)
Dequeue
Удалить и вернуть первый элемент:
dequeue(queue)
Пример:
queue = [7, 3, 9, 1]
dequeue() -> 7
queue = [3, 9, 1]
Условие:
size(queue) > 0
Обычно:
O(1)
Peek / Front
Посмотреть первый элемент без удаления:
peek(queue)
front(queue)
Пример:
queue = [7, 3, 9, 1]
peek() -> 7
queue = [7, 3, 9, 1]
Условие:
size(queue) > 0
Сложность:
O(1)
Is Empty
Проверить, пуста ли очередь:
isEmpty(queue)
Пример:
[] -> true
[7, 3, 9] -> false
Сложность:
O(1)
Size
Получить количество элементов:
size(queue)
Обычно:
O(1)
если размер хранится отдельно.
Проход по очереди
Если нужно обработать все элементы через операции очереди, её можно постепенно
разбирать:
while not isEmpty(queue):
x = dequeue(queue)
use x
Сложность:
O(n)
Важно: такой проход изменяет очередь, потому что dequeue() удаляет элементы.
Таблица сложностей
| Операция | Сложность |
|---|---|
| создание | O(1) |
enqueue(x) |
O(1) |
dequeue() |
O(1) |
peek() / front() |
O(1) |
isEmpty() |
O(1) |
size() |
O(1) |
| проход с удалением всех элементов | O(n) |
| поиск произвольного значения | O(n) |
Реализация
Очередь — это абстрактная структура данных. Её можно реализовать разными
способами.
Через связный список
Нужно хранить ссылки на начало и конец:
front back
↓ ↓
[7] -> [3] -> [9] -> [1]
Тогда:
enqueue(x) -> добавить новый узел после back
dequeue() -> удалить узел front
peek() -> прочитать front
Все основные операции работают за O(1), если есть ссылки на front и back.
Через кольцевой буфер
Очередь можно хранить в массиве фиксированной ёмкости с двумя указателями:
capacity = 8
front = 2
back = 6
index: 0 1 2 3 4 5 6 7
value: _ _ 7 3 9 1 _ _
При добавлении back сдвигается вперёд. При удалении front сдвигается вперёд.
Когда указатель доходит до конца массива, он переходит в начало:
next(i) = (i + 1) mod capacity
Если буфер заполнен, реализация может создать новый буфер большей ёмкости и
перенести элементы. Тогда отдельное расширение стоит O(n), но добавление
остаётся амортизированно быстрым.
Через динамический массив
Если добавлять в конец и удалять из начала обычного динамического массива:
enqueue(x) -> append(x)
dequeue() -> remove first element
то удаление из начала обычно стоит:
O(n)
потому что все оставшиеся элементы нужно сдвинуть влево.
Поэтому для очереди лучше использовать связный список, кольцевой буфер или
готовую реализацию дека.
Очередь, стек и дек
Стек удаляет последний добавленный элемент:
stack -> LIFO
Очередь удаляет первый добавленный элемент:
queue -> FIFO
Дек обобщает очередь:
deque -> операции доступны с обоих концов
Обычную очередь можно получить из дека:
enqueue(x) -> pushBack(x)
dequeue() -> popFront()
Python
В Python для обычной очереди часто используют:
collections.deque
Основные операции:
append(x) -> enqueue, добавить в конец
popleft() -> dequeue, удалить из начала
d[0] -> peek, посмотреть первый элемент
Пример:
from collections import deque
q = deque()
q.append(7)
q.append(3)
q.append(9)
print(q[0]) # 7
print(q.popleft()) # 7
print(q) # deque([3, 9])
Для потокобезопасной очереди в стандартной библиотеке есть:
queue.Queue
Её используют в задачах с потоками, где важны блокировки и синхронизация.
Типичные применения
BFS
очередь задач
обработка событий
планирование запросов
буферизация данных
симуляции
producer-consumer
Формальная схема
Queue = {
elements: e1, e2, ..., en,
front: e1,
back: en,
size: n,
rule: FIFO
}
Операции очереди изменяют или используют одну из четырёх сущностей:
начало
конец
размер
порядок удаления
Примеры:
enqueue(x) -> меняет конец и увеличивает размер
dequeue() -> возвращает начало и уменьшает размер
peek() -> читает начало без изменения очереди
isEmpty() -> проверяет размер
Минимальная формулировка:
очередь = структура с доступом к первому добавленному элементу
