In-depth analysis of queue implementation in js (code sharing)
In the previous article "A brief analysis of the entry cache problem in Vue (code sharing)", I introduced you to the problem of entry cache in Vue. The following article will introduce you to the implementation of queues in js. Let's take a look.
Queue definition
Queue (Queue) is a first-in-first-out (First in,first out. Referred to as FIFO) An ordered set based on the principle. The difference between it and a stack is that the stack is first in, first out, and the queue is first in, first out. The stack enters and exits at one end, while the queue enters and exits at the other end. The deletion operation of the stack is performed at the end of the table, and the deletion operation of the queue is performed at the head of the table. The sequential stack can realize multi-stack space sharing, but the sequential queue cannot. The common denominator is that only insertion and deletion of elements is allowed at the endpoints. The management modes of multi-chain stacks and multi-chain queues can be the same.
Stack definition
JavaScript is a single-threaded language, and the main thread executes synchronous code. When a function is called, a "call record", also known as a "call frame", is formed in the memory to save information such as the call location and internal variables. If other functions are called within the function, another call record will be formed above the call record, and all call records form a "call stack". (Tail call, tail recursion optimization)
Heap (heap) definition
Objects are allocated in a heap, one used to represent a large unorganized area in memory.
So
JS is a single thread. The main thread executes synchronous code. Asynchronous tasks such as events and I/O operations will enter the task queue for execution. Asynchronous execution has After the result, it will change to a waiting state, forming a first-in-first-out execution stack. After the main thread's synchronization code is executed, the event will be read from the "task queue" and the callback of the event asynchronous task will be executed. This is why the execution order is, Synchronous > Asynchronous > Callback. To put it more simply: as long as the main thread is empty (synchronous), it will read the "task queue" (asynchronous), this is JavaScript operating mechanism.
This article will implement basic queue, priority queue and circular queue
Message Queue and Event LoopEvent Loop
AJavaScript The runtime contains a message queue to be processed (Asynchronous task), (internally it is a task that does not enter the main thread but enters the "task queue" (task queue). For example, UIEvents, ajaxNetwork requests, timers setTimeout and setInterval, etc. Each message is associated with a function (Callback function callback). When the stack is empty, a message is taken from the queue for processing. This processing involves calling the function associated with the message (and thus creating an initial stack Frame). When the stack is empty again, it means that the message processing is over.
This process is cyclic, so the entire operating mechanism is also called Event Loop (Event Loop ).
Basic queue
The basic queue method includes the following 6 methods
① To the queue (tail) Add element (enqueue)
② (from the head of the queue) Delete element (dequeue)
③ Check the element at the head of the queue (front)
④ Check whether the queue is Empty (isEmpty)
⑤ View the length of the queue (size)
⑥ View the queue (print)
function Queue() {
//初始化队列（使用数组实现）
var items = [];
//入队
this.enqueue = function (ele) {
items.push(ele);
};
//出队
this.dequeue = function () {
return items.shift();
};
//返回首元素
this.front = function () {
return items[0];
};
//队列是否为空
this.isEmpty = function () {
return items.length == 0;
};
//清空队列
this.clear = function () {
items = [];
};
//返回队列长度
this.size = function () {
return items.length;
};
//查看列队
this.show = function () {
return items;
};
}
var queue = new Queue();
queue.enqueue("hello");
queue.enqueue("world");
queue.enqueue("css");
queue.enqueue("javascript");
queue.enqueue("node.js");
console.log(queue.isEmpty()); // false
console.log(queue.show()); //hello,world,css3,javascript,node.js
console.log(queue.size()); //5
console.log(queue.front()); //hello
console.log(queue.dequeue()); //hello
console.log(queue.show()); //'world', 'css', 'javascript', 'node.js'
console.log(queue.clear());
console.log(queue.size()); //0Implementation of priority queue
In the priority queue, the addition or deletion of elements is based on priority. There are two ways to implement the priority queue: ① add first, dequeue normally; ② add normally, dequeue first
Add first , an example of normal dequeuing (minimum priority queue) (this example is based on the implementation of the queue, and changes the elements added to the queue from ordinary data to an object (array) type. The object contains the value of the element that needs to be added to the queue and Priority):
function PriorityQueue() {
//初始化队列（使用数组实现）
var items = []
//因为存在优先级，所以插入的列队应该有一个优先级属性
function queueEle(ele, priority) {
this.ele = ele
this.priority = priority
}
//入队
this.enqueue = function (ele, priority) {
let element = new queueEle(ele, priority)
//为空直接入队
if (this.isEmpty()) {
items.push(element)
}
else {
var qeueued = false; //是否满足优先级要求，并且已经入队
for (let i = 0; i < this.size(); i++) {
if (element.priority < items[i].priority) {
items.splice(i, 0, element)
qeueued = true
break;
}
}
//如果不满足要求，没有按要求入队，那么就直接从尾部入队
if (!qeueued) items.push(element)
}
}
//出队
this.dequeue = function () {
return items.shift()
}
//返回首元素
this.front = function () {
return items[0]
}
//队列是否为空
this.isEmpty = function () {
return items.length == 0
}
//清空队列
this.clear = function () {
items = []
}
//返回队列长度
this.size = function () {
return items.length
}
//查看列队
this.show = function () {
return items
}
}
var priorityQueue = new PriorityQueue();
priorityQueue.enqueue('优先级2-1', 2);
priorityQueue.enqueue('优先级1-1', 1);
priorityQueue.enqueue('优先级1-2', 1);
priorityQueue.enqueue('优先级3-1', 3);
priorityQueue.enqueue('优先级2-2', 2);
priorityQueue.enqueue('优先级1-3', 1);
priorityQueue.show(); // 按优先级顺序输出
//输出
[
0:queueEle {ele: "优先级1-1", priority: 1},
1:queueEle {ele: "优先级1-2", priority: 1},
2:queueEle {ele: "优先级1-3", priority: 1},
3:queueEle {ele: "优先级2-1", priority: 2},
4:queueEle {ele: "优先级2-2", priority: 2},
5:queueEle {ele: "优先级3-1", priority: 3}
]Circular queue
You can use a circular queue to simulate the game of drumming and passing flowers (Joseph ring problem): a group of children sit in a circle and pass each time n number, the child holding the flower in his hand when stopping is eliminated until there is only one child left in the team, the winner.
Loop queue, pop up (from the head of the queue) every time it loops A child, then add this child to the end of the queue, loop n times, and when the loop stops, the child at the head of the queue will pop up (eliminated) until there is only one child left in the queue.
function Queue() {
//初始化队列（使用数组实现）
var items = [];
//入队
this.enqueue = function (ele) {
items.push(ele);
};
//出队
this.dequeue = function () {
return items.shift();
};
//返回首元素
this.front = function () {
return items[0];
};
//队列是否为空
this.isEmpty = function () {
return items.length == 0;
};
//清空队列
this.clear = function () {
items = [];
};
//返回队列长度
this.size = function () {
return items.length;
};
//查看列队
this.show = function () {
return items;
};
}
/**
*
* @param {名单} names
* @param {指定传递次数} num
*/
function onlyOne(names, num) {
var queue = new Queue();
//所有名单入队
names.forEach((name) => {
queue.enqueue(name);
});
//淘汰的人名
var loser = "";
//只要还有一个以上的人在，就一直持续
while (queue.size() > 1) {
for (let i = 0; i < num; i++) {
//把每次出队的人，再次入队 ，这样一共循环了num 次（击鼓传花一共传了num次）
queue.enqueue(queue.dequeue());
}
//到这就次数就用完了，下一个就要出队了
loser = queue.dequeue();
console.log(loser + "被淘汰了");
}
//到这就剩下一个人了
return queue.dequeue();
}
var names = ["文科", "张凡", "覃军", "邱秋", "黄景"];
var winner = onlyOne(names, 99);
console.log("金马奖影帝最终获得者是：" + winner);Recommended learning: JavaScript video tutorial
The above is the detailed content of In-depth analysis of queue implementation in js (code sharing). For more information, please follow other related articles on the PHP Chinese website!
Hot AI Tools
Undresser.AI Undress
AI-powered app for creating realistic nude photos
AI Clothes Remover
Online AI tool for removing clothes from photos.
Undress AI Tool
Undress images for free
Clothoff.io
AI clothes remover
Video Face Swap
Swap faces in any video effortlessly with our completely free AI face swap tool!
Hot Article
Hot Tools
Notepad++7.3.1
Easy-to-use and free code editor
SublimeText3 Chinese version
Chinese version, very easy to use
Zend Studio 13.0.1
Powerful PHP integrated development environment
Dreamweaver CS6
Visual web development tools
SublimeText3 Mac version
God-level code editing software (SublimeText3)
Hot Topics
Recommended: Excellent JS open source face detection and recognition project
Apr 03, 2024 am 11:55 AM
Face detection and recognition technology is already a relatively mature and widely used technology. Currently, the most widely used Internet application language is JS. Implementing face detection and recognition on the Web front-end has advantages and disadvantages compared to back-end face recognition. Advantages include reducing network interaction and real-time recognition, which greatly shortens user waiting time and improves user experience; disadvantages include: being limited by model size, the accuracy is also limited. How to use js to implement face detection on the web? In order to implement face recognition on the Web, you need to be familiar with related programming languages and technologies, such as JavaScript, HTML, CSS, WebRTC, etc. At the same time, you also need to master relevant computer vision and artificial intelligence technologies. It is worth noting that due to the design of the Web side
How to use JS and Baidu Maps to implement map pan function
Nov 21, 2023 am 10:00 AM
How to use JS and Baidu Map to implement map pan function Baidu Map is a widely used map service platform, which is often used in web development to display geographical information, positioning and other functions. This article will introduce how to use JS and Baidu Map API to implement the map pan function, and provide specific code examples. 1. Preparation Before using Baidu Map API, you first need to apply for a developer account on Baidu Map Open Platform (http://lbsyun.baidu.com/) and create an application. Creation completed
Essential tools for stock analysis: Learn the steps to draw candle charts with PHP and JS
Dec 17, 2023 pm 06:55 PM
Essential tools for stock analysis: Learn the steps to draw candle charts in PHP and JS. Specific code examples are required. With the rapid development of the Internet and technology, stock trading has become one of the important ways for many investors. Stock analysis is an important part of investor decision-making, and candle charts are widely used in technical analysis. Learning how to draw candle charts using PHP and JS will provide investors with more intuitive information to help them make better decisions. A candlestick chart is a technical chart that displays stock prices in the form of candlesticks. It shows the stock price
How to create a stock candlestick chart using PHP and JS
Dec 17, 2023 am 08:08 AM
How to use PHP and JS to create a stock candle chart. A stock candle chart is a common technical analysis graphic in the stock market. It helps investors understand stocks more intuitively by drawing data such as the opening price, closing price, highest price and lowest price of the stock. price fluctuations. This article will teach you how to create stock candle charts using PHP and JS, with specific code examples. 1. Preparation Before starting, we need to prepare the following environment: 1. A server running PHP 2. A browser that supports HTML5 and Canvas 3
How to use JS and Baidu Map to implement map click event processing function
Nov 21, 2023 am 11:11 AM
Overview of how to use JS and Baidu Maps to implement map click event processing: In web development, it is often necessary to use map functions to display geographical location and geographical information. Click event processing on the map is a commonly used and important part of the map function. This article will introduce how to use JS and Baidu Map API to implement the click event processing function of the map, and give specific code examples. Steps: Import the API file of Baidu Map. First, import the file of Baidu Map API in the HTML file. This can be achieved through the following code:
How to use JS and Baidu Maps to implement map heat map function
Nov 21, 2023 am 09:33 AM
How to use JS and Baidu Maps to implement the map heat map function Introduction: With the rapid development of the Internet and mobile devices, maps have become a common application scenario. As a visual display method, heat maps can help us understand the distribution of data more intuitively. This article will introduce how to use JS and Baidu Map API to implement the map heat map function, and provide specific code examples. Preparation work: Before starting, you need to prepare the following items: a Baidu developer account, create an application, and obtain the corresponding AP
PHP and JS Development Tips: Master the Method of Drawing Stock Candle Charts
Dec 18, 2023 pm 03:39 PM
With the rapid development of Internet finance, stock investment has become the choice of more and more people. In stock trading, candle charts are a commonly used technical analysis method. It can show the changing trend of stock prices and help investors make more accurate decisions. This article will introduce the development skills of PHP and JS, lead readers to understand how to draw stock candle charts, and provide specific code examples. 1. Understanding Stock Candle Charts Before introducing how to draw stock candle charts, we first need to understand what a candle chart is. Candlestick charts were developed by the Japanese
The relationship between js and vue
Mar 11, 2024 pm 05:21 PM
The relationship between js and vue: 1. JS as the cornerstone of Web development; 2. The rise of Vue.js as a front-end framework; 3. The complementary relationship between JS and Vue; 4. The practical application of JS and Vue.
