1, concept,

A queue is a special kind of linear table, special in that it only allows deletion at the front of the table and insertion at the rear. Like a stack, a queue is a linear table with limited operation. The end that inserts is called the end of the queue, and the end that deletes is called the head of the queue. (PS: Source baidu Encyclopedia)

Queue in JS

A queue is a first-in, first-out data structure. There are no queues in JS, but you can use Array to implement all the functions of queues.

// Create an array to emulate the queue
const queue = [];
/ / team
queue.push(1); // queue: [1]
queue.push(2); / / the queue: [1, 2]
/ / out of the team
const first = queue.shift() // stack: [2]
const second = queue.shift() // stack: []
Copy the code

3. Application scenarios of queues

  • A fifO scenario is required.
  • For example: canteen queue for meals, JS asynchronous task queue, calculate the number of recent requests

Js is single-threaded. When the main thread meets an asynchronous task during execution, it initiates a function, or registration function, to notify the corresponding worker thread (such as Ajax, DOM, setTimout, etc.) through the Event loop thread. At the same time, the main thread continues to execute backward without waiting. When the worker thread completes its task, the EventLoop thread adds the message to the message queue, and if the call stack is empty on the main thread, it executes the first message in the message queue. When new messages enter the queue, they are automatically placed at the bottom of the queue.

4, leetCode

LeetCode 933. Number of recent requests

Write a RecentCounter class to count the most recent requests within a specific time range.

  • Please implement RecentCounter class:
  • RecentCounter() initializes the counter with 0 requests.
  • Int ping(int t) adds a new request at time t, where t is some time in milliseconds, and returns the number of requests (including new requests) that have been sent in the last 3000 milliseconds. Specifically, return the number of requests that occurred within [T-3000, t].

Make sure that each call to ping uses a larger t value than before.

var RecentCounter = function() {
    this.q = []; // Define a queue
};

/ * * *@param {number} t
 * @return {number}* /
RecentCounter.prototype.ping = function(t) {
    // the request to join the queue occurred
    this.q.push(t);
    // Check whether the range from the front of the team to the back of the team is outside [t-3000, t]
    // If it is outside the range, the team leader's message is sent directly out of the team
    while (this.q[0] < t - 3000) {
        this.q.shift();
    }
    // The current queue length is the number of requests that occurred
    return this.q.length;
};

/** * Your RecentCounter object will be instantiated and called as such: * var obj = new RecentCounter() * var param_1 = obj.ping(t) */
Copy the code