EasyТеория7 min

Очередь

FIFO структура: очередь, двусторонняя очередь (deque), приоритетная очередь

AlgoStacks and queues

Очередь (Queue)

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

Очередь — структура данных, работающая по принципу FIFO (First In, First Out — первый вошёл, первый вышел). Как очередь в магазине: кто первый встал, тот первый обслужен.

Enqueue (добавление):          Dequeue (извлечение):

  -> | 4 | 3 | 2 | 1 | ->      | 4 | 3 | 2 | -> 1 (удалён)
      back           front       back       front

Операции

Операция Описание Сложность
enqueue(x) Добавить в конец O(1)
dequeue() Удалить из начала O(1)*
peek/front() Посмотреть первый элемент O(1)
isEmpty() Проверка на пустоту O(1)

* O(1) только при подходящей структуре: SplQueue в PHP, collections.deque в Python, Queue<T> в C#. Удаление из начала обычного массива (array_shift, list.pop(0)) — O(n).

Реализация

// PHP: SplQueue — optimal queue implementation
$queue = new SplQueue();
$queue->enqueue(1);      // [1]
$queue->enqueue(2);      // [1, 2]
$queue->enqueue(3);      // [1, 2, 3]
$queue->dequeue();       // 1, queue = [2, 3]
$queue->bottom();        // peek: 2

// WARNING: Do NOT use array_shift as dequeue!
// array_shift() = O(n), because it re-indexes all elements
## Deque (Double-Ended Queue)

Двусторонняя очередь — можно добавлять и удалять с обоих концов.

// PHP: SplDoublyLinkedList as deque
$dq = new SplDoublyLinkedList();
$dq->push(1);        // Add right:  [1]
$dq->push(2);        // Add right:  [1, 2]
$dq->unshift(0);     // Add left:   [0, 1, 2]
$dq->pop();          // Remove right: 2, deque = [0, 1]
$dq->shift();        // Remove left:  0, deque = [1]
## Приоритетная очередь (Priority Queue)

Элементы извлекаются не по порядку добавления, а по приоритету. Реализуется через кучу (heap).

// PHP: SplPriorityQueue — max-heap by default
$pq = new SplPriorityQueue();
$pq->insert('task_a', 5);   // priority 5
$pq->insert('task_b', 1);   // priority 1
$pq->insert('task_c', 3);   // priority 3

$pq->extract();  // -> 'task_a' (highest priority)
$pq->extract();  // -> 'task_c' (priority 3)
$pq->extract();  // -> 'task_b' (priority 1)

// For min-heap: use SplMinHeap
$heap = new SplMinHeap();
$heap->insert(5);
$heap->insert(1);
$heap->insert(3);
$heap->extract();  // -> 1 (minimum)
| Операция | Сложность | |------------------|-----------| | insert | O(log n) | | extract | O(log n) | | peek (top) | O(1) |

Задача 1: Реализация очереди через два стека

class QueueViaStacks
{
    private array $stackIn = [];
    private array $stackOut = [];

    public function enqueue(int $x): void
    {
        $this->stackIn[] = $x;
    }

    public function dequeue(): int
    {
        if (empty($this->stackOut)) {
            while (!empty($this->stackIn)) {
                $this->stackOut[] = array_pop($this->stackIn);
            }
        }
        return array_pop($this->stackOut);
    }

    public function peek(): int
    {
        if (empty($this->stackOut)) {
            while (!empty($this->stackIn)) {
                $this->stackOut[] = array_pop($this->stackIn);
            }
        }
        return end($this->stackOut);
    }
}
Амортизированно каждый элемент перекладывается **ровно один раз**, поэтому O(1) на операцию.

Задача 2: K-й наибольший элемент (с Priority Queue)

function kthLargest(array $nums, int $k): int
{
    $heap = new SplMinHeap();
    foreach (array_slice($nums, 0, $k) as $num) {
        $heap->insert($num);
    }

    for ($i = $k; $i < count($nums); $i++) {
        if ($nums[$i] > $heap->top()) {
            $heap->extract();
            $heap->insert($nums[$i]);
        }
    }

    return $heap->top();
}
**Сложность:** O(n log k) — лучше чем сортировка O(n log n) при k << n.

Задача 3: BFS с очередью

function bfs(array $graph, int $start): array
{
    $visited = [$start => true];
    $queue = new SplQueue();
    $queue->enqueue($start);
    $order = [];

    while (!$queue->isEmpty()) {
        $node = $queue->dequeue();
        $order[] = $node;

        foreach ($graph[$node] as $neighbor) {
            if (!isset($visited[$neighbor])) {
                $visited[$neighbor] = true;
                $queue->enqueue($neighbor);
            }
        }
    }

    return $order;
}
## Где используется
Структура Применение
Queue BFS, планировщики задач, буферы
Deque Sliding window max/min, паттерны с двух сторон
Priority Queue (Heap) Dijkstra, k-й элемент, merge k sorted lists

Запомни: Очередь = FIFO. В PHP используй SplQueue, никогда array_shift(). Priority Queue (heap) — когда нужно быстро получать min/max. Очередь из двух стеков — классика интервью.

Итоги

  1. Queue = FIFO, все операции O(1)
  2. Deque = операции с обоих концов за O(1)
  3. Priority Queue = извлечение min/max за O(log n)
  4. В PHP: SplQueue для очереди, SplPriorityQueue/SplMinHeap для приоритетной
  5. BFS всегда использует очередь
  6. Очередь из двух стеков — амортизированно O(1)

Проверь себя

5 из 8

Какая сложность операции insert в SplPriorityQueue (приоритетная очередь на куче)?

Почему в Python не стоит реализовывать dequeue через `arr.pop(0)` и что использовать вместо этого?

Для поиска K-го наибольшего элемента в массиве из n чисел используется SplMinHeap размера k. Какова итоговая сложность?

В Go dequeue часто пишут как `s = s[1:]`. Формально это O(1), но в чём подвох?

Почему в PHP нельзя использовать `array_shift()` для реализации dequeue?

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

Монотонный стек

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

HashSet: уникальность и поиск

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

Обходы деревьев: BFS vs DFS

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