По какому принципу работает очередь как структура данных

Принцип работы очереди как структуры данных

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

Ключевые операции и их принципы

Основные операции, обеспечивающие функционирование очереди:

• Enqueue (постановка в очередь): Добавление нового элемента в конец (tail/rear) очереди.
• Dequeue (удаление из очереди): Извлечение и удаление элемента из начала (head/front) очереди.
• Peek/Front (просмотр): Получение значения элемента в начале очереди без его удаления.
• isEmpty (проверка на пустоту): Проверка, содержит ли очередь элементы.
• isFull (проверка на заполненность): Актуально для реализации на массиве фиксированного размера.

Внутреннее устройство и реализации

Принцип FIFO может быть реализован различными способами, что влияет на производительность операций.

1. Реализация на массиве (кольцевой буфер) Используется массив фиксированного размера и два указателя (индекса): front (начало) и rear (конец). При достижении конца массива указатели «закольцовываются» на начало, если там есть свободное место.

class Queue {
  constructor(capacity) {
    this.items = new Array(capacity);
    this.front = 0;
    this.rear = -1;
    this.size = 0;
    this.capacity = capacity;
  }

  enqueue(item) {
    if (this.isFull()) {
      throw new Error('Queue is full');
    }
    this.rear = (this.rear + 1) % this.capacity; // Кольцевое движение
    this.items[this.rear] = item;
    this.size++;
  }

  dequeue() {
    if (this.isEmpty()) {
      throw new Error('Queue is empty');
    }
    const item = this.items[this.front];
    this.front = (this.front + 1) % this.capacity; // Кольцевое движение
    this.size--;
    return item;
  }

  peek() {
    if (this.isEmpty()) {
      return null;
    }
    return this.items[this.front];
  }

  isEmpty() {
    return this.size === 0;
  }

  isFull() {
    return this.size === this.capacity;
  }
}

Принцип: Эффективность O(1) для основных операций, но требуется управление указателями и есть ограничение по размеру.

2. Реализация на связном списке Более гибкая реализация, использующая узлы (Node). Указатель head указывает на первый узел, tail — на последний.

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class LinkedListQueue {
  constructor() {
    this.head = null; // Начало очереди
    this.tail = null; // Конец очереди
    this.length = 0;
  }

  enqueue(value) {
    const newNode = new Node(value);
    if (this.isEmpty()) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode; // Присоединяем новый узел в конец
      this.tail = newNode;      // Обновляем указатель на хвост
    }
    this.length++;
  }

  dequeue() {
    if (this.isEmpty()) {
      return null;
    }
    const removedNode = this.head;
    this.head = this.head.next; // Сдвигаем начало на следующий узел
    if (this.head === null) {   // Если очередь опустела
      this.tail = null;
    }
    this.length--;
    return removedNode.value;
  }

  peek() {
    return this.head ? this.head.value : null;
  }

  isEmpty() {
    return this.length === 0;
  }
}

Принцип: Динамическое изменение размера, каждая операция enqueue/dequeue работает за O(1), так как добавление/удаление происходит с разных концов списка.

Вариации очередей

Принцип FIFO модифицируется для решения специфических задач:

• Двусторонняя очередь (Deque) — позволяет добавлять и удалять элементы как с начала, так и с конца, объединяя принципы стека и очереди.
• Циклическая очередь (Circular Queue) — использует кольцевой буфер для эффективного переиспользования памяти.
• Очередь с приоритетом (Priority Queue) — нарушает принцип строгого FIFO. Элементы добавляются согласно их приоритету (часто реализуется через кучу). Извлекается всегда элемент с наивысшим приоритетом.

Принцип работы в контексте Event Loop

В веб-разработке принцип очереди фундаментален для Event Loop в JavaScript. Асинхронные операции (колбэки из setTimeout, промисы, события) помещаются в очередь задач (Task Queue) или очередь микрозадач (Microtask Queue). Event Loop непрерывно проверяет стек вызовов (Call Stack) и, когда он пуст, извлекает (dequeue) первую задачу из очереди и помещает её в стек на выполнение, строго соблюдая FIFO в пределах своих типов очередей.

console.log('1'); // Синхронная операция

setTimeout(() => console.log('2'), 0); // Макрозадача -> Task Queue

Promise.resolve().then(() => console.log('3')); // Микрозадача -> Microtask Queue

console.log('4'); // Синхронная операция
// Вывод: 1, 4, 3, 2
// Принцип: Синхронный код выполняется первым, затем Event Loop DEQUEUE микрозадачи из Microtask Queue, и только затем — макрозадачи из Task Queue.

Таким образом, принцип работы очереди — это не только абстрактная концепция структур данных, но и краеугольный камень управления асинхронностью, планирования задач и организации данных в бесчисленных областях программирования.