数据结构与算法JS描述之栈和队列

参考资料

数据结构与算法JS描述，[美] Michael McMillan 著，王群锋 杜欢 译

写在前面

写该系列的博客，初衷是帮助自己和初学者，奠定更高层次的编程基础和理念，能让大家对 JS 有更深层次的认知，并且借助 JS 了解高级的编程思想。

所有对于某个数据结构的算法的示范，并不是标准答案，只是我根据经验模仿了各种资料和其他成熟语言中的写法，如果有写的不精致的地方，或者更好的写法，联系我，我加以改正。

本来想用构造函数的形式实现这些数据结构，但是既然技术在更新，用新的语法可能更好一点。所以所有的代码实现方式都是 ES6+ 的代码。

一、什么是栈，什么是队列

1. 栈

• 栈是数据临时存储的地方，是一个动态内存区域
• 栈是只能在一端进行插入和删除操作的特殊线性表
• 栈按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶
• 栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针
• 需要读数据的时候从栈顶开始弹出数据，最后一个数据被第一个读出来
• 所以栈被称为一种后入先出的数据结构（LIFO，Last-In-First-Out）
• 允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)
• 栈底固定，而栈顶浮动
• 插入一般称为进栈（PUSH），删除则称为退栈（POP）
• 栈中元素个数为零时称为空栈

在前端开发的过程中，我们很少遇见一批数据需要用栈这种数据结构来管理，所以对于栈的概念比较淡薄，其实有一个非常形象的栈的例子，就是递归。还有函数的调用、执行都在栈里，闭包也跟栈有关系。

栈在程序的运行中有着举足轻重的作用。最重要的是栈保存了一个函数调用时所需要的维护信息，这常常称之为堆栈帧或者活动记录。堆栈帧一般包含两个重要的信息，函数的返回地址和参数和临时变量：包括函数的非静态局部变量以及编译器自动生成的其他临时变量。

这里我找到了一个非常具体的介绍 JS 函数执行栈的例子，感谢作者的分享，真心建议大家一看，作者写的特别好。

栈的概述图

2. 队列

• 队列和栈一样，都是一种受限制的线性数据结构
• 队列只允许在列表的前端进行删除操作，在表的后端进行插入操作
• 进行插入操作的一端成为队尾，进行删除操作的一端成为队头
• 在队列中插入一个队列元素成为入队，删除一个元素称为出队
• 最早入队的元素最早出队，所以队列被称为先进先出表（FIFO，First-In-First-Out）
• 队列中没有元素时，成为空队列

相对于栈，对于队列这种数据结构，我们可能要较为熟悉一点，但也并不常用，这里举一个队列相关的列子，就是传统的贪吃蛇游戏，写过这个游戏的人应该都知道，蛇在背景上移动的基础逻辑是，头部添加新的元素，尾部删除旧的元素。

队列的概述图

其实概念搞清楚了之后，代码实现很简单的。但是由于 JS 语言本身的特点，我们写的代码如果完全按照我们的规定去执行，那就能体现出这种概念性，但是如果随意操作，那这个概念性就没那么强烈了，就像类，抽象类，类的 getter 和 setter 一样。

二、用 JS 实现栈及其基础算法

1. 栈需要实现的基本算法

• top 属性，保留栈顶的位置，要在栈内做操作时，通过 top 找到栈顶的位置，做操作
• push 方法，从栈顶向栈内添加新元素（入栈）
• pop 方法，从栈顶删除元素（出栈）
• peek 方法，读取栈顶的元素，其实可以在 pop 的同时拿到栈顶的元素，但是一定会删除，有时候不需要删除，只想读取栈顶的元素
• clear 方法，清空栈

2. 代码

class Stack {
  top = 0; // 栈顶的位置
  data = []; // 数据源

  push(el) {
    this.data[this.top] = el;
    this.top++;

    // 简写: this.data[this.top++] = el;
  }

  pop() {
    const lastEl = this.data[this.top - 1];
    this.data[--this.top] = null;
    return lastEl;
  }

  peek() {
    return this.data[this.top - 1];
  }

  clear() {
    this.data = [];
    this.top = 0;
  }
}

三、用 JS 实现队列及其基础算法

1. 队列需要实现的基本算法

• front 属性，队头的位置
• end 属性，队尾的位置
• first 方法，读取队首的元素
• last 方法，读取队尾的元素
• shift 方法，从队首删除一个元素
• push 方法，向队尾添加一个元素

2. 代码

class Queue {
  front = 0; // 队头的位置
  end = 1; // 队尾的位置
  data = [45, 67, 89, 90]; // 数据源

  push(el) {
    this.data[this.end++] = el;
  }

  shift() {
    const firstEl = this.data[this.front];
    this.data[this.front++] = null;
    return firstEl;
  }

  first() {
    return this.data[this.front];
  }

  last() {
    return this.data[this.end - 1];
  }

  clear() {
    this.data = [];
    this.front = 0;
    this.end = 1;
  }
}

代码太简单了，所以我就没有写注释，但是重要的是我们要借助这些代码理解栈和队列这种数据结构。

扫码领取 Web 前端直播课免费学习名额，或进入前端技术交流群

其他文章链接:
JS 常见算法的解析和代码实现
Vue 利用 addRoutes 动态创建路由，并在页面刷新后保留动态路由的完整 Demo
React脚手架（5）Props和PropTypes检查类型
Vue 数据双向响应机制
Vue-cli 请求代理配置，封装 Axios 及请求拦截器和响应拦截器
Vue-cli + Element-UI 利用递归动态生成菜单栏