Как организовать очередь в JavaScript без использования структуры данных с O(1) shift, и стоит ли использовать Array.prototype.shift() при высокой нагрузке?

Проблема использования shift() для очереди

В JavaScript метод Array.prototype.shift() удаляет первый элемент массива и возвращает его. Однако после удаления все оставшиеся элементы сдвигаются на одну позицию влево, что требует O(n) операций. При большом количестве элементов и частых вызовах это приводит к значительному снижению производительности.

Эффективные реализации очереди

Для достижения O(1) при добавлении и удалении элементов можно использовать следующие подходы:

• Связный список — каждый элемент хранит ссылку на следующий, операции enqueue и dequeue выполняются за O(1).
• Объект с указателями — хранить элементы в объекте с ключами-индексами и двумя переменными head и tail.
• Кольцевой буфер — фиксированный массив с циклическими индексами.

Пример реализации с объектом

class Queue {
  constructor() {
    this.items = {};
    this.head = 0;
    this.tail = 0;
  }

  enqueue(element) {
    this.items[this.tail] = element;
    this.tail++;
  }

  dequeue() {
    if (this.isEmpty()) return undefined;
    const item = this.items[this.head];
    delete this.items[this.head];
    this.head++;
    return item;
  }

  isEmpty() {
    return this.head === this.tail;
  }
}

В этой реализации enqueue и dequeue выполняются за O(1), так как мы просто добавляем или удаляем свойство объекта по ключу.

Вывод

При высокой нагрузке и частых операциях с очередью не стоит использовать Array.prototype.shift(). Лучше применить специализированную структуру данных, например, реализацию на объекте или связном списке, чтобы обеспечить предсказуемую производительность O(1).