大家好，我是讯享网，很高兴认识大家。



讯享网

1. 基础知识就像是一座大楼的地基，它决定了我们的技术高度。
2. 我们应该多掌握一些可移值的技术或者再过十几年应该都不会过时的技术，数据结构与算法就是其中之一。

栈、队列、链表、堆 是数据结构与算法中的基础知识，是程序员的地基。

笔者写的 JavaScript 数据结构与算法之美 系列用的语言是 JavaScript ，旨在入门数据结构与算法和方便以后复习。

线性表（Linear List）：就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。数组、链表、队列、栈 等就是线性表结构。

非线性表：数据之间并不是简单的前后关系。二叉树、堆、图 就是非线性表。

本文主要讲线性表，非线性表会在后面章节讲。

• 数组 (Array) 是一个有序的数据集合，我们可以通过数组名称 (name) 和索引 (index) 进行访问。
• 数组的索引是从 0 开始的。

• 数组是用一组连续的内存空间来存储的。

所以数组支持 随机访问，根据下标随机访问的时间复杂度为 O(1)。

• 低效的插入和删除。

但是因为 JavaScript 是弱类型的语言，弱类型则允许隐式类型转换。

隐式：是指源码中没有明显的类型转换代码。也就是说，一个变量，可以赋值字符串，也可以赋值数值。

讯享网

你还可以直接让字符串类型的变量和数值类型的变量相加，虽然得出的最终结果未必是你想象的那样，但一定不会报错。

讯享网

数组的每一项可以是不同的类型，比如：

定义的数组的大小是可变的，不像强类型语言，定义某个数组变量的时候就要定义该变量的大小。

讯享网

JavaScript 原生支持数组，而且提供了很多操作方法，这里不展开讲。

1. 后进者先出，先进者后出，简称 后进先出（LIFO），这就是典型的结构。
2. 新添加的或待删除的元素都保存在栈的末尾，称作，另一端就叫。
3. 在栈里，新元素都靠近栈顶，旧元素都接近栈底。
4. 从栈的操作特性来看，是一种 的线性表，只允许在一端插入和删除数据。
5. 不包含任何元素的栈称为。

栈也被用在编程语言的编译器和内存中保存变量、方法调用等，比如函数的调用栈。

栈的方法：

• push(element)：添加一个（或几个）新元素到栈顶。
• pop()：移除栈顶的元素，同时返回被移除的元素。
• peek()：返回栈顶的元素，不对栈做任何修改。
• isEmpty()：如果栈里没有任何元素就返回 true，否则返回 false。
• clear()：移除栈里的所有元素。
• size()：返回栈里的元素个数。

测试：

讯享网

栈的应用实例：JavaScript 数据结构与算法之美 - 实现一个前端路由，如何实现浏览器的前进与后退 ？

定义

• 队列是遵循 FIFO（First In First Out，先进先出）原则的一组有序的项。
• 队列在尾部添加新元素，并从顶部移除元素。
• 最新添加的元素必须排在队列的末尾。
• 队列只有 入队 push() 和出队 pop()。

实现

队列里面有一些声明的辅助方法：

• enqueue(element)：向队列尾部添加新项。
• dequeue()：移除队列的第一项，并返回被移除的元素。
• front()：返回队列中第一个元素，队列不做任何变动。
• isEmpty()：如果队列中不包含任何元素，返回 true，否则返回 false。
• size()：返回队列包含的元素个数，与数组的 length 属性类似。
• print()：打印队列中的元素。
• clear()：清空整个队列。

代码：

测试：

讯享网

定义

优先队列中元素的添加和移除是依赖的。

应用

• 一个现实的例子就是机场登机的顺序。头等舱和商务舱乘客的优先级要高于经济舱乘客。
• 再比如：火车，老年人、孕妇和带小孩的乘客是享有优先检票权的。

优先队列分为两类

• 最小优先队列
• 最大优先队列

实现

实现一个优先队列，有两种选项：

• 1. 设置优先级，根据优先级正确添加元素，然后和普通队列一样正常移除
• 1. 设置优先级，和普通队列一样正常按顺序添加，然后根据优先级移除

这里最小优先队列和最大优先队列我都采用第一种方式实现，大家可以尝试一下第二种。

下面只重写 enqueue() 方法和 print() 方法，其他方法和上面的普通队列完全相同。

实现最小优先队列

实现最小优先队列 enqueue() 方法和 print() 方法：

讯享网

最小优先队列测试：

实现最大优先队列

讯享网

最大优先队列测试：

定义

循环队列，顾名思义，它长得像一个环。把它想像成一个圆的钟就对了。

关键是：确定好队空和队满的判定条件。

循环队列的一个例子就是击鼓传花游戏（Hot Potato）。在这个游戏中，孩子们围城一个圆圈，击鼓的时候把花尽快的传递给旁边的人。某一时刻击鼓停止，这时花在谁的手里，谁就退出圆圈直到游戏结束。重复这个过程，直到只剩一个孩子（胜者）。

下面我们在普通队列的基础上，实现一个模拟的击鼓传花游戏，下面只写击鼓传花的代码片段：

讯享网

执行结果为：

队列小结

一些具有某些额外特性的队列，比如：循环队列、阻塞队列、并发队列。它们在很多偏底层系统、框架、中间件的开发中，起着关键性的作用。

以上队列的代码要感谢 leocoder351。

• 链表存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的，它是通过 指针 将 零散的内存块 串连起来的。
• 每个元素由一个存储元素本身的 节点 和一个指向下一个元素的 引用（也称指针或链接）组成。

简单的链接结构图：

• 链表是通过指针将零散的内存块串连起来的。

所以链表不支持 随机访问，如果要找特定的项，只能从头开始遍历，直到找到某个项。
所以访问的时间复杂度为 O(n)。

• 高效的插入和删除。

三种最常见的链表结构，它们分别是：

• 单链表
• 双向链表
• 循环链表

定义

由于链表的起始点的确定比较麻烦，因此很多链表的实现都会在链表的最前面添加一个特殊的节点，称为 头节点，表示链表的头部。

经过改造，链表就成了如下的样子：

针对链表的插入和删除操作，我们只需要考虑相邻结点的指针改变，所以插入与删除的时间复杂度为 O(1)。

在 d2 节点后面插入 d4 节点：

删除 d4 节点：

实现

• Node 类用来表示节点。
• LinkedList 类提供插入节点、删除节点等一些操作。

单向链表的八种常用操作：

• append(element)：尾部添加元素。
• insert(position, element)：特定位置插入一个新的项。
• removeAt(position)：特定位置移除一项。
• remove(element)：移除一项。
• indexOf(element)：返回元素在链表中的索引。如果链表中没有该元素则返回 -1。
• isEmpty()：如果链表中不包含任何元素，返回 true，如果链表长度大于 0，返回 false。
• size()：返回链表包含的元素个数，与数组的 length 属性类似。
• getHead()：返回链表的第一个元素。
• toString()：由于链表使用了 Node 类，就需要重写继承自 JavaScript 对象默认的 toString() 方法，让其只输出元素的值。
• print()：打印链表的所有元素。

具体代码：

讯享网

测试：

整个链表数据在 JavaScript 里是怎样的呢 ？

为了看这个数据，特意写了个 list 函数：

讯享网

重点上上面的最后一行代码： singlyLinked.list() ，打印的数据如下：

所以，在 JavaScript 中，单链表的真实数据有点类似于对象，实际上是 Node 类生成的实例。

单向链表与又向链表比较

• 双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。

• 双向链表提供了两种迭代列表的方法：从头到尾，或者从尾到头。

我们可以访问一个特定节点的下一个或前一个元素。

• 在单向链表中，如果迭代链表时错过了要找的元素，就需要回到链表起点，重新开始迭代。
• 在双向链表中，可以从任一节点，向前或向后迭代，这是双向链表的一个优点。
• 所以，双向链表可以支持 O(1) 时间复杂度的情况下找到前驱结点，正是这样的特点，也使双向链表在某些情况下的插入、删除等操作都要比单链表简单、高效。

实现

具体代码：

测试：

讯享网

整个链表数据在 JavaScript 里是怎样的呢 ？

调用 doublyLinked.list(); .

控制台输出如下：

链表代码实现的关键是弄清楚：前节点与后节点与边界。

讯享网

这种行为会导致链表中每个节点的 next 属性都指向链表的头节点，换句话说，也就是链表的尾节点指向了头节点，形成了一个循环链表。如下图所示：

循环链表：在单链表的基础上，将尾节点的指针指向头结点，就构成了一个循环链表。环形链表从任意一个节点开始，都可以遍历整个链表。

代码：

测试：

讯享网

整个链表数据在 JavaScript 里是怎样的呢 ？

调用 circularLinked.list() 。

控制台输出如下：

你知道大家发现没有，为什么从 1 - 4 - 1 了，还有 next 节点，而且是还可以一直点 next ，重复的展开下去，这正是 循环 的原因。

链表总结

• 写链表代码是最考验逻辑思维能力的，要熟练链表，只有 多写多练，没有捷径。
• 因为，链表代码到处都是指针的操作、边界条件的处理，稍有不慎就容易产生 Bug。
• 链表代码写得好坏，可以看出一个人写代码是否够细心，考虑问题是否全面，思维是否缜密。
• 所以，这也是很多面试官喜欢让人手写链表代码的原因。
• 一定要自己写代码实现一下，才有效果。

JavaScript 数据结构与算法之美 的系列文章，坚持 3 - 7 天左右更新一篇，暂定计划如下表。

如果有错误或者不严谨的地方，请务必给予指正，十分感谢。

文章中的代码已经全部放在了我的 github 上，如果喜欢或者有所启发，欢迎 star，对作者也是一种鼓励。

关注我的公众号，第一时间接收最新的精彩博文。

文章可以转载，但须注明作者及出处，需要转载到公众号的，喊我加下白名单就行了。

参考文章：