Explain the queue, priority queue, circular queue, and implement a queue

This is the fifth day of my participation in the November Gwen Challenge. Check out the details: The last Gwen Challenge 2021

📢 Hello everyone, I am Xiao Cheng, a sophomore front-end enthusiast

📢 This article explains queues in data structures

📢 Thank you very much for reading

📢 May you be true to yourself and love life

💡 Knowledge points look first

What is a queue?
What methods do queues have?
Implement a queue by hand
Priority queue, circular queue
LeetCodeIn actual combat

📢 twitter

In the last article, we looked at the stack data structure, which is a linear structure with lifO.

In this article, we will look at queue data structures, which are also linear structures, but very different from stacks

What is a queue?

Very similar to stacks, but queues follow different rules than stacks

The queue follows a first-in, first-out rule, where elements are added at the tail, removed from the head, and the latest element is placed at the end

We can visualize a queue structure as a queue

In the picture below, there are a lot of people coming to buy French fries. The newcomer is always at the end of the line

Almost all examples of queuing in life can be used to describe a queue

In the example above,

We call the first element of the team head, the operation of adding elements is called joining the team, and the operation of removing elements after buying chips is called making the team

In the front-end world, there are also many applications for queues, such as

Task queues related to event handling mechanisms

JavaScript will maintain a microtask queue during execution. When a microtask is encountered, it will be added to the task queue. After executing the macro task, it will fetch the microtask from the task queue to execute it. For details on execution mechanisms and event loops, see the previous article: JavaScript Runtime Mechanism Parsing

What are the methods of queues?

Like the stack structure, queues have a wealth of methods, such as queuing, queuing, query, etc…

Here we mainly introduce the following

methods	meaning
`enqueue(element)`	Add a new element at the end of the queue
`dequeue()`	Removes the first item in the queue and returns
`front()`	Returns the first element in the queue
`isEmpty()`	Returns if the queue does not contain any elements`true`Otherwise, for`false`
`size()`	Returns the number of elements in the queue
`clear()`	Empty the queue
`print()`	Print all elements

Three, handwritten implementation of a queue

You’ve learned how queues can be used to implement a simple queue structure

As with the linear structure of a stack, we can implement a queue using arrays

One element of the array is considered the header

The last bit of the array is considered the end of the queue

1. Create a Queue

Start by creating a queue class and using the queueData variable to hold the data

class Queue {
    constructor() {
        this.queueData = []
    }
}
Copy the code

2. Implement enqueue

The enqueue method is to add new elements to the array, according to the rules of the queue should be added to the end of the queue, so we can use the array push method to implement

enqueue(element) {
    this.queueData.push(element)
}
Copy the code

3. Implement the dequeue method

The dequeue method removes the first element of the array, that is, the head. This can be done using the shift method of the array, which takes the first element of the array and returns it

dequeue() {
    return this.queueData.shift()
}
Copy the code

Let’s see how we can use the enqueue and dequeue methods, okay

const queue = new Queue()
queue.enqueue(2) / / into the
queue.enqueue(1) / / into the
queue.enqueue(5) / / into the
queue.dequeue()  / / the
queue.dequeue()  // c
Copy the code

Realize dynamic figure

4. Implement front method

The front method returns one element of the array, that is, the header value, which can be retrieved directly with [0]

front() {
    return this.queueData[0]}Copy the code

5. Implement isEmpty

The isEmpty method is used to determine whether the queue isEmpty and returns true if it isEmpty and false if it is not

Here we can use the length of the array to determine whether it is empty

isEmpty() {
    return !this.queueData.length
}
Copy the code

6. Implement size method

The size method returns the length of the queue, which can be replaced by the array length method

size() {
    return this.queueData.length
}
Copy the code

7. Implement clear method

The clear method clears the entire queue, which can be done by resetting the array

clear() {
    this.queueData = []
}
Copy the code

Implement the print method

The print method prints all the elements in the queue, which we can implement using the toString() method

print() {
    return this.queueData.toString()
}
Copy the code

9. Complete Queue class

class Queue {
    constructor() {
        this.queueData = []
    }
    enqueue(element) {
        this.queueData.push(element)
    }
    dequeue() {
        return this.queueData.shift()
    }
    front() {
        return this.queueData[0]}isEmpty() {
        return !this.queueData.length
    }
    size() {
        return this.queueData.length
    }
    clear() {
        this.queueData = []
    }
    print() {
    	return this.queueData.toString()
	}
}
Copy the code

At this point, we have implemented a complete queue structure that is very easy to implement

One of the most frequently mentioned queue structures is the priority queue, so let’s talk about it briefly

Priority queues

1. What is a priority queue?

A priority queue is a queue whose elements have a priority. Elements are added and removed based on priority. Those with a higher priority join the queue first and those with a lower priority join the queue later.

In real life, most cases are priority queues, for example:

In hospital emergency rooms, doctors prioritize the sickest patients over the weaker ones

As we study, we should also prioritize things

2. Implement enqueue

The main difference between a priority queue and a normal queue is the way it adds elements

First, each element has a priority
Inserts elements according to the size of the priority value

For a min-priority queue, it is sorted in order of priority value

Tips: The lower the priority value, the higher the priority

So we need to modify the code for adding elements to enQueue

First we need to create a priority node class

Because the elements in the queue have two attributes, value and priority, they are implemented using classes

class QueueElement {
    constructor(element, priority) {
        this.element = element
        this.priority = priority
    }
}
Copy the code

When creating an element, we just need to new to create a node with values and priorities

Next, implement an enqueue method

When the queue is empty, it is pushed directly into the queue
When not empty, we walk through the queue and compare its priority. Insert where the priority value is higher than it
usingspliceMethod insert, (splice: How many elements to delete and what elements to insert in a location)
When the inserted element has the highest priority value, push directly

enqueue(element, priority) {
    let queueElement = new QueueElement(element, priority)
    // Push the queue if it is empty
    if (this.isEmpty()) {
        this.data.push(queueElement)
    } else {
        // flag Records whether the insertion is successful
        let flag = false
        for (let i = 0; i < this.data.length; i++) {
            if (queueElement.priority < data[i].priority) {
                // Insert at the specified position
                this.data.splice(i, 0, queueElement)
                // Flag reset
                flag = true
                // End the loop prematurely
                break; }}if(! flag)this.data.push(queueElement)
    }
}
Copy the code

So a priority queue is implemented, and the other methods are the same as normal queues

5. Circular queues

Another modified version of the queue: the circular queue. Circular queues go round and round, end to end

The difference between a circular queue and a normal queue is that the circular queue ends at the head

We pass a classic drum pass flower game to introduce

📢 Rules:

In this game, children form a circle and pass flowers as quickly as possible to the person next to them. At a certain point, the flowers stop, this time in the hands of the flower, who quit the circle to end the game. Repeat the process until there is only one child left (winner).

Similar to the figure above, the input number is 7, the first round of C is eliminated, the flower is passed to its next digit, and the count starts again from here

Code implementation

function hotPotato(nameList, num) {
    const queue = new Queue()
    // Add players
    for (let i = 0; i < nameList.length; i++) {
        queue.enqueue(nameList[i])
    }
    let dead = ' '
    // Implement the loop
    while (queue.size() > 1) {
        // The queue is rearranged
        for (let i = 0; i < num; i++) {
            queue.enqueue(queue.dequeue())
        }
        // Output obsolete information
        dead = queue.dequeue()
        console.log(dead + 'out');
    }
    // Return the last winner
    return queue.dequeue()
}
let names = ['a'.'b'.'c'.'e'.'f']
let winner = hotPotato(names, 7)
Copy the code

Such a drum pass flower game is designed, you know the final winner is who?

LeetCode practice

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()Initialize the counter with a request count of 0.

int ping(int t)Add a new request at time t, where t represents some time in milliseconds, and return the number of all requests (including new requests) that occurred 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.

Their thinking

Will enter the time each timetJoin the queue
Start at the top of the queue and kick out elements that are not in the 3000 range
becausetIt’s a moment in time

AC code

var RecentCounter = function () {
    this.q = []
};
RecentCounter.prototype.ping = function (t) {
    this.q.push(t)
    // Kick out all elements that are not in 3000
    while (this.q[0] < t - 3000) {
        this.q.shift()
    }
    return this.q.length
};
Copy the code

📖 summary

In this article, we start from the implementation of a common queue, future priority queue, circular queue, and finally AN AC algorithm, or very profitable ~ probably need to master the following content

Implement a normal queue
Know how to encapsulate the priority queue addition method
Master the mysteries of circular queues

That concludes this article on queues, which I’m sure you’ll learn a lot from. The next article will explore the mysteries of sets.

The rest of this column

Stack 👉 what is a stack? Handwriting a stack structure!

Queue 👉 [Untangle data structures] Turn on data structures and algorithms from here

(The linked list has been published a long time ago. In order not to violate the rules of the platform, I will not republish it. The article “Undoing Data Structures” will show you how to understand the front-end data structure – linked lists.)

You are welcome to follow this column and stay tuned for the latest articles

Finally, I may not be clear enough in many places, please forgive me

💌 if the article has any mistakes, or have any questions, welcome to leave a message, also welcome private letter exchange

Explain the queue, priority queue, circular queue, and implement a queue

💡 Knowledge points look first

What is a queue?

What are the methods of queues?

Three, handwritten implementation of a queue

1. Create a Queue

2. Implement enqueue

3. Implement the dequeue method

4. Implement front method

5. Implement isEmpty

6. Implement size method

7. Implement clear method

Implement the print method

9. Complete Queue class

Priority queues

1. What is a priority queue?

2. Implement enqueue

5. Circular queues

LeetCode practice

933. Number of recent requests

📖 summary

Related Posts

TypeScript — Type compatibility

Front-end performance optimization based on React.Suspense and React.lazy

Js the multidimensional array into a one-dimensional array method