JavaScript 배열의 스택 및 큐 작업에 대한 심층적인 설명
- 王林앞으로
- 2019-08-21 15:02:362848검색
Stacks and Queues
JavaScript 배열의 스택 및 대기열 메서드 작동을 이해하려면 먼저 스택과 대기열의 기본 사항을 이해해야 합니다. 다음 내용을 계속하기 전에 스택과 큐의 개념을 간략하게 이해해 보겠습니다.
스택과 큐는 모두 동적 컬렉션입니다. 스택에서 제거할 수 있는 요소는 가장 최근에 삽입된 요소입니다. 스택은 후입선출 방식을 구현합니다. 대기열에서 제거할 수 있는 요소는 항상 컬렉션에 가장 오랫동안 존재했던 요소입니다. 대기열은 선입선출 정책을 구현합니다.
스택의 기본 개념
그림:
스택은 LIFO(Last-In-First-Out, Last-In-First-Out) 데이터 구조입니다. 가장 최근에 추가된 항목이 가장 먼저 제거되었습니다. 스택에 있는 항목의 삽입(푸시라고 함) 및 제거(팝이라고 함)는 스택의 맨 위 위치에서만 발생합니다. LIFO（Last-In-First-Out，后进先出）的数据结构，也就是最新添加的项最早被移除。而栈中项的插入（叫做推入）和移除（叫做弹出），只发生在一个位置——栈的顶部。
最开始栈中不含有任何数据，叫做空栈，此时栈顶就是栈底。然后数据从栈顶进入，栈顶栈底分离，整个栈的当前容量变大。数据出栈时从栈顶弹出，栈顶下移，整个栈的当前容量变小。
比如说，我们在一个箱子中放了很多本书，如果你要拿出第二书，那么你要先把第一本书拿出来，才能拿第二本书出来；拿出第二本书之后，再把第一本书放进去。
ECMAScript为数组专门提供了 push()和 pop()方法，以便实现类似栈的行为。 push() 方法可以接收任意数量的参数，把它们逐个添加到数组末尾，并返回修改后数组的长度。而 pop() 方法则从数组末尾移除最后一项，减少数组的length值，然后返回移除的项。
队列的基本概念
栈数据结构的访问规则是LIFO(后进先出)，而队列数据结构的访问规则是FIFO(Fist-In-First-Out,先进先出)。队列在列表的末端添加项，从列表的前端移除项。如下图所示：
比如说火车站排队买票，先到的先买，买好的先走。
入队列操作其实就是在队尾追加一个元素，不需要任何移动，时间复杂度为O(1)。出队列则不同，因为我们已经架设下标为0的位置是队列的队头，因此每次出队列操作所有元素都要向前移动。如下图所示：
ECMAScript为数组专门提供了 shift()和 unshift()方法，以便实现类似队列的行为。由于 push() 是向数组末端添加数组项的方法，因此要模拟队列只需一个从数组前端取得数组项的方法。实现这一操作的数组方法就是 shift() ，它能够移除数组中的第一个项并返回该项，同时将数组长度减1。
顾名思义， unshift() 与 shift() 的用途相反：它能在数组前端添加任意个数组项并返回新数组的长度。因此，同时使用 unshift() 和 pop()
ECMAScript는 스택과 같은 동작을 달성하기 위해 배열에 대한 push() 및 pop() 메서드를 구체적으로 제공합니다. push() 메소드는 원하는 수의 매개변수를 수신하고, 이를 배열의 끝에 하나씩 추가하고, 수정된 배열 길이를 반환할 수 있습니다. pop() 메서드는 배열 끝에서 마지막 항목을 제거하고 배열 길이를 줄인 후 제거된 항목을 반환합니다. 🎜🎜🎜큐의 기본 개념🎜🎜🎜스택 데이터 구조의 접근 규칙은 LIFO(후입선출)이고, 큐 데이터 구조의 접근 규칙은 FIFO(Fist-In-First-Out, 선입선출). 대기열은 목록 끝에 항목을 추가하고 목록 앞쪽에서 항목을 제거합니다. 아래 그림과 같이: 🎜🎜🎜🎜예를 들어, 기차역에서 표를 사기 위해 줄을 서면, 먼저 도착한 사람이 먼저 사고, 먼저 구입한 사람이 먼저 떠납니다. 🎜🎜큐 작업은 실제로 큐 끝에 요소를 추가하며 이동이 필요하지 않으며 시간 복잡도는 O(1)입니다. 대기열 제거는 인덱스 0의 위치를 대기열의 헤드로 설정했기 때문에 대기열 제거 작업마다 모든 요소가 앞으로 이동해야 하기 때문에 다릅니다. 아래 그림과 같이: 🎜🎜🎜🎜ECMAScript는 대기열과 같은 동작을 달성하기 위해 배열에 대한 shift() 및 unshift() 메서드를 구체적으로 제공합니다. push()는 배열의 끝에 배열 항목을 추가하는 메서드이므로, 대기열을 시뮬레이션하는 데 필요한 것은 배열의 앞쪽에서 배열 항목을 가져오는 메서드뿐입니다. 이를 수행하는 배열 메소드는 배열의 첫 번째 항목을 제거하고 이를 반환하며 배열의 길이를 1씩 감소시키는 Shift()입니다. 🎜🎜이름에서 알 수 있듯이 unshift()는 Shift()와 반대되는 목적을 가지고 있습니다. 즉, 배열 앞에 원하는 수의 배열 항목을 추가하고 새 배열의 길이를 반환할 수 있습니다. 따라서 unshift() 및 pop() 메서드를 동시에 사용하면 반대 방향, 즉 배열 항목을 배열 앞에 추가하는 대기열을 시뮬레이션할 수 있습니다. 배열 항목의 끝에서 제거합니다. 🎜push() 메서드
이 메서드는 배열 끝에 하나 이상의 요소를 추가하고 새 길이를 반환합니다.
push() 메서드는 원하는 수의 매개변수를 수신하고 이를 배열 끝에 하나씩 추가하고 수정된 배열의 길이를 반환할 수 있습니다. 예: Chrome 브라우저 콘솔에서
var arr = []; //创建一个空数组
console.log(arr); // []
console.log("入栈"); // 入栈
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출력의 효과는 아래와 같습니다.
pop() 메서드
pop() 메서드는 push() 메서드와 정반대입니다. pop() 메서드는 배열의 마지막 요소를 삭제하고 배열의 길이를 1만큼 감소시킨 후 삭제된 요소의 값을 반환합니다. 배열이 비어 있으면 이 메서드는 배열을 변경하지 않고 정의되지 않은 값을 반환합니다. 다음 코드는 다음을 보여줍니다.
var arr = [1,2,3,4]; //创建一个数组
console.log(arr); // [1,2,3,4]
console.log(arr.length); // 4
console.log("出栈，后进先出"); // 出栈，后进先出
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); // []Chrome 브라우저 콘솔의 효과 출력은 아래와 같습니다.
unshift() 메서드
unshift() 메서드는 시작 부분에 하나 이상의 요소를 추가하는 것입니다. 배열을 반환하고 새 길이를 반환합니다. Chrome 브라우저 콘솔에서
var arr = []; //创建一个空的数组
console.log(arr); // []
console.log("入队"); // 入队
arr.unshift(1,2,3,4); // 将1,2,3,4推入到数组arr
console.log(arr); // [1,2,3,4]
console.log(arr.length); // 4출력의 효과는 다음과 같습니다.
shift() 메서드
shift() 메서드는 unshift() 메서드와 정확히 반대입니다. 이 메서드는 배열에서 첫 번째 요소를 제거하고 삭제된 값을 반환하는 데 사용됩니다. 배열이 비어 있으면 Shift() 메서드는 아무 작업도 수행하지 않고 정의되지 않은 값을 반환합니다.
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); // []
Chrome 브라우저 콘솔의 출력 효과는 다음과 같습니다.
간단히 기억하자면:
1 push() 메서드는 끝에 값을 추가할 수 있습니다. 2. pop() 메서드는 배열의 마지막 요소를 삭제합니다push()方法可以在数组的末属添加一个或多个元素
2、pop()方法把数组中的最后一个元素删除
3、shift()方法把数组中的第一个元素删除
4、unshift()
shift() 메서드는 배열의 첫 번째 요소를 삭제합니다. 배열 삭제 4 unshift() 메서드는 배열 앞에 하나 이상의 요소를 추가할 수 있습니다.
JavaScript는 스택 및 대기열과 유사한 동작을 구현합니다.
이러한 메서드를 이해한 후 우리는 그것들을 결합하여 스택 및 대기열과 같은 동작을 쉽게 구현할 수 있습니다.
스택과 유사한 동작 달성
push()와 pop()을 결합하여 스택과 같은 동작을 달성할 수 있습니다.//创建一个数组来模拟堆栈
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);
Chrome 브라우저 콘솔의 효과 출력은 다음과 같습니다. 🎜🎜🎜实现类似队列的行为
将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'] 시작 인덱스를 1로 바꾸고 길이가 1인 값을 'ttt' , len으로 바꿉니다. is set to 1
arr.splice(1,2,'ttt') //['a','ttt','d'] 두 값을 시작 첨자 1, 길이 2를 '로 바꿉니다. ttt', len이 1로 설정됨
add---- len이 0으로 설정됨, 항목이 추가된 값
arr.splice(1,0,'ttt') //['a','ttt' , 'b','c','d'] 첨자에 'ttt' 항목을 추가한다는 의미 1
splice가 가장 편리한 것 같습니다
2: delete 배열의 요소를 삭제한 후 delete를 하면 Set이 됩니다. 아래 첨자 값은 정의되지 않으며 배열 길이는 변경되지 않습니다. 예: delete arr[1] //['a',,'c','d'] 중간에 두 개의 쉼표가 나타나면 길이가 변경됩니다. 배열은 변경되지 않습니다. , 하나의 항목이 정의되지 않았습니다
이 기사가 JavaScript를 처음 접하는 학생들에게 무엇이 잘못되었는지 지적해 주시기 바랍니다.
JavaScript 관련 질문이 더 필요하시면 PHP 중국어 웹사이트를 방문하세요:
https://www.php.cn/위 내용은 JavaScript 배열의 스택 및 큐 작업에 대한 심층적인 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!