1. A brief introduction to queues and stacks
1.1. Basic concepts of queues
Queue: It is a collection that supports first-in-first-out (FIFO), that is, the data inserted first is fetched first!
As shown in the figure below:
1.2. Basic concepts of stack
Stack: It is a collection that supports last-in-first-out (LIFO), that is, the data that is inserted later is fetched first!
As shown in the figure below:
2. Implement queues and stacks in JavaScript
In JavaScript, queues and arrays are mainly implemented through arrays. The following methods are provided in js arrays to make it easy for us to implement queues and stacks:
•shift: Delete the first element from the array and return the value of this element.
•unshift: Add one or more elements at the beginning of the array and return a new length
•push: Add an element at the end of the middle and return the new length
•pop: Delete the last element from the array and return the value of this element.
2.1. Implement queues
<script type="text/javascript">//Create an array to simulate queue var a=new Array();console.log(a);//unshift: Add one or more elements at the beginning of the array and return the new length console.log("enter");a.unshift()console.log(a);//----->a.unshift();console.log(a);//----->,a.unshift();console.log(a);//----->,a.unshift();console.log(a);//----->,a.unshift();console.log(a);//---->,,a.unshift();console.log(a);//---->,,,console .log("Exit, first in, first out");console.log(a);//pop: delete the last element from the array and return the value of this element a.pop();//----->console.log(a);a.pop();//----->console.log(a);a.pop();//----->console.log(a);a.pop();//----->console.log(a);a.pop();//----->console.log(a);</script>The output effect on the Google browser console is shown in the figure below:
2.2. Implementing the stack
<script type="text/javascript">//Create an array to simulate the stack var a=new Array();console.log(a);//push: Add one or more elements at the end of the array and return the new length console.log("stack");a.push()console.log(a);//----->a.push();console.log(a);//----->,a.push();console.log(a);//----->,a.push();console.log(a);//----->,a.push();console.log(a);//---->,,a.push();console.log(a);//---->,,,console.log(" out the stack, first out");console.log(a);//pop: delete the last element from the array and return the value of this element a.pop();//----->console.log(a);a.pop();//----->console.log(a);a.pop();//----->console.log(a);a.pop();//----->console.log(a);a.pop();//----->console.log(a);</script>The output effect on the Google browser console is shown in the figure below:
2.3. Performance testing of push method and unshift method
Array's push and unshift methods can add elements to the current array. The difference is that push is added at the end, while unshift is added at the beginning. From the principle, we can know that unshift's efficiency is relatively low. The reason is that every time it adds an element, it moves the existing element down one position. But how big is the difference in efficiency? Let’s take a simple test below.
<script type="text/javascript">/*The explanation of the trick explanation of "var s=+newDate();" in the code is as follows:=+This operator does not exist;+ is equivalent to .valueOf();+new Date() is equivalent to new Date().valueOf()//The results return the milliseconds of the current time, alert(+new Date());alert(+new Date);var s=new Date();alert(s.valueOf());alert(s.getTime());*/var arr = [ ];var startTime = +new Date(); //+new Date() is equivalent to new Date().valueOf(), returning the milliseconds of the current time// push performance test for (var i = ; i < ; i++) { arr.push(i); }var endTime = +new Date();console.log("It takes time to call the push method to add an element to the array"+(endTime-startTime)+"ms"); startTime = +new Date(); arr = [ ]; // unshift performance test for (var i = ; i < ; i++) { arr.unshift(i); }endTime = +new Date();console.log("It takes time to call the unshift method to add an element to the array"+(endTime-startTime)+"ms"); </script>This code performs 100,000 push and unshift operations respectively, and runs it once in Google browser. The result is shown in the figure below:
It can be seen that unshift is about 100 times slower than push! Therefore, you should use unshift with caution in daily life, especially for large arrays. If you have to achieve the effect of unshift, you can use Array's reverse method, which can reverse an array. First add the elements to be put into the array with push, and then execute reverse again to achieve the effect of unshift. for example:
<script type="text/javascript">//Create an array to simulate the stack var a=new Array();//Use the push method to add elements a.push()a.push();a.push();a.push();console.log("The order of elements in the array before the array is reversed");console.log(a);//---->,,,//Array has a method called reverse that can invert an array. First add the elements to be put into the array with push, and then perform reverse again, and the effect of unshift is achieved a.reverse();//Use reverse method to reverse the array console.log("The order of elements in the array after array inversion");console.log(a);</script>The output effect on the Google browser console is shown in the figure below:
Judging from the running results, the order of array elements has been reversed.
2.4. Performance testing of reverse method
What is the performance of reverse? Let’s test it again:
<script type="text/javascript">var arr = [ ], s = +new Date; for (var i = ; i < ; i++) { arr.push(i); }//Call reverse method to reverse the order of elements in the array arr.reverse(); console.log("Call reverse method to reverse the order of elements in the array: "+(+new Date - s)+"msec");</script>The output effect on the Google browser console is shown in the figure below:
From the running effect, we can see that the reverse method has extremely high performance and can be used with confidence.
The above is a summary of implementing queues and stacks through arrays in JavaScript, and I have simply tested the performance advantages and disadvantages of push, unshift, and reverse in operating large arrays.
The above is the queue and stack in the JavaScript array implementation data structure introduced by the editor. I hope it will be helpful to everyone. If you have any questions, please leave me a message and the editor will reply to everyone in time. Thank you very much for your support to Wulin.com website!