Shulou(Shulou.com)06/01 Report--

This article will explain in detail how to implement queues in JavaScript. The editor thinks it is very practical, so I share it for you as a reference. I hope you can get something after reading this article.

1. Queue data structure

Queues are a type of first-in first-out (FIFO) data structure. The first entry (input) is the first out (output).

The queue has two pointers: head and tail. The earliest queued item in the queue is at the header, while the newest queued item is at the end of the queue.

The queue is like us standing in line on the subway, with the passengers near the door at the head of the queue and the passengers who have just entered the queue at the back of the queue.

From a higher point of view, a queue is a data structure that allows us to process each item of data in the order in which it is stored.

two。 Operations on queu

The queue supports two main operations: join the team and leave the team. In addition, you may find it useful to perform peek and length operations on the queue.

Queue operation

The queuing operation is to insert an item at the end of the queue and the inserted item becomes the tail of the queue.

The queuing operation in the figure above inserts item 8 into the tail, and 8 becomes the tail of the queue.

Queue.enqueue (8)

Out of line operation

The dequeue operation extracts the item at the beginning of the queue, and the next item in the queue becomes the header item.

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

Queue.dequeue (); / / = > 7

View operation

The view operation reads the beginning of the queue without changing the queue.

Item 7 is the beginning of the queue in the figure above, and the view operation returns only header (project) 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 figure: 4, 6, 2, and 7, as a result, the queue length is 4.

Queue.length; / / = > 4

Queue operation time complexity

What is important for all queue operations (queuing, dequeuing, viewing, and length) is that all of these operations must be performed O (1) within a fixed time.

The constant time O (1) means that no matter the size of the queue (it can have 10 or 1 million items): join, dequeue, snoop and length operations must be performed at the same time.

3. Implementing queues in JavaScript

Let's look at the possible implementation of the queue data structure while maintaining the requirement that all operations must be performed within a constant time.

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 (); / / = > 7queue.peek (); / / = > 2queue.resume; / / = > 3

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

Call the queue.enqueue (7) method to queue this item 7.

Queue.dequeue () takes a header from the queue, while queue.peek () just looks at it from scratch.

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

About implementation: within the Queue class, the normal object this.items retains the items in the queue through a numerical index. The index of the header item is determined by the trace this.headIndex, and the tail item is indexed by the trace this.tailIndex.

Complexity of queuing method

The Queue-like methods queue (), dequeue (), peek (), and length () only use:

Property access (for example, 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 kind of first-in, first-out (FIFO): the items that are the first to join the team are the first to leave the team.

The queue has two main operations: joining the team and leaving the team. In addition, the queue can have auxiliary operations, such as view and length.

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

This is the end of the article on "how to implement queues in JavaScript". I hope the above content can be of some help to you, so that you can learn more knowledge. if you think the article is good, please share it for more people to see.

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.