Detailed examples with pictures and texts to implement queues in JavaScript

This article brings you relevant knowledge about javascript, which mainly introduces issues related to the implementation of queues in JavaScript, describes the queue data structure, its operations and shows the queue implementation in JavaScript ,I hope everyone has to help.

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 rear of the queue.

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

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
  The 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 tail, and 8 becomes the tail of the queue.

queue.enqueue(8);

• Dequeue operation
  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 above figure, 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
  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
  Importantly for all queue operations (enqueue, dequeue, view and length), all these operations must be executed in a fixed time O (1).

Constant time O(1) means that regardless of 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() takes out a head item from the queue, while queue.peek() just checks it again.

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

About implementation: Inside the Queue class, the ordinary 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 are only used Error:

属性访问（例如this.items[this.headIndex]），

或执行算术操作（例如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 that is enqueued is the earliest item that is dequeued.

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

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

Related recommendations: javascript learning tutorial

The above is the detailed content of Detailed examples with pictures and texts to implement queues in JavaScript. For more information, please follow other related articles on the PHP Chinese website!