An in-depth explanation of the stack and queue operations of JavaScript arrays

Stack and Queue

To understand the operation of the stack and queue methods of JavaScript arrays, you need to first understand the basics of stacks and queues. Before continuing with the following content, let's briefly understand the concepts of stacks and queues.

Both stacks and queues are dynamic collections. In the stack, the element that can be removed is the most recently inserted one. The stack implements last-in-first-out. In a queue, the element that can be removed is always the one that has existed in the collection the longest. The queue implements a first-in-first-out policy.

Basic concept of stack

Illustration:

The stack is a LIFO (Last-In-First-Out, last-in-first-out) data structure, that is, the latest added item is the earliest to be removed. The insertion (called push) and removal (called pop) of items in the stack only occur in one location - the top of the stack.

The initial stack does not contain any data, which is called an empty stack. At this time, the top of the stack is the bottom of the stack. Then the data enters from the top of the stack, the top of the stack and the bottom of the stack are separated, and the current capacity of the entire stack becomes larger. When data is popped from the stack, the top of the stack moves down, and the current capacity of the entire stack becomes smaller.

For example, we put a lot of books in a box. If you want to take out the second book, you have to take out the first book before you can take out the second book; take out After publishing the second book, add the first book.

ECMAScript provides push() and pop() methods specifically for arrays to achieve stack-like behavior. The push() method can receive any number of parameters, add them to the end of the array one by one, and return the modified length of the array. The pop() method removes the last item from the end of the array, reduces the length value of the array, and returns the removed item.

The basic concept of queue

The access rule of the stack data structure is LIFO (last in first out), while the access rule of the queue data structure is FIFO (Fist -In-First-Out, first in, first out). Queues add items to the end of the list and remove items from the front of the list. As shown in the picture below:

#For example, if you queue up to buy tickets at a train station, those who arrive first will buy first, and those who have purchased first will leave.

The operation of entering the queue is actually appending an element to the end of the queue. It does not require any movement and the time complexity is O(1). Dequeuing is different, because we have set the position with index 0 as the head of the queue, so all elements must move forward for each dequeue operation. As shown in the figure below:

##ECMAScript specifically provides shift() and unshift()## for arrays #Method to achieve queue-like behavior. Since push() is a method that adds an array item to the end of the array, all that is needed to simulate a queue is a method that gets an array item from the front of the array. The array method that does this is shift() , which removes the first item in the array and returns it, decrementing the length of the array by one. As the name suggests, unshift() has the opposite purpose of shift(): it can add any number of array items to the front of the array and return the length of the new array. Therefore, using the

unshift()

and pop() methods simultaneously, you can simulate a queue in the opposite direction, that is, adding array items to the front of the array and removing array items from the end of the array. . <p style="box-sizing: border-box; outline: 0px; margin: 8px 0px 16px; padding: 0px; font-size: 24px; font-family: " microsoft yahei pro display roboto noto arial sc sans-serif color: rgb line-height: overflow-wrap: break-word white-space: normal background-color:><strong>push() method</strong></p> <p>This method adds one or more elements to the end of the array and returns the new length. </p> <p>The push() method can receive any number of parameters, add them to the end of the array one by one, and return the modified length of the array. For example: </p><pre class="brush:js;toolbar:false">var arr = []; //创建一个空数组 console.log(arr); // [] console.log(&quot;入栈&quot;); // 入栈 arr.push(1); // 将1添加到数组arr中 console.log(arr); // [1] arr.push(2); //将2添加到数组arr中 console.log(arr); //[1,2] arr.push([3,4]); // 将数组[3,4]添加到arr中 console.log(arr); // [1,2,[3,4]] console.log(arr.length); // 3</pre><p>The effect output in the Chrome browser console is as shown below: </p> <p><img src="https://img.php.cn/upload/image/998/417/306/1566369414626583.png" title="1566369414626583.png" alt="An in-depth explanation of the stack and queue operations of JavaScript arrays"></p> <p style="box-sizing: border-box; outline: 0px; margin: 8px 0px 16px; padding: 0px; font-size: 24px; font-family: " microsoft yahei pro display roboto noto arial sc sans-serif color: rgb line-height: overflow-wrap: break-word white-space: normal background-color:><strong>pop() method</strong></p> <p>The pop() method is just the opposite of the push() method. The pop() method deletes the last element of the array, decrements the length of the array by 1, and returns the value of the deleted element. If the array becomes empty, this method does not change the array and returns the undefined value. The following code demonstrates: </p><pre class="brush:js;toolbar:false">var arr = [1,2,3,4]; //创建一个数组 console.log(arr); // [1,2,3,4] console.log(arr.length); // 4 console.log(&quot;出栈，后进先出&quot;); // 出栈，后进先出 arr.pop(); console.log(arr); // // [1,2,3] arr.pop(); console.log(arr); // [1,2] arr.pop(); console.log(arr); // [1] arr.pop(); console.log(arr); // []</pre><p>The effect output in the Chrome browser console is as shown below: </p> <p><img src="https://img.php.cn/upload/image/592/284/759/1566369510104917.png" title="1566369510104917.png" alt="An in-depth explanation of the stack and queue operations of JavaScript arrays"></p> <p style="box-sizing: border-box; outline: 0px; margin: 8px 0px 16px; padding: 0px; font-size: 24px; font-family: " microsoft yahei pro display roboto noto arial sc sans-serif color: rgb line-height: overflow-wrap: break-word white-space: normal background-color:><strong>unshift() method</strong> </p> <p>The unshift() method adds one or more elements to the beginning of the array and returns the new length. </p><pre class="brush:js;toolbar:false">var arr = []; //创建一个空的数组 console.log(arr); // [] console.log(&quot;入队&quot;); // 入队 arr.unshift(1,2,3,4); // 将1,2,3,4推入到数组arr console.log(arr); // [1,2,3,4] console.log(arr.length); // 4</pre><p>The effect output in the Chrome browser console is as shown below: </p> <p><img src="https://img.php.cn/upload/image/842/960/563/1566369572470604.png" title="1566369572470604.png" alt="An in-depth explanation of the stack and queue operations of JavaScript arrays"></p> <p style="box-sizing: border-box; outline: 0px; margin: 8px 0px 16px; padding: 0px; font-size: 24px; font-family: " microsoft yahei pro display roboto noto arial sc sans-serif color: rgb line-height: overflow-wrap: break-word white-space: normal background-color:><strong>shift() method</strong></p> <p>The shift() method is exactly the opposite of the unshift() method. This method is used to remove the first element from the array and return the deleted value. If the array is empty, the shift() method will do nothing and return an undefined value. </p><pre class="brush:js;toolbar:false">var arr = [1,2,3,4]; // 创建一个数组 console.log(arr); // [1,2,3,4] arr.shift(); // 取得第一项 console.log(arr); // [2,3,4] arr.shift(); // 取得第一项 console.log(arr); // [3,4] arr.shift(); // 取得第一项 console.log(arr); // [4] arr.shift(); // 取得第一项 console.log(arr); // []</pre><p>The effect output in the Chrome browser console is as shown below: </p> <p><img src="https://img.php.cn/upload/image/995/366/746/1566369643403886.png" title="1566369643403886.png" alt="An in-depth explanation of the stack and queue operations of JavaScript arrays"></p> <p> Simply recall: </p> <p>1, <code>push()The method can add one or more elements to the end of the array

2, pop()The method deletes the last element in the array

3. shift() method deletes the first element in the array

4. unshift() method can add an or Multiple elements

JavaScript implements behaviors similar to stacks and queues

After understanding these methods, we can combine them to easily implement behaviors similar to stacks and queues Queue behavior.

Achieve stack-like behavior

By combining push() and pop(), we can achieve stack-like behavior:

//创建一个数组来模拟堆栈
var a=new Array();
console.log(a);
//push: 在数组的末尾添加一个或更多元素，并返回新的长度
console.log("入栈");
a.push(1)
console.log(a);//----->1
a.push(2);
console.log(a);//----->1,2
a.push(3);
console.log(a);//----->1,2,3
a.push(4);
console.log(a);//----->1,2,3,4
console.log("出栈，后进先出");
console.log(a);
//pop：从数组中把最后一个元素删除，并返回这个元素的值
a.pop();//----->4
console.log(a);
a.pop();//----->3
console.log(a);
a.pop();//----->2
console.log(a);
a.pop();//----->1
console.log(a);

The effect output in the Chrome browser console is as shown below:

实现类似队列的行为

将shift()和push()方法结合在一起，可以像使用队列一样使用数组。即在数组的后端添加项，从数组的前端移除项：

//创建一个数组来模拟队列
var a=new Array();
console.log(a);
//push: 在数组的末尾添加一个或更多元素，并返回新的长度
console.log("入队");
a.push(1)
console.log(a);//----->1
a.push(2);
console.log(a);//----->1,2
a.push(3);
console.log(a);//----->1,2,3
a.push(4);
console.log(a);//----->1,2,3,4
console.log("出队，先进先出");
console.log(a);
//shift：从数组中把第一个元素删除，并返回这个元素的值
a.shift();//----->1
console.log(a);
a.shift();//----->2
console.log(a);
a.shift();//----->3
console.log(a);
a.shift();//----->4
console.log(a);

在Chrome浏览器控制台输出的效果如下图所示：

除此之外，还可以同时使用unshift()和pop()方法，从相反的方向来模拟队列，即在数组的前端添加项，从数组的后端移除项。如下面的示例所示：

//创建一个数组来模拟队列
var a=new Array();
console.log(a);
//unshift: 在数组的前端添加一个或更多元素，并返回新的长度
console.log("入队");
a.unshift(1)
console.log(a);//----->1
a.unshift(2);
console.log(a);//----->2,1
a.unshift(3);
console.log(a);//----->3,2,1
a.unshift(4);
console.log(a);//----->4,3,2,1
console.log("出队，先进先出");
console.log(a);
//pop：从数组中把最一个元素删除，并返回这个元素的值
a.pop();//----->4
console.log(a);
a.pop();//----->3
console.log(a);
a.pop();//----->2
console.log(a);
a.pop();//----->1
console.log(a);

在Chrome浏览器控制台输出的效果如下图所示：

push()方法和unshift()方法的性能测试

Array的push()与unshift()方法都能给当前数组添加元素，不同的是，push()是在末尾添加，而unshift()则是在开头添加，从原理就可以知道，unshift()的效率是较低的。原因是，它每添加一个元素，都要把现有元素往下移一个位置。但到底效率差异有多大呢?下面来简单测试一下。

/*
关于代码中"var s=+newDate();"的技巧说明
解释如下:=+这个运算符是不存在的;
+相当于.valueOf();
+new Date()相当于new Date().valueOf()
//4个结果一样返回当前时间的毫秒数
  alert(+new Date());
  alert(+new Date);
  var s=new Date();
  alert(s.valueOf());
  alert(s.getTime());
*/
var arr = [ ];
var startTime = +new Date(); //+new Date()相当于new Date().valueOf()，返回当前时间的毫秒数
// push性能测试 
for (var i = 0; i < 100000; i++) { 
　　arr.push(i); 
}
var endTime = +new Date();
console.log("调用push方法往数组中添加100000个元素耗时"+(endTime-startTime)+"毫秒"); 
 
startTime = +new Date(); 
arr = [ ]; 
// unshift性能测试 
for (var i = 0; i < 100000; i++) { 
　　arr.unshift(i); 
}
endTime = +new Date();
console.log("调用unshift方法往数组中添加100000个元素耗时"+(endTime-startTime)+"毫秒");

这段代码分别执行了100000次push()和unshift()操作，在chrome浏览器运行一次，得到的结果如下图所示：

可见，unshift()比push()要慢差不多100倍!因此，平时还是要慎用unshift()，特别是对大数组。那如果一定要达到unshift()的效果，可以借助于Array的reverse()方法，Array的reverse()的方法能够把一个数组反转。先把要放进数组的元素用push()添加，再执行一次reverse()，就达到了unshift()的效果。比如：

//创建一个数组来模拟堆栈
var a=new Array();
//使用push方法在数组的末尾添加元素
a.push(1)
a.push(2);
a.push(3);
a.push(4);
console.log("数组反转之前数组中的元素顺序");
console.log(a);//----->1,2,3,4
//Array有一个叫做reverse的方法，能够把一个数组反转。先把要放进数组的元素用push添加，再执行一次reverse，就达到了unshift的效果
a.reverse();//使用reverse方法将数组进行反转
console.log("数组反转之后数组中的元素顺序");
console.log(a);

在chrome浏览器控制台输出的效果如下图所示：

从运行结果来看，数组元素的顺序已经反转过来了。

reverse()方法的性能测试

var arr = [ ], s = +new Date; 
for (var i = 0; i < 100000; i++) { 
　　    arr.push(i); 
}
//调用reverse方法将数组里面的100000元素的顺序反转
arr.reverse(); 
console.log("调用reverse方法将数组里面的100000元素的顺序反转耗时："+(+new Date - s)+"毫秒");

在chrome浏览器控制台输出的效果如下图所示：

总结

本文主要介绍了JavaScript数组的push()、pop()、shift()和unshift()方法。并且如何通过组合这几种方法实现类似栈和队例的行为。

js中删除堆栈：

1:js中的splice方法

splice(index,len,[item])    注释：该方法会改变原始数组。

splice有3个参数，它也可以用来替换/删除/添加数组内某一个或者几个值

index:数组开始下标        len: 替换/删除的长度       item:替换的值，删除操作的话 item为空

如：arr = ['a','b','c','d']

删除 ----  item不设置

arr.splice(1,1)   //['a','c','d']         删除起始下标为1，长度为1的一个值，len设置的1，如果为0，则数组不变

arr.splice(1,2)  //['a','d']          删除起始下标为1，长度为2的一个值，len设置的2

替换 ---- item为替换的值

arr.splice(1,1,'ttt') //['a','ttt','c','d'] Replace the starting index with 1 and a value with length 1 as ' ttt', 1

arr.splice(1,2,'ttt') set by len The two values ​​​​of 2 are 'ttt', the 1

set by len is added---- len is set to 0, and item is the added value

arr.splice(1,0,' ttt') //['a','ttt','b','c','d'] means adding an item 'ttt' at the subscript 1

It seems that splice is the most convenient La

2: delete After delete deletes an element in the array, the subscripted value will be set to undefined, and the length of the array will not change

For example: delete arr[1] //['a', ,'c','d'] There are two commas in the middle, the length of the array remains unchanged, and one item is undefined

I hope this article can help students who are new to JavaScript, something is wrong Please point it out, it would be greatly appreciated!

For more JavaScript-related questions, please visit the PHP Chinese website: https://www.php.cn/

The above is the detailed content of An in-depth explanation of the stack and queue operations of JavaScript arrays. For more information, please follow other related articles on the PHP Chinese website!