跳到主要内容位置

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

定义#

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

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

等方法。

JavaScript 实现#

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

  1. 定义一个 Stack Class:
class Stack {}
  1. 在里边定义一个数组成员变量,保存栈内部的数据:
class Stack {  stack = [];}
  1. 接下来看一下每个操作的实现方式,先看一下 push(),把一个元素添加到栈的顶部,它:
    • 接收一个要添加的元素作为参数。
    • 调用数组 push() 方法,把新元素 item 添加到内部的 stack 数组中。
push(item) {  this.stack.push(item);}
  1. pop() 方法移除栈顶部的元素,并返回,因为数组的 pop() 方法已经实现了这个功能,所以直接调用它,不过在调用之前先判断了当前栈是否为空,如果为空,返回“栈为空”字样:
 pop() {    return this.isEmpty() ? "栈为空" : this.stack.pop(); }
  1. isEmpty() 方法判断了栈是否已经清空,这里调用了 size() 方法,获取栈的长度,检查它是否为 0:
  isEmpty() {    return this.size() === 0;  }
  1. size() 方法返回栈的大小,这里返回 stack 数组的 length 属性:
size() {  return this.stack.length;}
  1. 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 实现,你学会了吗?如果有帮助请三连,想学更多有用的前端开发知识,请关注峰华前端工程师,感谢观看!