怒肝 JavaScript 数据结构 — 栈篇 (一)

大家好，我是杨成功。

前面两篇我们学习了最简单的数据结构 —— 数组，数组是最基本的数据集合，它提供了非常灵活的操作方式，可以任意添加，需改，删除数组项。

从这篇开始，我们学习一个新的数据结构 —— 栈。栈其实本质上也是一个数组，只不过它并没有数组那么灵活，栈有自己的存储和操作数据的规则，算是在数组的基础上加了一层限制。

这个规则你肯定不陌生，概括起来就四个字 —— 后进先出。

什么是栈？

定义：栈是一种遵从 后进先出 原则的有序集合。

后进先出的英文名叫 LIFO，这个也得记一下，保不定有面试官会整个洋词儿问你，你可别懵了。

后进先出的意思是，一组数据按照先后顺序排队被添加到数组当中，当需要取出（删除）的时候，最后进入的数据先被取出，最先进入的最后一个被取出。

除了后进先出的规则，还有一点是“有序集合”。有序的意思是这个集合是有顺序的，顺序不能乱，像数组中的排序功能，在栈里肯定没有，因为栈是不允许改变顺序的。

举个例子：你去食堂打饭时看到的一摞餐盘，就可以看作是典型的栈。

栈有两个端，以一摞餐盘为例，最上面的盘子就处在这个栈的栈顶，而最底下的盘子就在栈的栈底。所以不管你是放盘子还是取盘子，永远是栈顶的一端先被使用，栈底的最后使用。

这也印证了栈的原则：后进先出，先进后出。

我们用一个数组 ['北京','上海','成都'] 来表示栈，画一张图可以更清晰的了解栈的结构：

可见，在数组中，第一个元素是栈底，最后一个元素是栈顶，切记不能搞混。

除此之外，栈也被用在编程语言的保存变量，方法调用当中。比如 JavaScript 中的“函数调用栈”，以及浏览器的返回记录，这都是栈的应用。

实现一个栈

上面我们介绍了栈的概念，以及栈的特性和原则是什么。然而 JavaScript 中并没有原生提供“栈”这种数据类型，那我们就基于数组，自己实现一个表示栈的类。

class Stack {  constructor() {    this.lists = []  }}

上述代码用一个 lists 属性来保存栈里的数据，默认值为空数组。按照 LIFO 原则，还需要在这个类中创建一些方法，来指定栈的进/出操作。方法如下：

• push()：添加新元素到栈顶

• pop()：移除栈顶底新元素

• peek()：返回栈顶底元素

• isEmpty()：判断栈里是否有元素，没有则返回 true

• clear()：清除栈里的所有元素

• size()：返回栈里元素的数量

其实这几个方法比较简单，我们直接上代码：

class Stack {  constructor() {    this.lists = []  }  // 入栈  push(item) {    this.lists.push(item)  }  // 出栈  pop() {    this.lists.pop()  }  peek() {    this.lists[this.lists.length - 1]  }  isEmpty() {    return this.lists.length == 0  }  clear() {    this.lists = []  }  size() {    return this.lists.length  }}

这里值得一说的是 JavaScript 原生的 push 和 pop 方法，这俩方法就是按照栈的原则设计的。push 叫入栈，向栈顶添加新元素；pop 叫出栈，移除栈顶的第一个元素，所以我们直接用这两方法即可。

定义好了 Stack 类，我们来使用一下：

var stack = new Stack()console.log(stack.isEmpty()) // true

然后再执行入栈操作：

stack.push('北京')stack.push('上海')console.log(stack.size()) // 2console.log(stack.peek()) // '上海'

再添加一个：

stack.push('成都')console.log(stack.size()) // 3console.log(stack.peek()) // '成都'console.log(stack.lists) // ['北京', '上海', '成都']

目前栈里有三个元素，我们做一次出栈：

stack.pop()console.log(stack.size()) // 2console.log(stack.lists) // ['北京', '上海']

你看，“成都” 是最后被添加进来的，也是最先被移出去的。

还有优化空间吗？

上面我们基于 ES6 的 Class 语法，将数据保存在数组中，模拟了栈的操作方法，基本实现了一个自定义的栈。

但是还要考虑一个问题：如果这个数组非常大，有 1000 条数据，会不会有什么问题？

这里要科普一个小知识：在数组中查询，操作元素，不管用什么方法，本质都是要遍历数组，直到找到目标元素。这样的话，如果数组非常大，那么查询的效率就会很低。再加上数组会保证元素的排列顺序，因而占用内存也更多。

那有没有方法能直接获取和操作元素，不需要遍历，并且实现上述栈的所有功能呢？当然有，就是我们的 JavaScript 对象了。

下一篇，我们用 JavaScript 对象来实现一个栈。

加入学习群

本文来源公众号：程序员成功。这是学习 JavaScript 数据结构与算法的第 3 篇，本系列会连续更新一个月，欢迎关注公众号，点击“加群”一起加入我们的学习队伍～