Shulou(Shulou.com)05/31 Report--

This article introduces the knowledge of "how to implement a queue in JavaScript". Many people will encounter such a dilemma in the operation of actual cases, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

1. Queue data structure

If you like to travel, you must have gone through the procedure of ticket checking at the railway station. If there are a lot of people who want to take the train, it will naturally form a queue. People who have just entered the station join the queue. On the other side, the person who had just passed the check-in came out of the queue. This is an example of a queue that operates in the same way as the queue data structure.

A queue is a data structure that follows first-in, first-out (FIFO) rules. The first item in the queue (input) is the first out (output).

The queue has two pointers: the head and the end of the line. The first item to enter the queue is at the head of the queue, while the last item to enter the queue is at the end of the queue.

Looking back at the example of the station, the first person who checked in was the head of the queue. The person who has just entered the queue is at the end of the line.

Queue data structure

At a higher level, a queue is a data structure that allows you to process projects in order.

two。 Operation of the queue

The queue supports two main operations: enqueue and dequeue, as well as peek and length operations.

2.1 queuing operation

The queuing operation inserts an item at the end of the queue, making it the end of the queue.

Queue operation

The queuing operation in the image above inserts 8 at the end of the queue, and then 8 becomes the end of the queue.

Queue.enqueue (8); 2.2 out-of-line operation

The queuing operation takes out the first item in the queue, and the next item in the queue becomes the head of the queue.

Out of line operation

In the figure above, the dequeue operation returns item 7 and removes it from the queue. After leaving the team, item 2 became the new team leader.

Queue.dequeue (); / / = > 72.3 Peek operation

The Peek operation reads the items at the head of the queue, but does not change the queue.

Peek operation

7 in the picture above is the leader of the team. The peek operation only needs to return to the first 7 of the queue without modifying the queue.

Queue.peek (); / / = > 72.4 length

The length operation returns the number of items contained in the queue.

Length operation

There are four queues in the figure above: 4, 6, 2, and. seven. As a result, the queue length is 4.

Queue.length; / / = > time complexity of queue operations

Key points for all queue operations: enqueue,dequeue,peek and length must be performed with a constant time complexity of O (1).

The constant time complexity O (1) means that these operations must be performed in a relatively consistent time regardless of the queue size (whether there are 10 or 1 million items).

3. Implementing queues with JavaScript

Let's take a look at how to ensure that all operations must implement a queue data structure with a constant time complexity of 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 an instance of creating a queue.

The queue.enqueue (7) method stores 7 in a queue.

Queue.dequeue () fetches a header item from the queue, while queue.peek () reads only the first item of the team.

The final Queue.Length shows how many items are left in the queue.

About implementation: in the Queue class, the normal object this.Items holds the items of the queue through a numeric index. The index of the first item of the team is tracked by Where.HeadInex and the last item of the team is tracked by this.tailIndex.

Complexity of queuing method

Exists in the queue (), dequeue (), peek (), and length () methods of Queue:

Property accessors (such as: this.items [this.headIndex])

Perform arithmetic operations (e. G. this.headidex++)

The time complexity of these methods is a constant time O (1).

That's all for "how to implement a queue in JavaScript". Thank you for reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.