Как реализовать очередь в javascript за короткое время при кодировании во время интервью?

Question

Мне интересно, есть ли какой-нибудь встроенный модуль или пакет, который я мог бы использовать для реализации queue в javascript, когда я кодирую на leetcode.Как вы знаете, во время собеседования невозможно использовать много времени для создания очереди руками.Когда я использовал Python, я всегда хотел использовать модуль с именем collections, который включает в себя класс deque.Но после просмотра переполнения стека я обнаружил, что большинство ответов говорят людям, как реализовать очередь в javascript с нуля.Я ищу такой удобный способ его реализации.Может ли кто-нибудь помочь?

Хмммммм, кажется, нет лучшего способа реализации очереди, чем просто использование массивов.Кажется, он основан на самом движке javascript.Это ссылка об этом: временная сложность unshift () и push () в Javascript

Answer 1

A queue - это структура FIFO, где первый вставленный элемент в списке является первым, который будет удален.

В JavaScript вы можете легко использовать массивы для реализации этой логики.

Метод shift возвращает и удаляет первый элемент массива (как это делает dequeue), поэтому, если вы добавляете элементы, используя push, и удаляете элементы с shift, вы фактически используетеочередь.

Ниже приведен пример:

const a = [];
a.push(3);
a.push(5);
a.push(7);

console.log(a.shift());

Таким же образом вы можете иметь FIFO, даже используя unshift для добавления в начале массива и pop для удаления из конца массива.

Результатом всегда является структура FIFO, в которой первый добавленный элемент является первым, который должен быть удален:

const a = [];
a.unshift(3);
a.unshift(5);
a.unshift(7);

console.log(a.pop());

Хотя реализация стека в JavaScript может быть реализована в O (1) с простыми массивами, через push и pop, которые принимают O (1), очередьРеализация, как указано выше, должна принимать O (1) для вставки и O (n) в худшем случае для удаления.

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

class MyQueue extends Map {
  constructor() {
    super();
    this.insertionIndex = 0;
    this.removalIndex = 0;
  }

  queue(element) {
    this.set(this.insertionIndex, element);
    this.insertionIndex++;
  }

  dequeue() {
    const el = this.get(this.removalIndex);
    if (typeof el !== 'undefined') {
      this.delete(this.removalIndex);
      this.removalIndex++;
    }
    return el;
  }
}

const q = new MyQueue();
q.queue(1);
q.queue(2);
console.log(q.dequeue());
console.log(q.dequeue());
q.queue(3);
console.log(q.dequeue());
console.log(q.dequeue()); // now is empty so dequeue will return undefined with no errors
q.queue(4);
console.log(q.dequeue());