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

In this article, the editor introduces in detail "how to achieve a queue data structure in JavaScript". The content is detailed, the steps are clear, and the details are handled properly. I hope this "how to achieve a queue data structure in JavaScript" article can help you solve your doubts.

1. Queue data structure

If you like to travel (like me), you probably checked in at the airport. If many passengers are willing to check in, there will naturally be a long queue at the check-in counter.

Passengers who have just entered the airport and want to check in will be queued up, while those who have just checked in at the reception desk can leave the queue.

This is a real example of a queue-the queue data structure works in the same way.

Queues are a type of first-in first-out (FIFO) data structure. The first item to join the team (input) is the first item to be out (output).

Structurally, a queue has two pointers. The earliest queued item in the queue is at the top of the queue, while the newest queued item is at the end of the queue.

two。 Actions in queu

Queues support two main operations: in queue (enqueue) and out queue (dequeue). In addition, you may find it useful to use peek and length operations.

2.1 queuing operation

The queuing operation inserts an item at the end 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)

2.2 out-of-line operation

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

In the picture above, the dequeue operation returns from the queue and deletes item 7, and after leaving the queue, item 2 becomes the new header.

Queue.dequeue (); / / = > 7

2.3 Peek operation

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

Item 7 is the header of the queue in the figure above, and the Peek operation simply returns the header of the queue, item 7, without modifying the queue.

Queue.peek (); / / = > 7

2.4 queue length

The length operation calculates how many items the queue contains.

The queue in the picture has four items: 4, 6, 2, and 7. Therefore, the queue length is 4.

Queue.length; / / = > 4

2.5 queue operation time complexity

For all queue operations-- enqueue, dequeue, peek, and length-- it is important that all of these operations must be performed within a constant amount of time O (1).

A constant time O (1) means that regardless of the size of the queue (it can have 10 or 1 million items): enqueue, dequeue, peek, and length operations must be performed at relatively 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 at a 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

Try the demo.

Const queue = new Queue () is the way to create a queue instance.

Calling the queue.enqueue (7) method queues item 7.

Queue.dequeue () queues a header item from the queue, while queue.peek () is just an item in the Peek header.

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

Complexity of queuing method

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

Property accessors (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).

After reading this, the article "how to implement a queue data structure in JavaScript" has been introduced. If you want to master the knowledge points of this article, you still need to practice and use it yourself to understand it. If you want to know more about related articles, welcome to follow the industry information channel.

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.