Data structure “queue”

What is a queue

A Queue is a first in first out (FIFO) data structure. In general, the insert operation is called enqueue in the stack, and a new element is always added to the end of the queue. A delete operation, called a dequeue in the stack, always deletes the first element in the queue.

Second, simulate the implementation queue

Before we can simulate the functionality of queues, we need to understand the methods of queues:

• Enqueue (Element): Adds one or more elements to a queue
• Dequeue (): removes the first element in the queue and returns it
• Front (): Gets the first element in the queue
• IsEmpty (): checks whether the queue isEmpty
• Clear (): clears elements in the queue
• Size: Returns the length of the queue

In javascript, there are no queues, but we can use arrays to simulate the function of queues.

class Queue { constructor() { this.data = []; } enqueue(element) { this.data.push(element); } dequeue() { const element = this.data.shift(); return element; } front() { return this.data[0]; } isEmpty() { return this.data.length === 0; } clear() { this.data = []; } size() { return this.data.length; }}Copy the code

Use queues to solve problems

1. In what scenarios

Consider using queues for any scenario that involves fifO.

For example: canteen queue for meals, JS asynchronous task queue, calculate the number of recent requests and so on

2. Number of recent requests

Leetcode 933 number of recent requests

Write a RecentCounter class to count the most recent request. It has only one method: ping(int t), where t stands for some time in milliseconds. Returns the number of pings from 3000 ms ago to the present. Any pings within the [T-3000, t] time range will be counted, including current pings. Make sure that each call to ping uses a larger t value than before. Example: the input: inputs = [" RecentCounter ", "ping", "ping", "ping", "ping"], inputs = [[], [1], [100], [3001], [3002]] output: [null, 1,2,3,3]Copy the code

Answer:

• The earlier the request is made, the earlier the request is not included in the last 3000ms.
• For fifO, consider using queues
• If there is a new request, join the team and remove the request sent before 3000ms
• The length of the queue is the number of recent requests

Code implementation

var RecentCounter = function() {
	this.queue = [];
};

RecentCounter.prototype.ping = function(t) {
	this.queue.push(t);
    while (this.queue[0] < t - 3000) {
    	this.queue.shift();
    }
    return this.queue.length;
};
Copy the code

Priority queues

The removal and addition of elements to a priority queue are priority-dependent. Priority queues are classified by priority into minimum priority queues and maximum priority queues.

To implement a priority queue, there are two options:

• Set the priority, add the element correctly according to the priority, and then remove it as normal
• Set the priority, add the queue as normal, and remove the queue according to the priority

The first method is generally used to implement priority queues, so you just need to override the enqueue method above

Class MinPriorityQueue {constructor() {this.data = []; this.enqueue = enqueue; } enqueue(element, priority) { let queueElement = { element: element, priority: priority }; if (this.isEmpty()) { this.data.push(queueElement); } else { let added = false; for (let i = 0; i < this.size(); i++) { if (queueElement.priority < this.data[i].priority) { this.data.splice(i, 0, queueElement); added = true; break; } } if (! added) { this.data.push(queueElement); } } } dequeue() { const queueElement = this.data.shift(); return queueElement; } front() { return this.data[0]; } isEmpty() { return this.data.length === 0; } clear() { this.data = []; } size() { return this.data.length; }}Copy the code

5. Circular queues

Circular queue with fixed size array and two Pointers to indicate the start and end positions.

class CirculateQueue { construtor(len) { this.data = new Array(len); this.size = len; this.head = -1; this.tail = -1; } enqueue(element) { if (this.isFull()) return false; if (this.isEmpty()) this.head = 0; this.tail = (this.tail + 1) % this.size; this.data[this.tail] = element; return true; } dequeue() { if (this.isEmpty()) return false; if (this.head === this.tail) { this.head = -1; this.tail = -1; return true; } this.head = (this.head - 1) % this.size; return true; } getFront() { if (this.isEmpty()) return -1; return this.data[this.head]; } getRear() { if (this.isEmpty()) return -1; return this.data[this.tail]; } isEmpty() { return this.head === -1; } isFull() { return (this.tail + 1) % this.size === this.head; }}Copy the code