preface
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. A queue with no elements is called an empty queue.
The data elements of a queue are also called queue elements. Inserting a queue element into a queue is called enqueueing, and removing a queue element from a queue is called enqueueing. Because the queue can only be inserted at one end and deleted at the other end, only the earliest element can be deleted from the queue first, so the queue is also called FIFO – first in first out (FIFO – first in first out) linear table.
Tip: the article about 15300 words, more detailed introduction of the queue in JS application and role, the realization of several common algorithms with queue code. The following is the main content of this article, and the following cases are for reference
What is a queue?
1. Queues in life
A real life example of queuing
2. Queues in programs
Like this
After reading these pictures, I feel that the program is very close to life. Most of the inspiration of the process design comes from the observation of life. After repeated application and verification, it will be convenient in life.
Second, various types of queues
1. Basic queues
1.1 Methods in queues
- Enqueue (Element) : Adds a new item to the end of the queue.
- Dequeue () : removes the first item in the queue and returns the removed element.
- Front () : Returns the first element in the queue, unchanged.
- IsEmpty () : Returns true if the queue contains no elements, false otherwise.
- Size () : Returns the number of elements contained in the queue, similar to the length property of an array.
- Print () : Prints the elements in the queue.
- Clear () : Clears the entire queue.
1.2 Queue Class Creation
Tip:
JavaScript doesn’t have its own built-in queue data structure type like Java, C# or other strongly typed programming languages. In javaScript, we usually wrap queue classes or queue constructors with arrays.
class Queue {
constructor() {
this.items = []
}
// Add an element to the end of the queue
enqueue(element) {
this.items.push(element)
}
// Remove the first element of the queue and return the removed element
dequeue() {
return this.items.shift()
}
// return the first element of the queue
front() {
return this.items[0]}// Check whether the queue is empty
isEmpty() {
return this.items.length === 0
}
// Get the length of the queue
size() {
return this.items.length
}
// Clear the queue
clear() {
this.items = []
}
// Prints the elements in the queue
print() {
console.log(this.items.toString())
}
}
Copy the code1.3 Use queues to convert decimal to binary
function generatePrintBinary(n) {
let q = new Queue()
q.enqueue('1')
while (n-- > 0) {
let s1 = q.front()
q.dequeue()
console.log(s1)
let s2 = s1
q.enqueue(s1 + '0')
q.enqueue(s2 + '1')
}
}
generatePrintBinary(5) // => 1 10 11 100 101
Copy the code1.4 constructor to create the queue
The code is as follows (example) :
/ / the Queue class
function Queue() {
this.items = [];
// Add an element to the end of the queue
this.enqueue = function(element) {
this.items.push(element);
};
// Remove the first element of the queue and return the removed element
this.dequeue = function() {
return this.items.shift();
};
// return the first element of the queue
this.front = function() {
return this.items[0];
};
// Check whether the queue is empty
this.isEmpty = function() {
return this.items.length === 0;
};
// Get the length of the queue
this.size = function() {
return this.items.length;
};
// Clear the queue
this.clear = function() {
this.items = [];
};
// Prints the elements in the queue
this.print = function() {
console.log(this.items.toString());
};
}
Copy the code1.5 Create sample objects to test
Description:
Either created as a class or implemented as a constructor can be tested with the following sample code
// Create a Queue instance
let queue = new Queue();
console.log(queue.isEmpty()); // true
queue.enqueue('Aristotle');
queue.enqueue('Plato');
queue.enqueue('Socrates');
queue.print(); // "Aristotle, Plato, Socrates"
console.log(queue.size()); / / 3
console.log(queue.isEmpty()); // false
queue.dequeue();
queue.dequeue();
queue.print(); // "Socrates"
queue.clear();
console.log(queue.size()); / / 0
Copy the codeDescription:
The following code is implemented as a class
Tip: You can create queues using not only arrays but also objects as data structure bases
- You define your class like this, and then the methods inside of it think about it this way
class Queue {
constructor() {
this.count = 0; {1} controls the size of the queue
this.lowestCount = 0; // {2} trace the first element
this.items = {}; // {3} items to store the elements}}Copy the code2. Minimum priority queue
2.1 Differences with basic queues
2.2 Code Implementation
The code is as follows (example) :
class MinPriorityQueue {
constructor() {
this.items = [];
}
// To add elements to the priority queue, the order of insertion is determined according to the priority
enqueue(element, priority) {
let queueElement = {
element: element,
priority: priority
};
if (this.isEmpty()) {
this.items.push(queueElement);
} else {
let added = false;
for (let i = 0; i < this.size(); i++) {
if (queueElement.priority < this.items[i].priority) {
this.items.splice(i, 0, queueElement);
added = true;
break; }}if(! added) {this.items.push(queueElement); }}}// Remove the first element of the queue and return the removed element
dequeue() {
return this.items.shift();
};
// return the first element of the queue
front() {
return this.items[0];
};
// Check whether the queue is empty
isEmpty() {
return this.items.length === 0;
};
// Get the length of the queue
size() {
return this.items.length;
};
// Clear the queue
clear() {
this.items = [];
};
// Prints the elements in the queue
print() {
let strArr = [];
strArr = this.items.map(function (item) {
return `${item.element}->${item.priority}`;
});
console.log(strArr.toString()); }}Copy the codeThe enqueue method above adds a bit of priority judgment, using the js array splice method on the use of the detailed tutorial splice
The splice() method modifies an array by deleting or replacing existing elements or adding new ones in place, and returns the modified contents as an array. This method changes the original array.
Usage:
- Feel the
const months = ['Jan'.'March'.'April'.'June'];
months.splice(1.0.'Feb');
// inserts at index 1
console.log(months);
// expected output: Array ["Jan", "Feb", "March", "April", "June"]
months.splice(4.1.'May');
// replaces 1 element at index 4
console.log(months);
// expected output: Array ["Jan", "Feb", "March", "April", "May"]
Copy the code- Delete 1 element starting at index 2 and insert “trumpet”
var myFish = ['angel'.'clown'.'drum'.'sturgeon'];
var removed = myFish.splice(2.1."trumpet");
// 运算后的 myFish: ["angel", "clown", "trumpet", "sturgeon"]
// Deleted element: ["drum"]
Copy the code- Delete 2 elements from index 0 and insert “parrot”, “anemone”, and “blue”
var myFish = ['angel'.'clown'.'trumpet'.'sturgeon'];
var removed = myFish.splice(0.2.'parrot'.'anemone'.'blue');
// myFish after calculation: [" Parrot ", "Anemone "," Blue ", "Trumpet "," Sturgeon "]
// Removed element: ["angel", "Clown "]
Copy the code2.3 Example Test Examples
// Create minPriorityQueue instance
let minPriorityQueue = new MinPriorityQueue();
console.log(minPriorityQueue.isEmpty()); // true
minPriorityQueue.enqueue("John".1);
minPriorityQueue.enqueue("Jack".3);
minPriorityQueue.enqueue("Camila".2);
minPriorityQueue.enqueue("Tom".3);
minPriorityQueue.print(); // John->1,Camila->2,Jack->3,Tom->3
console.log(minPriorityQueue.size()); / / 4
console.log(minPriorityQueue.isEmpty()); // false
minPriorityQueue.dequeue();
minPriorityQueue.dequeue();
minPriorityQueue.print(); // Jack->3,Tom->3
minPriorityQueue.clear();
console.log(minPriorityQueue.size()); / / 0
Copy the codeOutput:
3. Maximum priority queue
3.1 Differences with basic queues
- The method of entrance
enqueue(element, priority) {
let queueElement = {
element: element,
priority: priority
};
if (this.isEmpty()) {
this.items.push(queueElement);
} else {
let added = false;
for (let i = 0; i < this.size(); i++) {
if (queueElement.priority > this.items[i].priority) {
this.items.splice(i, 0, queueElement);
added = true;
break; }}if(! added) {this.items.push(queueElement); }}}Copy the code- A method to print a queue
print() {
let strArr = [];
strArr = this.items.map(function (item) {
return `${item.element}->${item.priority}`;
});
console.log(strArr.toString());
}
Copy the codeThe difference between a maximum priority queue and a minimum priority queue is just the judgment of priority
if (queueElement.priority < this.items[i].priority) // Minimum priority queue
if (queueElement.priority > this.items[i].priority) // Maximum priority queue
Copy the codeThe complete code is as follows (example) :
/ / the Queue class
class MaxPriorityQueue {
constructor() {
this.items = [];
}
// To add elements to the priority queue, the order of insertion is determined according to the priority
enqueue(element, priority) {
let queueElement = {
element: element,
priority: priority
};
if (this.isEmpty()) {
this.items.push(queueElement);
} else {
let added = false;
for (let i = 0; i < this.size(); i++) {
if (queueElement.priority > this.items[i].priority) {
this.items.splice(i, 0, queueElement);
added = true;
break; }}if(! added) {this.items.push(queueElement); }}}// Remove the first element of the queue and return the removed element
dequeue() {
return this.items.shift();
};
// return the first element of the queue
front() {
return this.items[0];
};
// Check whether the queue is empty
isEmpty() {
return this.items.length === 0;
};
// Get the length of the queue
size() {
return this.items.length;
};
// Clear the queue
clear() {
this.items = [];
};
// Prints the elements in the queue
print() {
let strArr = [];
strArr = this.items.map(function (item) {
return `${item.element}->${item.priority}`;
});
console.log(strArr.toString()); }}Copy the code3.2 Example Test examples
// Create maxPriorityQueue instance
let maxPriorityQueue = new MaxPriorityQueue();
console.log(maxPriorityQueue.isEmpty()); // true
maxPriorityQueue.enqueue("John".1);
maxPriorityQueue.enqueue("Jack".3);
maxPriorityQueue.enqueue("Camila".2);
maxPriorityQueue.enqueue("Tom".3);
maxPriorityQueue.print(); // "Jack->3,Tom->3,Camila->2,John->1"
console.log(maxPriorityQueue.size()); / / 4
console.log(maxPriorityQueue.isEmpty()); // false
maxPriorityQueue.dequeue(); // {element: "Jack", priority: 3}
maxPriorityQueue.dequeue(); // {element: "Tom", priority: 3}
maxPriorityQueue.print(); // "Camila->2,John->1"
maxPriorityQueue.clear();
console.log(maxPriorityQueue.size()); / / 0
Copy the codeOutput:
4. Loop queues
4.1 introduction
In practice, to make the queue space reusable, the queue is often used in a slightly modified way: whenever the rear pointer increases by 1 or the front pointer increases by 1 and exceeds the allocated queue space, it points to the starting position of the contiguous space.
Rear % MaxSize = rear % MaxSize = front % MaxSize = rear % MaxSize = front % MaxSize = rear % MaxSize This is actually to think of the queue space as a ring space in which the storage units are recycled. Queues managed in this way are also called circular queues. Except for some simple applications, the really useful queue is the circular queue.
4.2 Hot Potato game of Circular Queue
- The new Queue () class used below is the first base Queue class defined above
// Achieve drum pass flowers
// Achieve drum pass flowers
function hotPotato (nameList, num) {
let queue = new Queue();
// Join the team
for (let i = 0; i < nameList.length; i++) {
queue.enqueue(nameList[i]);
}
// Record eliminated participants
let eliminated = ' ';
let n = Math.floor(Math.random()*num + 1)
while (queue.size() > 1) {
// loop 1 to num times, the leader of the queue goes to the end of the queue
for (let i = 0; i < n; i++) {
queue.enqueue(queue.dequeue());
}
After loop 1 to num, remove the current queue head element
eliminated = queue.dequeue();
console.log(`${eliminated}Be eliminated in the drum pass! `);
}
// There is only one element left
return queue.dequeue();
}
Copy the code- The test data
/ / test
let nameList = ["Sun Wukong"."Tang's monk"."Sand monk".White Dragon Horse."Pig Eight Quit".'Pig Eight quit his two aunt'];
let winner = hotPotato(nameList, 10);
console.log('The final winner was:${winner}`);
Copy the code- The results of
Note: the entry parameter is namelist and the highest number of cycles num so that each cycle is a random operation, there is no suspicion of black box operation.
5. Dual-ended queue data structures
5.1 Introduction to and dual-ended queue class code
A deque, or double-ended queue, is one that allows us to add and remove from both the front end and the back end
A special queue of elements. Examples of double-ended queues in real life include queues in cinemas and restaurants. For example, a person who has just bought a ticket can go straight back to the head of the line if they just need to ask a few more simple questions. In addition, the person at the end of the line can just leave the line if he is in a hurry.
In computer science, a common use of double-endian queues is to store a series of undo operations. Every time a user performs an operation in the software, the operation is stored in a double-ended queue (like in a stack). When the user clicks the undo button, the action is ejected from the two-end queue, indicating that it has been removed from behind. After a predefined number of operations are performed, the first operation is removed from the front of the two-end queue. Since the two-ended queue complies with both fifO and LIFO principles, it can be said that it is a kind of data structure combining queue and stack
LowestCount is used to track the first element (header), and count is used to count, not the length of the array, so it looks a bit more cumbersome.
- Double-endian queue class
class Deque {
constructor() {
this.items = {} // {1} uses an object to store elements
this.count = 0 {2} controls the size of the queue
this.lowestCount = 0 // {3} is used to trace (header) the first element
}
// Add an element to the queue header
addFront(ele) {
if (this.isEmpty()) { {1} The first scenario is that the queue is empty
this.items[this.count] = ele
} else if (this.lowestCount > 0) { // {2} The second scenario is one in which an element has been removed from the front of a two-ended queue
this.lowestCount -= 1
this.items[this.lowestCount] = ele
} else {
for (let i = this.count; i > 0; i--) { // {3} moves all elements back one bit
this.items[i] = this.items[i - 1]}this.items[0] = ele // {4} overwrite it with the new element that needs to be added
}
this.count++
return ele
}
// Remove the element from the queue header
removeFront() {
if (this.isEmpty()) {
return
}
const delEle = this.items[this.lowestCount]
delete this.items[this.lowestCount] // delete deletes an object's keyword API for JavaScript
this.lowestCount++
return delEle
}
// Add an element to the end of the queue
addBack(ele) {
this.items[this.count] = ele
this.count++
}
// Remove the element at the end of the queue
removeBack() {
if (this.isEmpty()) {
return
}
const delEle = this.items[this.count - 1]
delete this.items[this.count - 1]
this.count--
return delEle
}
// Get the first element in the header of a double-ended queue
peekFront() {
if (this.isEmpty()) {
return
}
return this.items[this.lowestCount]
}
// Get the first element at the end of the double-ended queue
peekBack() {
if (this.isEmpty()) {
return
}
return this.items[this.count - 1]}size() {
return this.count - this.lowestCount
}
isEmpty() {
return this.size() === 0
}
clear() {
this.items = {}
this.count = 0
this.lowestCount = 0
}
toString() {
if (this.isEmpty()) {
return ' '
}
let objString = `The ${this.items[this.lowestCount]}`
for (let i = this.lowestCount + 1; i < this.count; i++) {
objString = `${objString}.The ${this.items[i]}`
}
return objString
}
}
Copy the code5.2 Relevant algorithms and code implementation – palindrome checker
- Explanation: A palindrome is a word, phrase, number, or sequence of characters that can be read forward or backward, such as madam or racecar.
There are different algorithms that check whether a phrase or string is palindrome. The easiest way is to reverse the string and check that it is the same as the original string. If the two are the same, then it is a palindrome. We could also do this with a stack, but the easiest way to solve this problem with data structures is to use a double-endian queue.
- Palindrome inspector code
function palindromeChecker(str) {
// Check whether the input condition is empty or a string
if(! str ||typeofstr ! = ='string'| |! str.trim().length) {return false
}
const deque = new Deque()
// Convert to lowercase
const lowerString = str.toLowerCase().split(' ').join(' ')
// Enqueue each character
for (let i = 0; i < lowerString.length; i++) {
deque.addBack(lowerString[i])
}
let isEqual = true
let firstChar = ' '
let lastChar = ' '
while (deque.size() > 1 && isEqual) {
firstChar = deque.removeFront()
lastChar = deque.removeBack()
// Push both ends to the middle to check whether palindrome
if(firstChar ! = lastChar) { isEqual =false}}return isEqual
}
Copy the code- test
let a = 'ABXBA'
let b = 'fddf'
let c = 'abcdefg'
console.log(palindromeChecker(a)) // true The current palindrome
console.log(palindromeChecker(b)) // true The current palindrome
console.log(palindromeChecker(c)) // false Is not a palindrome
Copy the code- The results of
6. Concurrent queues
Description:
The concurrent queue is more important to the programming of the bottom layer of the computer. The bottom layer involves more concurrent queues, and the front queue……
Simple understand understand understand understand
7. Block the queue
A BlockingQueue is a queue that supports two additional operations. The two additional operations are:
- When the queue is empty, the thread that fetched the element waits for the queue to become non-empty.
- When the queue is full, the thread that stores the element waits for the queue to become available.
The application of queue data structure in the algorithm
1. Queue in LeetCode algorithm
1.1 933 Number of recent requests
Each ping will store an element in the queue, and then check to see if the previous element is not in the queue. If so, delete it.
Take the example given in the question:
Input:
[” RecentCounter “, “ping”, “ping”, “ping”, “ping”] [[], [1], [100], [3001], [3002]] output: [null, 1, 2, 3, 3]
The first deposit is 1, the second deposit is 100… And then each time you save it, look at how many of the elements you saved before, how many of them are between t and t-3000; When I save 1,1 is between [-2999,1], so I return 1; … [2,3002]; [2,3002]; [3,3002];
Their thinking
- The earlier the request is made, the earlier the request is not included in the last 3000ms
- First in, first out, queue
The problem solving steps
- If there is a new request, join the team, the request sent before 3000ms is out of the team
- The queue length is the number of recent requests
Coding Part
var RecentCounter = function() {
// bind a queue to the constructor
this.queue = [];
}
/ * * *@param {number} t
* @return {number}* /
RecentCounter.prototype.ping = function(t) {
this.queue.push(t)
while (this.queue < t - 3000) {
this.queue.shift()
}
return this.queue.length
}
/** * Your RecentCounter object will be instantiated and called as such: * var obj = new RecentCounter() * var param_1 = obj.ping(t) */
let obj = new RecentCounter()
let param_1 = obj.ping(3001)
console.log(param_1);
Copy the codeComplexity analysis
- Time complexity: O(Q)O(Q), where QQ is the number of pings.
- Space complexity: O(W)O(W), where W=3000 W=3000 indicates the maximum number of ping records stored in the queue.
2. Queues in other interview questions
2.1 Asynchronous Interview Questions (Task Queue)
Consider the following print:
setTimeout(() = > {
console.log(1)},0);
console.log(2);
Copy the codeCopy the code between the browser and press F12 to open the console and have a look!
- Like this
- Press Enter to view the result
2.2 Principles of asynchronous queues and event loops
Let’s take a look at the JS asynchronous queue
- The execution logic of the program code in the bottom layer is shown as follows:
- More specific and beautified forms of expression:
- Sometimes when you look at the picture, it’s easier to understand the relationship,
Here is the image result after Google search Event Loop, look at the picture, Google can not access the link oh!
The above figure is divided into (A) the call stack on the left, (B) the asynchronous parsing on the right, and (C) the task queue on the bottom
- (C) Tasks in the task queue are queued to be executed in (A) call stack
- (A) Call stack processing task encountered synchronous program code, it is compiled and executed, encountered asynchronous code program, it is thrown to (B) for asynchronous parsing
- B) Asynchronously parse asynchronous callbacks, timers, HTTP and other asynchronous operations,
- This event loop is like being stripped layer by layer during the asynchronous queue, so the above 2.1 asynchronous interview question will output 2, 1, because setTimeout is asynchronous.
- Similarly, complex asynchronous programs also follow this principle, to clarify the order of layer by layer, can be removed. Execution is straightforward.
conclusion
Above is today’s content, this article briefly introduces the use of queues in JS and the application of actual programs.
Ebook download website 1 ebook download website 2 JavaScript learning website