Очередь JavaScript

Краткое описание: в этом уроке вы узнаете о структуре данных очереди и о том, как реализовать очередь в JavaScript.

Введение в структуру данных очереди

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

Очередь работает по принципу «первым пришел — первым ушел» (FIFO), что отличается от стека, который работает по принципу «последним пришел — первым ушел» (LIFO).

Очередь состоит из двух основных операций:

• Вставить новый элемент в конец очереди, что называется enqueue.
• Удалить элемент из передней части очереди, что называется dequeue.

На следующем рисунке показана очередь:

Другой важной операцией очереди является получение элемента, находящегося впереди, называемое peek. В отличие от операции dequeue, операция peek возвращает элемент, находящийся впереди, не изменяя очередь.

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

Реализация очереди в JavaScript с использованием объекта

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

class Queue {
  constructor() {
    this.elements = {};
    this.head = 0;
    this.tail = 0;
  }
  enqueue(element) {
    this.elements[this.tail] = element;
    this.tail++;
  }
  dequeue() {
    const item = this.elements[this.head];
    delete this.elements[this.head];
    this.head++;
    return item;
  }
  peek() {
    return this.elements[this.head];
  }
  get length() {
    return this.tail - this.head;
  }
  get isEmpty() {
    return this.length === 0;
  }
}
Code language: JavaScript (javascript)

Как это работает.

Во-первых, инициализируйте объект, хранящий элементы очереди (elements) и две переменные для отслеживания головы и хвоста в конструкторе:

class Queue {
  constructor() {
    this.elements = {};
    this.head = 0;
    this.tail = 0;
  }
  //...
}
Code language: JavaScript (javascript)

Во-вторых, занести элемент в очередь, добавив его в объект elements в конец очереди:

class Queue {
  //...
  enqueue(element) {
    this.elements[this.tail] = element;
    this.tail++;
  }

  //...
}
Code language: JavaScript (javascript)

В-третьих, удалить элемент из передней части очереди:

class Queue {

  // ...
  dequeue() {
    const item = this.elements[this.head];
    delete this.elements[this.head];
    this.head++;
    return item;
  }

  //...
}
Code language: JavaScript (javascript)

В-четвертых, определить метод peek(), который обращается к элементу, находящемуся в начале очереди:

class Queue {
  //...
  peek() {
    return this.elements[this.head];
  }
  //...  
}
Code language: JavaScript (javascript)

В-пятых, получить длину очереди:

class Queue {
  //...
  get length() {
    return this.tail - this.head;
  }
  //...
}
Code language: JavaScript (javascript)

Очередь пуста, если ее длина равна нулю.

Наконец, определите метод isEmpty(), который возвращает true, если очередь пуста:

class Queue {
  // ...
  get isEmpty() {
    return this.tail - this.head;
  }
  // ... 
}
Code language: JavaScript (javascript)

Чтобы создать новую очередь из функции конструктора Queue(), вы используете ключевое слово new следующим образом:

let q = new Queue();
Code language: JavaScript (javascript)

Чтобы поставить в очередь числа от 1 до 7, вы используете следующий код.

for (let i = 1; i <= 7; i++) {
    q.enqueue(i);
}
Code language: JavaScript (javascript)

Для получения номера, находящегося в начале очереди, используется метод peek().

console.log(q.peek()); // 1
Code language: JavaScript (javascript)

Для получения текущей длины очереди используется метод length(), как в следующем примере.

console.log(q.length); // 7
Code language: JavaScript (javascript)

Для удаления элемента, находящегося в начале очереди, используется метод dequeue(), как показано в следующем примере:

// dequeue all elements
while (!q.isEmpty()) {
    console.log(q.dequeue());
}
Code language: JavaScript (javascript)

Соберите все вместе:

class Queue {
  constructor() {
    this.elements = {};
    this.head = 0;
    this.tail = 0;
  }
  enqueue(element) {
    this.elements[this.tail] = element;
    this.tail++;
  }
  dequeue() {
    const item = this.elements[this.head];
    delete this.elements[this.head];
    this.head++;
    return item;
  }
  peek() {
    return this.elements[this.head];
  }
  get length() {
    return this.tail - this.head;
  }
  get isEmpty() {
    return this.length === 0;
  }
}

let q = new Queue();
for (let i = 1; i <= 7; i++) {
  q.enqueue(i);
}
// get the current item at the front of the queue
console.log(q.peek()); // 1

// get the current length of queue
console.log(q.length); // 7

// dequeue all elements
while (!q.isEmpty) {
  console.log(q.dequeue());
}
Code language: JavaScript (javascript)

Резюме

• Очередь — это структура данных, работающая по принципу FIFO.