前言
- 基础知识就像是一座大楼的地基，它决定了我们的技术高度。
- 我们应该多掌握一些可移值的技术或者再过十几年应该都不会过时的技术，数据结构与算法就是其中之一。
栈、队列、链表、堆 是数据结构与算法中的基础知识，是程序员的地基。
笔者写的 JavaScript 数据结构与算法之美 系列用的语言是 JavaScript ，旨在入门数据结构与算法和方便以后复习。
1. 线性表与非线性表
线性表（Linear List）：就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。数组、链表、队列、栈 等就是线性表结构。
非线性表：数据之间并不是简单的前后关系。二叉树、堆、图 就是非线性表。
本文主要讲线性表，非线性表会在后面章节讲。
2. 数组
定义
- 数组 (Array) 是一个有序的数据集合，我们可以通过数组名称 (name) 和索引 (index) 进行访问。
- 数组的索引是从 0 开始的。
特点
- 数组是用一组连续的内存空间来存储的。
所以数组支持 随机访问，根据下标随机访问的时间复杂度为 O(1)。
- 低效的插入和删除。
数组为了保持内存数据的连续性，会导致插入、删除这两个操作比较低效，因为底层通常是要进行大量的数据搬移来保持数据的连续性。
插入与删除的时间复杂度如下：
插入：从最好 O(1) ，最坏 O(n) ，平均 O(n)
删除：从最好 O(1) ，最坏 O(n) ，平均 O(n)
注意
但是因为 JavaScript 是弱类型的语言，弱类型则允许隐式类型转换。
隐式：是指源码中没有明显的类型转换代码。也就是说，一个变量，可以赋值字符串，也可以赋值数值。
let str = "string" str = 123 console.log(str) // 123
你还可以直接让字符串类型的变量和数值类型的变量相加，虽然得出的最终结果未必是你想象的那样，但一定不会报错。
let a = 123 let b = "456" let c = a + b // 数值加字符串，结果是字符串 console.log(c) // "123456"
数组的每一项可以是不同的类型，比如：
// 数组的类型有 数值、字符串，还可以随意变更类型 const arr = [ 12, 34, "abc" ] arr[2] = { "key": "value" } // 把数组的第二项变成对象 console.log(arr) // [ 12, 34, { "key": "value"} ]
定义的数组的大小是可变的，不像强类型语言，定义某个数组变量的时候就要定义该变量的大小。
const arr = [ 12, 34, "abc"] arr.push({ "key": "value" }) // 添加一项 对象 consolelog(arr) // [ 12, 34, "abc", { "key": "value" } ]
实现
JavaScript 原生支持数组，而且提供了很多操作方法，这里不展开讲。
3. 栈
定义
- 后进者先出，先进者后出，简称 后进先出（LIFO），这就是典型的
栈结构。 - 新添加的或待删除的元素都保存在栈的末尾，称作
栈顶，另一端就叫栈底。 - 在栈里，新元素都靠近栈顶，旧元素都接近栈底。
- 从栈的操作特性来看，是一种
操作受限的线性表，只允许在一端插入和删除数据。 - 不包含任何元素的栈称为
空栈。
栈也被用在编程语言的编译器和内存中保存变量、方法调用等，比如函数的调用栈。
实现
栈的方法：
- push(element)：添加一个（或几个）新元素到栈顶。
- pop()：移除栈顶的元素，同时返回被移除的元素。
- peek()：返回栈顶的元素，不对栈做任何修改。
- isEmpty()：如果栈里没有任何元素就返回 true，否则返回 false。
- clear()：移除栈里的所有元素。
- size()：返回栈里的元素个数。
// Stack类 function Stack() { this.items = []; // 添加新元素到栈顶 this.push = function(element) { this.items.push(element); }; // 移除栈顶元素，同时返回被移除的元素 this.pop = function() { return this.items.pop(); }; // 查看栈顶元素 this.peek = function() { return this.items[this.items.length - 1]; }; // 判断是否为空栈 this.isEmpty = function() { return this.items.length === 0; }; // 清空栈 this.clear = function() { this.items = []; }; // 查询栈的长度 this.size = function() { return this.items.length; }; // 打印栈里的元素 this.print = function() { console.log(this.items.toString()); }; }
测试：
// 创建Stack实例 var stack = new Stack(); console.log(stack.isEmpty()); // true stack.push(5); // undefined stack.push(8); // undefined console.log(stack.peek()); // 8 stack.push(11); // undefined console.log(stack.size()); // 3 console.log(stack.isEmpty()); // false stack.push(15); // undefined stack.pop(); // 15 console.log(stack.size()); // 3 stack.print(); // 5,8,11 stack.clear(); // undefined console.log(stack.size()); // 0
栈的应用实例：JavaScript 数据结构与算法之美 - 实现一个前端路由，如何实现浏览器的前进与后退 ？
4. 队列
普通队列
定义
- 队列是遵循 FIFO（First In First Out，先进先出）原则的一组有序的项。
- 队列在尾部添加新元素，并从顶部移除元素。
- 最新添加的元素必须排在队列的末尾。
- 队列只有 入队 push() 和出队 pop()。
实现
队列里面有一些声明的辅助方法：
- enqueue(element)：向队列尾部添加新项。
- dequeue()：移除队列的第一项，并返回被移除的元素。
- front()：返回队列中第一个元素，队列不做任何变动。
- isEmpty()：如果队列中不包含任何元素，返回 true，否则返回 false。
- size()：返回队列包含的元素个数，与数组的 length 属性类似。
- print()：打印队列中的元素。
- clear()：清空整个队列。
代码：
// Queue类 function Queue() { this.items = []; // 向队列尾部添加元素 this.enqueue = function(element) { this.items.push(element); }; // 移除队列的第一个元素，并返回被移除的元素 this.dequeue = function() { return this.items.shift(); }; // 返回队列的第一个元素 this.front = function() { return this.items[0]; }; // 判断是否为空队列 this.isEmpty = function() { return this.items.length === 0; }; // 获取队列的长度 this.size = function() { return this.items.length; }; // 清空队列 this.clear = function() { this.items = []; }; // 打印队列里的元素 this.print = function() { console.log(this.items.toString()); }; }
测试：
// 创建Queue实例 var queue = new Queue(); console.log(queue.isEmpty()); // true queue.enqueue('John'); // undefined queue.enqueue('Jack'); // undefined queue.enqueue('Camila'); // undefined queue.print(); // "John,Jack,Camila" console.log(queue.size()); // 3 console.log(queue.isEmpty()); // false queue.dequeue(); // "John" queue.dequeue(); // "Jack" queue.print(); // "Camila" queue.clear(); // undefined console.log(queue.size()); // 0
优先队列
定义
优先队列中元素的添加和移除是依赖优先级的。
应用
- 一个现实的例子就是机场登机的顺序。头等舱和商务舱乘客的优先级要高于经济舱乘客。
- 再比如：火车，老年人、孕妇和带小孩的乘客是享有优先检票权的。
优先队列分为两类
- 最小优先队列
- 最大优先队列
最小优先队列是把优先级的值最小的元素被放置到队列的最前面（代表最高的优先级）。
比如：有四个元素："John", "Jack", "Camila", "Tom"，他们的优先级值分别为 4，3，2，1。
那么最小优先队列排序应该为："Tom"，"Camila"，"Jack"，"John"。
最大优先队列正好相反，把优先级值最大的元素放置在队列的最前面。
以上面的为例，最大优先队列排序应该为："John", "Jack", "Camila", "Tom"。
实现
实现一个优先队列，有两种选项：
- 设置优先级，根据优先级正确添加元素，然后和普通队列一样正常移除
- 设置优先级，和普通队列一样正常按顺序添加，然后根据优先级移除
这里最小优先队列和最大优先队列我都采用第一种方式实现，大家可以尝试一下第二种。
下面只重写 enqueue() 方法和 print() 方法，其他方法和上面的普通队列完全相同。
实现最小优先队列
// 定义最小优先队列 function MinPriorityQueue () { this.items = []; this.enqueue = enqueue; this.dequeue = dequeue; this.front = front; this.isEmpty = isEmpty; this.size = size; this.clear = clear; this.print = print; }
实现最小优先队列 enqueue() 方法和 print() 方法：
// 优先队列添加元素，要根据优先级判断在队列中的插入顺序 function enqueue (element, priority) { var queueElement = { element: element, priority: priority }; if (this.isEmpty()) { this.items.push(queueElement); } else { var added = false; for (var i = 0; i < this.size(); i++) { if (queueElement.priority < this.items[i].priority) { this.items.splice(i, 0, queueElement); added = true; break ; } } if (!added) { this.items.push(queueElement); } } } // 打印队列里的元素 function print () { var strArr = []; strArr = this.items.map(function (item) { return `${item.element}->${item.priority}`; }); console.log(strArr.toString()); }
最小优先队列测试：
// 创建最小优先队列minPriorityQueue实例 var minPriorityQueue = new MinPriorityQueue(); console.log(minPriorityQueue.isEmpty()); // true minPriorityQueue.enqueue("John", 1); // undefined minPriorityQueue.enqueue("Jack", 3); // undefined minPriorityQueue.enqueue("Camila", 2); // undefined minPriorityQueue.enqueue("Tom", 3); // undefined minPriorityQueue.print(); // "John->1,Camila->2,Jack->3,Tom->3" console.log(minPriorityQueue.size()); // 4 console.log(minPriorityQueue.isEmpty()); // false minPriorityQueue.dequeue(); // {element: "John", priority: 1} minPriorityQueue.dequeue(); // {element: "Camila", priority: 2} minPriorityQueue.print(); // "Jack->3,Tom->3" minPriorityQueue.clear(); // undefined console.log(minPriorityQueue.size()); // 0
实现最大优先队列
// 最大优先队列 MaxPriorityQueue 类 function MaxPriorityQueue () { this.items = []; this.enqueue = enqueue; this.dequeue = dequeue; this.front = front; this.isEmpty = isEmpty; this.size = size; this.clear = clear; this.print = print; } // 优先队列添加元素，要根据优先级判断在队列中的插入顺序 function enqueue (element, priority) { var queueElement = { element: element, priority: priority }; if (this.isEmpty()) { this.items.push(queueElement); } else { var added = false; for (var i = 0; i < this.items.length; i++) { // 注意，只需要将这里改为大于号就可以了 if (queueElement.priority > this.items[i].priority) { this.items.splice(i, 0, queueElement); added = true; break ; } } if (!added) { this.items.push(queueElement); } } }
最大优先队列测试：
// 创建最大优先队列maxPriorityQueue实例 var maxPriorityQueue = new MaxPriorityQueue(); console.log(maxPriorityQueue.isEmpty()); // true maxPriorityQueue.enqueue("John", 1); // undefined maxPriorityQueue.enqueue("Jack", 3); // undefined maxPriorityQueue.enqueue("Camila", 2); // undefined maxPriorityQueue.enqueue("Tom", 3); // undefined maxPriorityQueue.print(); // "Jack->3,Tom->3,Camila->2,John->1" console.log(maxPriorityQueue.size()); // 4 console.log(maxPriorityQueue.isEmpty()); // false maxPriorityQueue.dequeue(); // {element: "Jack", priority: 3} maxPriorityQueue.dequeue(); // {element: "Tom", priority: 3} maxPriorityQueue.print(); // "Camila->2,John->1" maxPriorityQueue.clear(); // undefined console.log(maxPriorityQueue.size()); // 0
循环队列
定义
循环队列，顾名思义，它长得像一个环。把它想像成一个圆的钟就对了。
关键是：确定好队空和队满的判定条件。
循环队列的一个例子就是击鼓传花游戏（Hot Potato）。在这个游戏中，孩子们围城一个圆圈，击鼓的时候把花尽快的传递给旁边的人。某一时刻击鼓停止，这时花在谁的手里，谁就退出圆圈直到游戏结束。重复这个过程，直到只剩一个孩子（胜者）。
下面我们在普通队列的基础上，实现一个模拟的击鼓传花游戏，下面只写击鼓传花的代码片段：
// 实现击鼓传花 function hotPotato (nameList, num) { var queue = new Queue(); for (var i = 0; i < nameList.length; i++) { queue.enqueue(nameList[i]); } var eliminated = ''; while (queue.size() > 1) { // 循环 num 次，队首出来去到队尾 for (var i = 0; i < num; i++) { queue.enqueue(queue.dequeue()); } // 循环 num 次过后，移除当前队首的元素 eliminated = queue.dequeue(); console.log(`${eliminated} 在击鼓传花中被淘汰！`); } // 最后只剩一个元素 return queue.dequeue(); } // 测试 var nameList = ["John", "Jack", "Camila", "Ingrid", "Carl"]; var winner = hotPotato(nameList, 10); console.log(`最后的胜利者是：${winner}`);
执行结果为：
// John 在击鼓传花中被淘汰！ // Ingrid 在击鼓传花中被淘汰！ // Jack 在击鼓传花中被淘汰！ // Camila 在击鼓传花中被淘汰！ // 最后的胜利者是：Carl
队列小结
一些具有某些额外特性的队列，比如：循环队列、阻塞队列、并发队列。它们在很多偏底层系统、框架、中间件的开发中，起着关键性的作用。
以上队列的代码要感谢 leocoder351。
