栈

数据结构和算法在规划程序数据存储、读取和计算效率上，有着非常大的重要性。好的数据结构和算法，能让程序的执行效率呈指数级增加，不好的则会让效率指数级下降，所以程序员需要掌握常见的数据结构和算法。另外，它们在面试中也是不可避免的一环。这期视频作为数据结构和算法的第一期，先看一个最简单的数据结构，栈，的定义和实现。因为视频主要是前端相关，所以我们的数据结构和算法会用 JavaScript 语言实现。

定义

栈是一种线性的、后进先出的数据结构。线性指的是和数组一样，栈中的数据只有一个维度，每个元素依次排列。后进先出指的是，最后添加到栈中的元素，会第一个从栈中取出来。 JavaScript 的函数调用栈就是用栈来实现的，另外也可以用栈实现带小括号的数学表达式的计算。 栈的基本操作有 push() 入栈和 pop() 出栈两个，入栈会把元素添加到栈的顶部，栈的大小加 1，出栈则会把栈顶的元素弹出，栈的大小减 1。另外根据栈的应用，它还可以有：

• 判断栈是否为空。
• 获取栈的大小。
• 查看栈顶元素。

等方法。

JavaScript 实现

根据栈的特点，我们可以用 JavaScript 代码实现它，因为 JavaScript 的数组本身就支持栈模式，我们可以对它进行包装。

1. 定义一个 Stack Class：

class Stack {}

2. 在里边定义一个数组成员变量，保存栈内部的数据：

class Stack {
  stack = [];
}

3. 接下来看一下每个操作的实现方式，先看一下 push()，把一个元素添加到栈的顶部，它：
   • 接收一个要添加的元素作为参数。
   • 调用数组 push() 方法，把新元素 item 添加到内部的 stack 数组中。

push(item) {
  this.stack.push(item);
}

4. pop() 方法移除栈顶部的元素，并返回，因为数组的 pop() 方法已经实现了这个功能，所以直接调用它，不过在调用之前先判断了当前栈是否为空，如果为空，返回“栈为空”字样：

 pop() {
    return this.isEmpty() ? "栈为空" : this.stack.pop();
 }

5. isEmpty() 方法判断了栈是否已经清空，这里调用了 size() 方法，获取栈的长度，检查它是否为 0：

  isEmpty() {
    return this.size() === 0;
  }

6. size() 方法返回栈的大小，这里返回 stack 数组的 length 属性：

size() {
  return this.stack.length;
}

7. peek() 方法返回栈顶元素，但并不从栈中弹出，这里直接返回 stack 数组的最后一个元素：

peek() {
  return this.stack[this.stack.length - 1];
}

运行示例

我们使用 Stack 类，来编写一些栈的操作示例：

1. 初始化一个 Stack 对象。
2. 使用 push() 添加元素 1， 5， 7 到栈中。
3. 调用 peek() 查看栈顶元素，为 7，注意 peek() 不会把元素从栈中弹出。
4. 调用 size() 查看栈的大小，此时为 3。
5. 调用 pop() 弹出一个栈顶元素，7。
6. 再调用 size() 查看栈的大小，此时为 2。
7. 最后调用 3 次 pop() ，其中前两次执行后，就会把栈中的元素全部弹出，最后一次调用时栈已经为空了，会输出“栈为空”。

let stack = new Stack();
stack.push(1);
stack.push(5);
stack.push(7);
console.log(stack.peek());
console.log(stack.size());

console.log(stack.pop());
console.log(stack.size());
console.log(stack.pop());
console.log(stack.pop());
console.log(stack.pop());

执行结果是：

7;
3;
7;
2;
5;
1;
栈为空;

小结

好了，这个就是栈数据结构的定义、操作和 JavaScript 实现，你学会了吗？如果有帮助请三连，想学更多有用的前端开发知识，请关注峰华前端工程师，感谢观看！