Detailed examples with pictures and texts to implement queues in JavaScript

Related recommendations: javascript tutorial

1. Queue data structure

• Queue is a type of "first in, first out" (FIFO) data structure. The first enqueued item (input) is the first dequeued (output).
• The queue has 2 pointers: head and tail. The oldest queued item in the queue is at the head, and the newest queued item is at the tail.
• The queue is like queuing in the subway. Passengers near the door are at the head of the queue, and passengers who have just entered the queue are at the back of the queue.

From a high-level perspective, a queue is a data structure that allows us to process each item of data in the order in which it is stored in the database.

2. Operations on the queue

The queue supports 2 main operations: enqueue and dequeue. Additionally, you may find it useful to perform peek and length operations on the queue.

• Enqueue operation <br/>Enqueue operation is to insert an item at the end of the queue, and the inserted item becomes the end of the queue.

The enqueue operation in the above figure inserts item 8 to the end, and 8 becomes the end of the queue.

queue.enqueue(8);

• Dequeue operation <br/> The dequeue operation is to extract the item at the beginning of the queue, and the next item in the queue becomes the head item.

In the picture above, the dequeue operation returns and removes the item 7 from the queue. After dequeuing, item 2 becomes the new head item.

queue.dequeue(); // => 7

• inspection operation <br/> The inspection operation reads the beginning of the queue without changing the queue.

Item 7 is the beginning of the queue in the picture above, and the inspection operation only returns header (item) 7 without modifying the queue.

queue.peek(); // => 7

• queue length The length operation calculates how many items the queue contains.

There are 4 items in the queue in the picture: 4, 6, 2, and 7. As a result, the queue length is 4.

queue.length; // => 4

• Queue Operation Time Complexity The important thing for all queue operations (enqueue, dequeue, view and length) is that all these operations must execute in fixed time O(1).

Constant time O(1) means that no matter the queue size (it can have 10 or 1 million items): enqueue, dequeue, peek and length operations must all be performed simultaneously.

3. Implementing Queues in JavaScript

Let’s look at a possible implementation of a queue data structure while maintaining the requirement that all operations must be performed in constant time O(1).

class Queue {
  constructor() {
    this.items = {};
    this.headIndex = 0;
    this.tailIndex = 0;
  }

  enqueue(item) {
    this.items[this.tailIndex] = item;
    this.tailIndex++;
  }

  dequeue() {
    const item = this.items[this.headIndex];
    delete this.items[this.headIndex];
    this.headIndex++;
    return item;
  }

  peek() {
    return this.items[this.headIndex];
  }

  get length() {
    return this.tailIndex - this.headIndex;
  }
}

const queue = new Queue();

queue.enqueue(7);
queue.enqueue(2);
queue.enqueue(6);
queue.enqueue(4);

queue.dequeue(); // => 7

queue.peek(); // => 2

queue.length; // => 3

const queue = new Queue() is how to create an instance of a queue.

Call the queue.enqueue(7) method to put item 7 into the queue.

queue.dequeue() removes a head item from the queue, while queue.peek() just peeks from the beginning.

Finally, queue.length shows how many items are left in the queue.

Regarding the implementation: Inside the Queue class, the plain object this.items holds the items in the queue by numerical index. The index of the head item is tracked by this.headIndex, and the index of the tail item is tracked by this.tailIndex.

• Complexity of queue methods

The methods queue(), dequeue(), peek() and length() of class Queue only use:

attribute access (such as this.items[this.headIndex]),

or perform arithmetic operations (such as this.headIndex++)

Therefore, the time complexity of these methods is constant time O(1).

4. Summary

The queue data structure is a type of "first in, first out" (FIFO): the earliest item to be enqueued is the earliest item to be dequeued.

Queues have 2 main operations: enqueue and dequeue. Additionally, queues can have auxiliary operations such as view and length.

All queue operations must perform O(1) in constant time.

Related recommendations: JavaScript learning tutorial.

The above is a detailed explanation of the implementation of queues in JavaScript with examples and pictures. For more information, please pay attention to other related articles on the PHP Chinese website!