Очереди в TypeScript

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

В этом практическом руководстве мы расскажем, как реализовать очереди в TypeScript с помощью связанных списков.

Вот что мы рассмотрим:

• Предварительные условия
• Начало работы
• Что такое очереди?
• Что такое связные списки?
• Что такое простая очередь?
• Что такое кольцевая очередь?
• Что такое двухсторонняя очередь?
• Что такое приоритетная очередь?
• Когда следует использовать очереди (а когда не стоит)
• Заключение

Предварительные условия

1. TypeScript. Вы должны знать основы TypeScript (интерфейсы, типы и классы).
2. Основы алгоритмов. Вам необходимо иметь базовое представление о структурах данных и алгоритмах. Например, у вас не должно быть проблем с анализом временной и пространственной сложности с помощью нотации “O” большое.
3. Структура данных связный список. Прежде чем приступать к этому руководству, важно получить твердое представление о связных списках.

Начало работы

В этом руководстве мы будем работать с проектом-песочницей, который вы можете клонировать из репозитория GitHub.

Структура проекта выглядит следующим образом:

.
├── index.ts
├── examples
│   ├── 01-linked-list.ts
│   ├── 02-simple-queue.ts
│   ├── 03-circular-queue.ts
│   ├── 04-double-ended-queue.ts
│   └── 05-priority-queue.ts
└── playground
    ├── 01-linked-list.ts
    ├── 02-simple-queue.ts
    ├── 03-circular-queue.ts
    ├── 04-double-ended-queue.ts
    └── 05-priority-queue.ts

На протяжении всего руководства для реализации и тестирования кода мы будем использовать каталог playground.

Каталог examples содержит финальную версию каждой реализации. Если вы застрянете, то сможете обратиться к этим решениям!

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

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

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

В программировании очереди помогают управлять задачами, которые должны выполняться по порядку, например:

• Веб-сервер ставит в очередь входящие запросы, чтобы обрабатывать их по очереди.
• Приложение-чат ставит сообщения в очередь, чтобы отправлять их в том порядке, в котором они были набраны.
• Навигационное приложение ставит в очередь местоположения, чтобы изучать карту уровень за уровнем.

Есть четыре типа очередей:

1. Простая очередь. Элементы добавляются в заднюю часть и удаляются из передней в порядке FIFO.
2. Кольцевая (круговая, кольцевая) очередь (англ. Circular Queue). Аналогична простой очереди, за исключением того, что последний элемент соединен с первым.
3. Двухсторонняя очередь (англ. Double-Ended Queue, Deque). Позволяет добавлять или удалять элементы как спереди, так и сзади.
4. Приоритетная очередь (англ. Priority Queue). Обрабатывает элементы на основе приоритета, а не порядка поступления. Например, приложение для доставки обрабатывает VIP-заказы раньше обычных.

Каждая из этих очередей имеет свой набор операций для управления своими элементами. В этом руководстве мы рассмотрим следующие распространенные и широко используемые операции:

• enqueue. Добавляет элемент в конец очереди. Пример из жизни — новый покупатель становится в очередь в кассу за билетами.
• dequeue. Удаляет и возвращает элемент, находящийся в начале очереди.
• getFront. Просматривает элемент, находящийся спереди, не удаляя его. Пример из жизни — кассир смотрит, кто первый в очереди.
• getRear. Просматривает элемент, находящийся сзади, не удаляя его. Пример из жизни — кассир смотрит, кто последний в очереди.
• isEmpty. Проверяет отсутствие элементов в очереди.
• isFull. Проверяет, достигла ли очередь своего максимального размера.
• peek. Так же, как и getFront, просматривает передний элемент, не удаляя его, например, чтобы быстро взглянуть на первую задачу.
• size. Возвращает количество элементов в очереди. Пример из жизни — кассир подсчитывает, сколько людей в очереди.

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

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

Что такое связные списки?

Связный список — это метод хранения коллекции элементов, в котором каждый элемент, называемый «узлом», содержит две части: собственно данные и ссылку (или указатель) на следующий элемент в списке.

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

Связные списки используются для реализации очередей, поскольку они позволяют эффективно вставлять элементы в конец и удалять их из передней части, т.е. осуществлять две основные операции в очереди.

В очереди, основанной на связном списке, можно добавить новый узел в хвост и удалить его из головы списка за постоянное время (O(1)) без необходимости сдвигать элементы, как это делается в массиве.

В этом руководстве мы будем использовать особый тип связного списка — кольцевой двухсвязный список (англ. Circular Doubly Linked List).

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

Это означает, что вы можете перемещаться по списку в обоих направлениях и никогда не попадете в тупик. Это облегчает переход вперед или назад по узлам и помогает избежать особых случаев, таких как обработка null на концах.

В кольцевом двухсвязном списке все соединяется в цикл, что упрощает некоторые операции с очередями и делает их эффективными.

Кольцевой двухсвязный список уже добавлен в src/playground/01-linked-list.ts:

// 📁 src/playground/01-linked-list.ts

/**
 * Node for doubly linked list
 */
export class NodeItem<T> {
  value: T;
  next: NodeItem<T> | null = null;
  prev: NodeItem<T> | null = null;

  constructor(value: T) {
    this.value = value;
  }
}

/**
 * Circular Doubly Linked List
 */
export class LinkedList<T> {
  private head: NodeItem<T> | null = null;
  private tail: NodeItem<T> | null = null;
  private currentSize: number = 0;

  /**
   * Add a new node to the front of the list
   * @param value The value to add
   */
  prepend(value: T): void {
    const newNode = new NodeItem(value);
    if (this.isEmpty()) {
      this.head = newNode;
      this.tail = newNode;
      newNode.next = newNode;
      newNode.prev = newNode;
    } else {
      newNode.next = this.head;
      newNode.prev = this.tail;
      this.head!.prev = newNode;
      this.tail!.next = newNode;
      this.head = newNode;
    }
    this.currentSize++;
  }

  /**
   * Add a new node to the back of the list
   * @param value The value to add
   */
  append(value: T): void {
    const newNode = new NodeItem(value);
    if (this.isEmpty()) {
      this.head = newNode;
      this.tail = newNode;
      newNode.next = newNode;
      newNode.prev = newNode;
    } else {
      newNode.next = this.head;
      newNode.prev = this.tail;
      this.tail!.next = newNode;
      this.head!.prev = newNode;
      this.tail = newNode;
    }
    this.currentSize++;
  }

  /**
   * Remove and return the value from the front of the list
   * @returns The value at the head or undefined if empty
   */
  deleteHead(): T | undefined {
    if (this.isEmpty()) {
      return undefined;
    }
    const value = this.head!.value;
    if (this.currentSize === 1) {
      this.head = null;
      this.tail = null;
    } else {
      this.head = this.head!.next;
      this.head!.prev = this.tail;
      this.tail!.next = this.head;
    }
    this.currentSize--;
    return value;
  }

  /**
   * Remove and return the value from the back of the list
   * @returns The value at the tail or undefined if empty
   */
  deleteTail(): T | undefined {
    if (this.isEmpty()) {
      return undefined;
    }
    const value = this.tail!.value;
    if (this.currentSize === 1) {
      this.head = null;
      this.tail = null;
    } else {
      this.tail = this.tail!.prev;
      this.tail!.next = this.head;
      this.head!.prev = this.tail;
    }
    this.currentSize--;
    return value;
  }

  /**
   * Get the value at the front without removing it
   * @returns The value at the head or undefined if empty
   */
  getHead(): T | undefined {
    return this.head?.value;
  }

  /**
   * Get the value at the back without removing it
   * @returns The value at the tail or undefined if empty
   */
  getTail(): T | undefined {
    return this.tail?.value;
  }

  /**
   * Check if the list is empty
   * @returns True if the list is empty, false otherwise
   */
  isEmpty(): boolean {
    return this.currentSize === 0;
  }

  /**
   * Get the current size of the list
   * @returns The number of nodes in the list
   */
  size(): number {
    return this.currentSize;
  }
}

В этом модуле у вас есть кольцевой двухсвязный список с 8 различными методами, которые в дальнейшем облегчат построение очередей:

• prepend. Добавляет новое значение в начало списка.
• append. Добавляет новое значение в конец списка.
• deleteHead. Удаляет и возвращает значение в начале списка.
• deleteTail. Удаляет и возвращает значение в конце списка.
• getHead. Возвращает переднее значение без его удаления.
• getTail. Возвращает конечное значение без его удаления.
• isEmpty. Проверяет отсутствие элементов в списке.
• size. Возвращает количество элементов в списке.

Теперь, когда наш связный список готов, давайте начнем создавать нашу первую очередь!

Что такое простая очередь?

Простая очередь подчиняется основному правилу FIFO: вы должны добавлять элементы в конец очереди и удалять их спереди.

Это похоже на очередь покупателей в билетной кассе, где первый человек в очереди покупает билет первым.

Чтобы начать работу, откройте файл src/playground/02-simple-queue.ts, в котором вы найдете плейсхолдер для простой очереди с ее методами:

// 📁 src/playground/02-simple-queue.ts

import { LinkedList } from "./01-linked-list";

/**
 * Simple Queue implemented with a circular doubly linked list
 */
export class SimpleQueue<T> {
  private list: LinkedList<T>;
  private maxSize?: number;

  /**
   * @param maxSize Optional maximum size of the queue
   */
  constructor(maxSize?: number) {
    this.list = new LinkedList<T>();
    this.maxSize = maxSize;
  }

  ...methods
}

В основе класса SimpleQueue лежит использование кольцевого двусвязного списка для хранения элементов, а также опциональное ограничение максимального размера для контроля величины очереди.

• private list: LinkedList<T> — это место, где хранятся данные очереди. Вместо простого массива мы используем пользовательский связный список, что позволяет эффективно добавлять и удалять элементы с любого конца. Связный список управляет структурой данных и позволяет сосредоточиться на работе очереди.
• private maxSize — необязательное ограничение на количество элементов в очереди. Если его не указать, очередь может расти настолько, насколько это необходимо.
• Метод constructor запускается при создании новой очереди. Он создает новый пустой связный список для хранения элементов очереди.

Теперь давайте реализуем методы очереди.

Откройте редактор кода и обновите файл src/playground/02-simple-queue.ts следующим кодом:

// 📁 src/playground/02-simple-queue.ts

import { LinkedList } from "./01-linked-list";

/**
 * Simple Queue implemented with a circular doubly linked list
 */
export class SimpleQueue<T> {
  private list: LinkedList<T>;
  private maxSize?: number;

  /**
   * @param maxSize Optional maximum size of the queue
   */
  constructor(maxSize?: number) {
    this.list = new LinkedList<T>();
    this.maxSize = maxSize;
  }

  /**
   * Add an element to the rear of the queue
   * @param item The element to add
   */
  enqueue(item: T): void {
    if (this.isFull()) {
      throw new Error("Queue is full");
    }
    this.list.append(item);
  }

  /**
   * Remove and return the element from the front of the queue
   * @returns The element at the front or undefined if empty
   */
  dequeue(): T | undefined {
    return this.list.deleteHead();
  }

  /**
   * Get the element at the front without removing it
   * @returns The element at the front or undefined if empty
   */
  getFront(): T | undefined {
    return this.list.getHead();
  }

  /**
   * Get the element at the rear without removing it
   * @returns The element at the rear or undefined if empty
   */
  getRear(): T | undefined {
    return this.list.getTail();
  }

  /**
   * Check if the queue is empty
   * @returns True if the queue is empty, false otherwise
   */
  isEmpty(): boolean {
    return this.list.isEmpty();
  }

  /**
   * Check if the queue is full
   * @returns True if the queue is full, false otherwise
   */
  isFull(): boolean {
    return this.maxSize !== undefined && this.list.size() >= this.maxSize;
  }

  /**
   * Peek at the front element without removing it
   * @returns The element at the front or undefined if empty
   */
  peek(): T | undefined {
    return this.getFront();
  }

  /**
   * Get the current size of the queue
   * @returns The number of elements in the queue
   */
  size(): number {
    return this.list.size();
  }
}

Как видите, связный список значительно упрощает реализацию очереди, потому что он выступает в качестве движка очереди.

Вот как работает наша простая очередь:

• isEmpty(). Этот метод проверяет отсутствие элементов в очереди. Он вызывает метод isEmpty() связного списка, который проверяет, равен ли текущий размер списка нулю. Если в списке нет узлов, метод возвращает true, указывая на то, что очередь пуста. Это базовый вспомогательный метод, часто используемый перед попыткой очистки или проверки очереди.
• isFull(). Этот метод определяет, достигла ли очередь своей вместимости. Он сравнивает текущий размер связного списка (с помощью метода size()) с необязательным значением maxSize. Если maxSize определен, а размер связного списка равен ему или превышает его, возвращается true. Это означает, что уже нельзя добавлять новые элементы. Такое ограничение полезно для предотвращения переполнения в ограниченных очередях.
• size(). Этот метод возвращает количество элементов, хранящихся в очереди в данный момент. Он напрямую вызывает метод size() связного списка, который отслеживает количество узлов. Это позволяет отслеживать использование очереди и ее оставшуюся емкость.
• enqueue(). Этот метод добавляет новый элемент в конец очереди. Сначала он проверяет, заполнена ли очередь, вызывая метод isFull(). Если да, то метод выбрасывает ошибку. В противном случае он добавляет новый элемент во внутренний связный список с помощью метода append(), который добавляет новый узел в хвост кольцевого двухсвязного списка.
• dequeue(). Этот метод удаляет и возвращает элемент, находящийся в начале очереди. Он вызывает метод deleteHead() связного списка, который удаляет головной узел и обновляет связи окружающих узлов, чтобы сохранить кольцевую структуру. Если очередь пуста, возвращается значение undefined.
• getFront(). Этот метод возвращает значение, находящееся в начале очереди, не удаляя его. Он использует метод getHead() связного списка для получения значения головного узла. Эта операция не изменяет очередь и полезна для предварительного просмотра следующего элемента, который будет удален из очереди.
• getRear(). Этот метод возвращает значение в конце очереди, не удаляя его. Он использует метод getTail() связного списка, который возвращает значение хвостового узла. Это позволяет проверить последний добавленный элемент, не изменяя очередь.
• peek(). Этот метод является псевдонимом для getFront(). Он возвращает элемент, находящийся в начале очереди, не удаляя его. Под капотом он вызывает getFront(), чтобы получить значение head. Это часто используется в API очередей для проверки следующего элемента в очереди.

Вы только что реализовали свою первую очередь на TypeScript. Чтобы убедиться, что наша реализация работает правильно, выполните следующую команду в терминале в корне проекта:

npm run test:file 02

Если какой-либо из тестов не прошел, используйте последний пример из src/examples/02-simple-queue.ts для отладки проблемы, а затем запустите тесты снова.

Если все тесты пройдены, вы можете перейти к следующему разделу, где мы реализуем кольцевую очередь.

Что такое кольцевая очередь?

CircularQueue — это очередь фиксированного размера, в которой последняя позиция соединяется с первой. Это позволяет повторно использовать пространство после удаления элементов.

Представьте себе очередь к шведскому столу с ограниченным количеством тарелок: когда кто-то берет тарелку спереди, новая добавляется сзади, снова используя то же пространство.

CircularQueue очень похожа на SimpleQueue, но имеет несколько уникальных отличий.

Давайте изменим src/playground/03-circular-queue.ts и добавим следующий код:

// 📁 src/playground/03-circular-queue.ts

import { LinkedList } from "./01-linked-list";

/**
 * Circular Queue implemented with a circular doubly linked list
 */
export class CircularQueue<T> {
  private list: LinkedList<T>;
  private maxSize: number;

  /**
   * @param maxSize Required maximum size of the circular queue
   */
  constructor(maxSize: number) {
    this.list = new LinkedList<T>();
    this.maxSize = maxSize;
  }

  /**
   * Add an element to the rear of the queue
   * @param item The element to add
   */
  enqueue(item: T): void {
    if (this.isFull()) {
      throw new Error("Circular queue is full");
    }
    this.list.append(item);
  }

  /**
   * Remove and return the element from the front of the queue
   * @returns The element at the front or undefined if empty
   */
  dequeue(): T | undefined {
    return this.list.deleteHead();
  }

  /**
   * Get the element at the front without removing it
   * @returns The element at the front or undefined if empty
   */
  getFront(): T | undefined {
    return this.list.getHead();
  }

  /**
   * Get the element at the rear without removing it
   * @returns The element at the rear or undefined if empty
   */
  getRear(): T | undefined {
    return this.list.getTail();
  }

  /**
   * Check if the queue is empty
   * @returns True if the queue is empty, false otherwise
   */
  isEmpty(): boolean {
    return this.list.isEmpty();
  }

  /**
   * Check if the queue is full
   * @returns True if the queue is full, false otherwise
   */
  isFull(): boolean {
    return this.list.size() >= this.maxSize;
  }

  /**
   * Peek at the front element without removing it
   * @returns The element at the front or undefined if empty
   */
  peek(): T | undefined {
    return this.getFront();
  }

  /**
   * Get the current size of the queue
   * @returns The number of elements in the queue
   */
  size(): number {
    return this.list.size();
  }
}

Может показаться, что это очень похоже на SimpleQueue, но есть несколько ключевых отличий:

• Разница в конструкторе. В отличие от SimpleQueue, CircularQueue требует параметр maxSize при инстанцировании. Это устанавливает строгий верхний предел того, сколько элементов может находиться в очереди одновременно.
  SimpleQueue допускает неограниченные очереди, поэтому maxSize там — опциональный параметр. Благодаря обязательному указанию maxSize CircularQueue лучше подходит для сценариев с буфером фиксированного размера, где важен контроль памяти или ресурсов (например, в системах реального времени или кэшировании).
• enqueue(). Этот метод почти идентичен такому же методу в SimpleQueue. В CircularQueue выброс ошибки при переполнении очереди является частью контракта, и это предполагает, что вы управляете фиксированным буфером.
  Кольцевая природа вступает в игру концептуально: когда очередь заполнена, в нее больше не могут попасть данные, пока не будут удалены старые записи, что имитирует механизм кольцевой перезаписи (хотя в данной конкретной реализации автозапись не происходит).
• isFull(). Этот метод ведет себя так же, как и в SimpleQueue, когда там задан maxSize. В CircularQueue размер ограничивается всегда, что делает очередь предсказуемой и идеально подходящей для таких случаев использования, как потоковые данные и обработка с ограниченной скоростью.

Теперь давайте протестируем реализацию, чтобы проверить, работает ли она:

npm run test:file 03

Если какой-либо из тестов не сработал, используйте каталог final /examples для отладки проблемы.

Если тесты пройдут, вы будете готовы перейти к следующему разделу, где узнаете о двухсторонних очередях.

Что такое двухсторонняя очередь?

Двухсторонняя очередь (deque) позволяет добавлять или удалять элементы как спереди, так и сзади.

Давайте изменим src/playground/04-double-ended-queue.ts и добавим следующий код:

// 📁 src/playground/04-double-ended-queue.ts

import { LinkedList } from "./01-linked-list";

/**
 * Double-Ended Queue (Deque) implemented with a circular doubly linked list
 */
export class Deque<T> {
  private list: LinkedList<T>;
  private maxSize?: number;

  /**
   * @param maxSize Optional maximum size of the deque
   */
  constructor(maxSize?: number) {
    this.list = new LinkedList<T>();
    this.maxSize = maxSize;
  }

  /**
   * Add an element to the front of the deque
   * @param item The element to add
   */
  enqueueFront(item: T): void {
    if (this.isFull()) {
      throw new Error("Deque is full");
    }
    this.list.prepend(item);
  }

  /**
   * Add an element to the rear of the deque
   * @param item The element to add
   */
  enqueueRear(item: T): void {
    if (this.isFull()) {
      throw new Error("Deque is full");
    }
    this.list.append(item);
  }

  /**
   * Remove and return the element from the front of the deque
   * @returns The element at the front or undefined if empty
   */
  dequeueFront(): T | undefined {
    return this.list.deleteHead();
  }

  /**
   * Remove and return the element from the rear of the deque
   * @returns The element at the rear or undefined if empty
   */
  dequeueRear(): T | undefined {
    return this.list.deleteTail();
  }

  /**
   * Get the element at the front without removing it
   * @returns The element at the front or undefined if empty
   */
  getFront(): T | undefined {
    return this.list.getHead();
  }

  /**
   * Get the element at the rear without removing it
   * @returns The element at the rear or undefined if empty
   */
  getRear(): T | undefined {
    return this.list.getTail();
  }

  /**
   * Check if the deque is empty
   * @returns True if the deque is empty, false otherwise
   */
  isEmpty(): boolean {
    return this.list.isEmpty();
  }

  /**
   * Check if the deque is full
   * @returns True if the deque is full, false otherwise
   */
  isFull(): boolean {
    return this.maxSize !== undefined && this.list.size() >= this.maxSize;
  }

  /**
   * Peek at the front element without removing it
   * @returns The element at the front or undefined if empty
   */
  peek(): T | undefined {
    return this.getFront();
  }

  /**
   * Get the current size of the deque
   * @returns The number of elements in the deque
   */
  size(): number {
    return this.list.size();
  }
}

Теперь давайте пройдемся по методам:

• enqueueFront(). Этот метод позволяет добавить элемент в переднюю часть deque, в отличие от SimpleQueue и CircularQueue, которые поддерживают добавление только в заднюю часть. Для вставки элемента в начало используется list.prepend(item).
  Эта операция делает двухстороннюю очередь подходящей для случаев, когда элементы нужно выгружать с обоих концов, как в системах отмены/повтора или в планировщиках задач.
• enqueueRear(). Ведет себя аналогично enqueue() в SimpleQueue: добавляет элементы в заднюю часть с помощью list.append(item). Отличие Deque в том, что здесь это одна из двух симметричных операций.
• dequeueFront(). Удаляет и возвращает элемент из передней части очереди, используя list.deleteHead(). Хотя этот метод похож на метод dequeue() в очередях, его имя явно указывает на то, что он работает с передней частью.
• dequeueRear(). Эта функция уникальна для двухсторонних очередей, она удаляет и возвращает элемент в задней части очереди с помощью list.deleteTail(). Эта функция дополняет dequeueFront() и позволяет при необходимости использовать стекоподобное поведение (LIFO, от Last In, First Out — “последний пришел, первый ушел”).
• Разница в конструкторе. Как и SimpleQueue, Deque принимает опциональное значение maxSize. Это позволяет создавать гибкие конфигурации. Ваши двухсторонние очереди могут быть неограниченными, когда maxSize не указан, или иметь фиксированный размер, когда ограничения важны. Это контрастирует с CircularQueue, которая требует указания максимального размера.

После завершения реализации выполните следующую команду, чтобы протестировать модуль:

npm run test:file 04

Теперь вы готовы перейти к последнему разделу руководства, в котором вы узнаете о приоритетной очереди.

Что такое приоритетная очередь?

Приоритетная очередь обрабатывает элементы на основе их приоритета, а не порядка поступления.

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

Давайте изменим src/playground/05-priority-queue.ts:

// 📁 src/playground/05-priority-queue.ts

import { LinkedList, NodeItem } from "./01-linked-list";

/**
 * Interface for an element with priority
 */
interface PriorityItem<T> {
  value: T;
  priority: number;
}

/**
 * Priority Queue implemented with a circular doubly linked list
 */
export class PriorityQueue<T> {
  private list: LinkedList<PriorityItem<T>>;
  private maxSize?: number;

  /**
   * @param maxSize Optional maximum size of the priority queue
   */
  constructor(maxSize?: number) {
    this.list = new LinkedList<PriorityItem<T>>();
    this.maxSize = maxSize;
  }

  /**
   * Add an element to the queue based on its priority
   * Higher priority numbers are dequeued first
   * @param value The value to add
   * @param priority The priority of the value (higher number = higher priority)
   */
  enqueue(value: T, priority: number): void {
    if (this.isFull()) {
      throw new Error("Priority queue is full");
    }

    const newItem: PriorityItem<T> = { value, priority };
    if (this.isEmpty()) {
      this.list.prepend(newItem);
      return;
    }

    let current = this.list["head"];
    let count = 0;
    while (
      current &&
      current.value.priority >= priority &&
      count < this.size()
    ) {
      current = current.next;
      count++;
    }

    if (count === this.size()) {
      this.list.append(newItem);
    } else {
      const newNode = new NodeItem(newItem);
      newNode.next = current;
      newNode.prev = current!.prev;
      if (current!.prev) {
        current!.prev.next = newNode;
      } else {
        this.list["head"] = newNode;
      }
      current!.prev = newNode;
      if (current === this.list["head"]) {
        this.list["head"] = newNode;
      }
      this.list["tail"]!.next = this.list["head"];
      this.list["head"]!.prev = this.list["tail"];
      this.list["currentSize"]++;
    }
  }

  /**
   * Remove and return the element with the highest priority from the queue
   * @returns The value with the highest priority or undefined if empty
   */
  dequeue(): T | undefined {
    return this.list.deleteHead()?.value;
  }

  /**
   * Get the element with the highest priority without removing it
   * @returns The value at the front or undefined if empty
   */
  getFront(): T | undefined {
    return this.list.getHead()?.value;
  }

  /**
   * Get the element with the lowest priority without removing it
   * @returns The value at the rear or undefined if empty
   */
  getRear(): T | undefined {
    return this.list.getTail()?.value;
  }

  /**
   * Check if the queue is empty
   * @returns True if the queue is empty, false otherwise
   */
  isEmpty(): boolean {
    return this.list.isEmpty();
  }

  /**
   * Check if the queue is full
   * @returns True if the queue is full, false otherwise
   */
  isFull(): boolean {
    return this.maxSize !== undefined && this.list.size() >= this.maxSize;
  }

  /**
   * Peek at the element with the highest priority without removing it
   * @returns The value at the front or undefined if empty
   */
  peek(): T | undefined {
    return this.getFront();
  }

  /**
   * Get the current size of the queue
   * @returns The number of elements in the queue
   */
  size(): number {
    return this.list.size();
  }
}

А теперь давайте разберемся, как работают методы в приоритетной очереди:

• enqueue(). Этот метод вставляет новый элемент в очередь, основываясь на его приоритете. В отличие от других типов очередей, где порядок основан на времени вставки, PriorityQueue использует механизм сортировки, где элементы с более высоким приоритетом располагаются ближе к началу.
  Метод обходит связный список от головы, отыскивая нужную позицию, куда следует вставить новый элемент, чтобы список оставался отсортированным в порядке убывания приоритета. Он вручную корректирует указатели prev и next, чтобы сохранить целостность кольцевого двусвязного списка. Такая сортировка во время вставки обеспечивает быстрый доступ к элементу с наивысшим приоритетом в дальнейшем.
• dequeue(). Этот метод удаляет и возвращает элемент с наивысшим приоритетом, который всегда располагается в начале списка. Под капотом он вызывает deleteHead(), а затем возвращает значение из узла PriorityItem<T>. Поскольку элементы сортируются при вставке, эта операция всегда эффективна и возвращает нужный элемент.
• getFront(). Эта операция извлекает значение, находящееся в начале очереди, не удаляя его. Поскольку список отсортирован по убыванию приоритета, это значение всегда представляет элемент с наивысшим приоритетом.
• getRear(). Возвращает значение, находящееся в конце очереди, то есть элемент с наименьшим приоритетом. Метод получает доступ к последнему элементу списка с помощью getTail() и извлекает значение.
• isEmpty(). Проверяет, содержит ли очередь какие-либо элементы, используя метод isEmpty() связного списка.
• isFull(). Проверяет, достигла ли очередь своего максимально допустимого размера. Метод сравнивает текущий размер с maxSize, если он определен.
• peek(). Этот метод функционально эквивалентен getFront(). Он предоставляет более понятное семантическое название, когда пользователи хотят просмотреть самый приоритетный элемент, не удаляя его.
• size(). Возвращает общее количество элементов, находящихся в приоритетной очереди. Это полезно для мониторинга пропускной способности или отладки.

Ключевые отличия

Приоритетная очередь отличается от других типов очередей тем, что обеспечивает порядок при вставке на основе числового приоритета. Благодаря этому доступ к элементу с наивысшим приоритетом будет иметь постоянную временную сложность, а вставка элемента — линейную (поскольку для каждого нового элемента нужно искать подходящее место).

Это поддерживает расширенное планирование и балансировку нагрузки в тех случаях, когда срочность или важность задачи имеет большее значение, чем время ее поступления.

Покончив с реализацией, выполните следующую команду, чтобы протестировать наш код:

npm run test:file 05

Вот и все, поздравляем!

Вы успешно прошли это руководство и познакомились с очередями и их вариациями. Отличная работа!

Теперь давайте вкратце разберем, где стоит использовать очереди, а где их лучше избегать. Мы также обсудим узкие места и проблемы, которые очереди могут создать, если их использовать неправильно и не в том месте.

Когда следует использовать очереди (а когда не стоит)

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

Например, когда на принтер отправляется несколько заданий, очередь может обеспечить печать всех документов в том порядке, в котором они были отправлены.

Аналогично очереди используются в операционных системах для управления заданиями в пулах потоков или при планировании работы процессора (например, Round Robin), где порядок имеет решающее значение.

Очереди также широко используются в системах асинхронных коммуникаций, таких как брокеры сообщений RabbitMQ и Kafka.

В таких системах производители и потребители работают независимо друг от друга: производитель отправляет сообщения в очередь, а потребитель обрабатывает их позже.

Этот паттерн чрезвычайно полезен в архитектуре микросервисов или бессерверных средах, где различные части системы должны оставаться слабосвязанными и хорошо масштабируемыми.

Аналогичным образом, в системах реального времени, таких как потоковое видео или сбор данных с датчиков, очереди помогают буферизировать входящие данные, чтобы избежать их потери и обеспечить плавную последующую обработку.

Когда следует избегать очередей

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

Поскольку очереди обычно позволяют вставлять данные с одного конца и удалять с другого, они неэффективны для случаев, когда вам часто требуется доступ к элементам в середине или поиск по всем элементам. В таких случаях лучше использовать массив, дерево или хэш-карту.

Неправильное использование очередей может привести к излишней сложности и скрытым узким местам. Например, необдуманное размещение очередей между микросервисами может развязать компоненты, но при этом усложнить отладку и устранение сбоев.

Избыточное использование очередей также может привести к проблемам обратного давления, когда очереди неконтролируемо растут под высокой нагрузкой, что увеличивает задержки или даже приводит к краху системы, если не управлять ими должным образом.

Поэтому очереди следует использовать осознанно: когда требуется порядок, буферизация или асинхронная обработка.

Заключение

Очереди в TypeScript — это базовая структура данных, которая хорошо работает, когда вам нужен порядок и асинхронная обработка.

Очереди полезны для обработки задач, стриминга данных или координации сервисов, а также для обеспечения бесперебойной и эффективной работы.

Но они подходят не для всех задач. Важно понимать их плюсы и минусы, чтобы использовать их правильно и избежать ненужных сложностей.

Перевод статьи “How to Work with Queues in TypeScript”.