Detailed explanation of how to implement queue structure in JavaScript

This article will take you to understand the queue data structure, introduce in detail its operations and the method of implementing the queue structure in JavaScript. It has certain reference value. Friends in need can refer to it. I hope it will be helpful to everyone.

#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. Queue operations

The queue supports 2 main operations:Enqueue (enqueue)andDequeue (dequeue), there are also peek and length operations.

2.1 Enqueue operation

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

The queue entry operation in the above picture inserts8at the end of the queue, and then8becomes the end of the queue.

queue.enqueue(8);

2.2 Dequeue operation

The dequeue operation takes out the first item in the queue. At this time, the next item in the queue becomes the leader of the queue.

In the above image, the dequeue operation returns item7and removes it from the queue. After leaving the team, project2becomes the new team leader.

queue.dequeue(); // => 7

2.3 Peek operation

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

7in the picture above is the leader of the team. The peek operation only needs to return the head of the queue7but does not modify the queue.

queue.peek(); // => 7

2.4 length

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

The queue in the above picture has 4 items:4,6,2and.7. The resulting queue length is4.

queue.length; // => 4

2.5 Time complexity of queue operations

The key points about all operations on the queue: enqueue, dequeue, peek and length must be in constant time complexityO (1)Execute.

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

3. Use JavaScript to implement queues

Let’s take a look at how to ensure that all operations must be implemented with constant time complexityO(1)requirements Queue is a data structure.

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.

queue.enqueue(7)method stores7into the queue.

queue.dequeue()Removes a head item from the queue, whilequeue.peek()only reads the head item of the queue.

The lastQueue.Lengthshows how many items are left in the queue.

About implementation: In theQueueclass, the ordinary objectthis.Itemsmaintains the items of the queue through numerical indexes. The index of the first item in the queue is tracked byWhere.HeadInex, and the index of the last item in the queue is tracked bythis.tailIndex.

The complexity of the queue method

is in thequeue()anddequeue()## ofQueue#,peek()andlength()methods exist:

Attribute accessor (such as:
• this.items[this.headIndex ]),
Perform arithmetic operations (such as:
• this.headidex)

The time complexity of these methods is constant time

O(1).

4. Summary

Queue is a data structure that follows the first-in-first-out (FIFO) rule.

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

All queue operations must be executed in constant time

O(1).

Challenge: Improve thedequeue()andpeek()methods to throw an error when executed on an empty queue.

For more programming-related knowledge, please visit:

Introduction to Programming! !

The above is the detailed content of Detailed explanation of how to implement queue structure in JavaScript. For more information, please follow other related articles on the PHP Chinese website!