Визуализация
Сценарий: Поток
Легенда цветов
Как работает очередь
Идея структуры: Очередь реализует принцип FIFO (First In, First Out - первым пришел, первым ушел). Элементы добавляются в один конец (хвост), а извлекаются с другого конца (голова). Это в точности повторяет поведение обычной очереди в магазине.
Базовые операции:
- Enqueue (поставить в очередь): добавление элемента со стороны указателя
tail. - Dequeue (обслужить): извлечение элемента, на который указывает
head. - Peek / Front: посмотреть элемент на голове очереди без его извлечения.
Сдвиг указателей. Как видно в сценарии "Поток", при активной работе оба указателя все время сдвигаются вправо, оставляя за собой пустую память. Из-за этого очередь на базе массива может быстро исчерпать свободное место. Для решения этой проблемы используют кольцевую очередь.
Где применяется:
- Буферизация ввода/вывода, буфер пакетов роутера;
- Очередь задач (Task Queue), планировщики ОС;
- Алгоритм поиска в ширину (BFS) в графах и деревьях.
Зеркальная структура. Если и класть, и брать с одного конца, получится стек с принципом LIFO. Обе стратегии сразу умеет дек.
Синонимы названия: Queue, FIFO-очередь, буфер FIFO.
Сложность
Сложность - это оценка того, как быстро растет потребление ресурса при росте числа элементов n. Ресурса у структуры два, поэтому и оценки две: по времени и по памяти. Обе записывают через O-нотацию - у нас есть отдельная анимация о том, как читать такие записи.
По времени
| Операция | Сложность | Комментарий |
|---|---|---|
| Добавление (Enqueue) | O(1) | Вставка по индексу tail и сдвиг указателя. |
| Удаление (Dequeue) | O(1) | Извлечение по индексу head и сдвиг указателя. |
| Просмотр (Peek) | O(1) | Чтение значения по индексу head. |
По памяти
| Характеристика | Оценка | Комментарий |
|---|---|---|
| Затраты по памяти | O(n) | Для хранения n элементов требуется соответствующий массив или список. |
Свойства
| Свойство | Значение | Комментарий |
|---|---|---|
| Принцип работы | FIFO | Первым пришел - первым ушел. Элементы добавляются в конец (tail) и извлекаются из начала (head). |
| Доступ к элементам | Ограничен | Произвольный доступ по индексу отсутствует; просматривать и извлекать можно только первый элемент. |
| Эффективность | O(1) | Операции вставки (enqueue) и извлечения (dequeue) занимают константное время. |
Примеры реализации: Очередь (Queue)
Код на C (массив)
#include <stdio.h>
#define MAX_SIZE 100 // Максимальная вместимость очереди
int queue[MAX_SIZE]; // Статический массив для элементов
int head = 0; // Указатель на голову (индекс элемента для извлечения)
int tail = 0; // Указатель на хвост (индекс для вставки нового элемента)
// Функция добавления элемента в конец очереди (Enqueue)
void enqueue(int item) {
// Защита от переполнения: если достигли конца массива
if (tail == MAX_SIZE) return;
// Записываем элемент и смещаем хвост вправо
queue[tail] = item;
tail++;
}
// Функция извлечения элемента из начала очереди (Dequeue)
int dequeue() {
// Если голова догнала хвост, значит элементов больше нет
if (head == tail) return -1;
// Берем первый элемент и смещаем голову вправо
int item = queue[head];
head++;
return item;
}Код на Python (collections.deque)
# В Python стандартный список (list) крайне неэффективен для очередей:
# удаление из начала массива list.pop(0) требует сдвига всех элементов (O(n)).
# Поэтому для очередей всегда используют двустороннюю очередь - deque.
from collections import deque
# Создаем пустую очередь
queue = deque()
# Добавление элементов в конец очереди (Enqueue) O(1)
queue.append(10) # Очередь: [10]
queue.append(20) # Очередь: [10, 20]
# Извлечение первого элемента из головы очереди (Dequeue) O(1)
# popleft() удаляет и возвращает самый старый элемент
item = queue.popleft() # Возвращает 10. Очередь: [20]Код на JavaScript (массив)
// Реализация простой очереди на базе динамического массива в JavaScript
class SimpleQueue {
constructor() {
this.items = []; // Внутренний массив
this.head = 0; // Указатель на первый элемент, чтобы не удалять через shift()
}
// Постановка в очередь (добавляет в конец массива)
enqueue(element) {
this.items.push(element);
}
// Обслуживание из очереди (возвращает элемент с головы)
dequeue() {
// Если указатель головы дошел до конца массива - очередь пуста
if (this.head >= this.items.length) return null;
const item = this.items[this.head];
this.head++; // Сдвигаем виртуальное начало вправо
// ВНИМАНИЕ: В реальных нагруженных приложениях старые элементы перед head
// останутся висеть в памяти. Нужно периодически очищать массив (slice),
// если this.head стал слишком большим.
return item;
}
}Хотите разобрать тему глубже? В нашем бесплатном курсе есть урок про очередь и принцип FIFO - с подробной теорией, задачами и проверочными вопросами.