Detailed explanation of queue data structure, how to implement it in js?

Being an excellent programmer requires a breadth of knowledge. The first thing is to understand your chosen programming language. If you're reading this article, you're most likely using JavaScript.

However, after becoming familiar with the programming language, you must also understand how to easily and effectively manipulate data according to the task. This is where data structures come in.

In this article, I will describe the structure of queue data: what operations it has and how to implement it in JavaScript.

1. Queue data structure

If you like to travel around, you must have gone through the ticket check-in procedure at the train station. If a lot of people want to take a train, it's natural for a queue to form. People who have just entered the station join the queue. On the other side, people who had just passed the ticket check walked out of the queue. This is an example of a queue and operates in the same way as the queue data structure.

Queue is a data structure that follows the first-in-first-out (FIFO) rule. The first item to enter the queue (input) is the first to dequeue (output).

The queue has two pointers: the head of the queue and the tail of the queue. The first item to enter the queue for queuing is located at the head of the queue , and the last item to enter the queue is located at the tail .

Looking back at the station example, the first person to check in is at the head of the queue. People who have just entered the queue are at the end of the queue.

At a high level, a queue is a data structure that allows you to process items in sequence.

2. Queue operations

The queue supports 2 main operations: Enqueue (enqueue) and Dequeue (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 inserts 8 at the end of the queue, and then 8 becomes 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 item 7 and removes it from the queue. After leaving the team, project 2 becomes 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.

7 in the picture above is the leader of the team. The peek operation only needs to return the head of the queue 7 but 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, 2 and. 7. The resulting queue length is 4.

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 stores 7 into the queue.

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

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

About implementation: In the Queue class, the ordinary object this.Items maintains the items of the queue through numerical indexes. The index of the first item in the queue is tracked by Where.HeadInex, and the index of the last item in the queue is tracked by this.tailIndex.

The complexity of the queue method

is in the queue() and dequeue()## of Queue #, peek() and length() 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 the dequeue() and peek() methods to throw an error when executed on an empty queue.

For more programming related knowledge, please visit: Programming Video! !

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