2020年6月4日下午，前端小伙伴胡利朋同学分享了数据结构中栈和队列的 JavaScript 实现，收获良多，在此做下笔记，也自己实现一下栈和队列这两个数据结构。

1.栈

1.1 栈的定义

栈是一种特殊的线性表，仅能够在栈顶进行操作，有着后进先出的特性 。

前端分享会-数据结构-栈和队列 - 图1

1.2 栈的 JavaSaript 实现

1.2.1数据存储

  • 数组
  • 链表

栈这样的数据结构，一般可以用数组或者链表进行数据的存储。在JavaScript中，数组最常用，也是最熟悉的，下面我们就用数组来实现栈这个数据结构。

1.2.2栈的方法

栈的方法主要有以下几个：

  • 入栈
  • 出栈
  • 返回栈顶元素
  • 判空
  • 清空
  • 返回大小
  • 打印所有元素

具体实现：

  1. class Stack {
  2. constructor() {
  3. // 定义一个数组存储数据,数组头为栈底,尾为栈顶
  4. this.stack = [];
  5. }
  7. // 入栈:添加一个或多个元素到栈顶
  8. inStack(...args) {
  9. this.stack.push(...args);
  10. }
  12. // 出栈:移除栈顶的元素,同时返回被移除的元素
  13. outStack() {
  14. return this.stack.pop();
  15. }
  17. // 返回栈顶元素
  18. stackTop() {
  19. return this.stack[this.stack.length - 1];
  20. }
  22. // 判空
  23. isEmpty() {
  24. return this.stack.length === 0;
  25. }
  27. // 清空
  28. clearStack() {
  29. this.stack = [];
  30. }
  32. // 返回大小
  33. stackSize() {
  34. return this.stack.length;
  35. }
  37. // 打印所有元素
  38. printStack() {
  39. console.log(this.stack.toString());
  40. }
  41. }
  43. // 测试
  44. let new_stack = new Stack();
  45. // 入栈
  46. new_stack.inStack(1, 2, 3, 4)
  47. console.log('打印入栈之后栈中所有元素')
  48. new_stack.printStack();
  49. console.log('返回栈顶元素', new_stack.stackTop());
  50. console.log('返回栈的大小', new_stack.stackSize());
  51. console.log('判断栈是否为空', new_stack.isEmpty());
  52. console.log('出栈', new_stack.outStack());
  53. console.log('打印出栈之后栈中所有元素')
  54. new_stack.printStack();

1.3 栈的应用练习

创建好栈这个数据结构之后，很多算法的时间都会变得很简单，下面就以判断括号合法性这一算法来举例说明。

判断括号的合法性

举例：

  • ‘(()()((((()))))(()))’ —合法的括号，左右配对
  • ‘())())(()()(()))()’ —不合法的括号，左右不配对

算法实现：

  1. // 栈的应用练习
  2. // 判断括号的合法性
  3. // 整体思路:
  4. // 如果只有一个括号,直接不合法
  5. // 如果第一个是")",直接不合法
  6. // 创建一个栈,遍历字符串,如果是"(",将其入栈,当碰到")"的时候,将一个"("出栈,当没有"("可以出栈和")"匹配,直接不合法,最后栈不为空(还有"("没有被匹配),直接不合法
  7. function isLegalBracket(str) {
  8. // 输入的字符串为空,返回提示信息
  9. if (str.length === 0) {
  10. return '请输入要检验的字符串';
  11. }
  12. // 只有一个括号,返回false
  13. if (str.length === 1) {
  14. return false;
  15. }
  16. // 第一个是")",返回false
  17. if (str[0] === ")") {
  18. return false;
  19. }
  20. let stack = new Stack;
  21. for (let i = 0; i < str.length; i++) {
  22. if (str[i] === "(") {
  23. stack.inStack(str[i]);
  24. }
  25. if (str[i] === ")") {
  26. if (stack.isEmpty()) {
  27. return false;
  28. } else {
  29. stack.outStack();
  30. }
  31. }
  32. }
  33. return stack.isEmpty();
  34. }
  36. console.log("'(()()((((()))))(()))'中括号的合法性为:",isLegalBracket('(()()((((()))))(()))'))
  37. console.log("'())())(()()(()))()'中括号的合法性为:",isLegalBracket('())())(()()(()))()'))

栈除了上面的应用，还可以实现一些操作的撤回以及重做，都是很方便的，碰到需要做撤回的功能，小伙伴们可以考虑用栈来存储数据哦！

2. 队列

2.1 队列的定义

队列是一种特殊的线性表，其特殊之处在于，它只允许你在队列的头部删除元素，在队列的末尾添加新的元素。有着先进先出的特性。

前端分享会-数据结构-栈和队列 - 图2

前端分享会-数据结构-栈和队列 - 图3

2.2 队列的 JavaScript实现

2.2.1 数据存储

  • 数组
  • 链表

同栈一样，我们经常用数组或者链表来存储队列这一数据结构，下面来看看用数组怎么存储队列吧！

2.2.2 队列的方法

和栈类似，队列中一般也都有以下方法

  • 队尾添加
  • 队首删除
  • 返回队首元素
  • 判断队列是否为空
  • 清空队列
  • 返回队列的大小
  • 打印队列中所有的元素

具体实现

  1. class Queue {
  2. constructor() {
  3. // 定义一个数组存储数据,数组头为队首,尾为队尾
  4. this.queue = [];
  5. }
  7. // 入队:添加一个或多个元素到队列中
  8. inQueue(...args) {
  9. this.queue.push(...args);
  10. }
  12. // 出队:移除队首的元素,同时返回被移除的元素
  13. outQueue() {
  14. return this.queue.shift();
  15. }
  17. // 返回队首元素
  18. queueTop() {
  19. return this.queue[0];
  20. }
  22. // 判空
  23. isEmpty() {
  24. return this.queue.length === 0;
  25. }
  27. // 清空
  28. clearQueue() {
  29. this.queue = [];
  30. }
  32. // 返回大小
  33. queueSize() {
  34. return this.queue.length;
  35. }
  37. // 打印所有元素
  38. printQueue() {
  39. console.log(this.queue.toString());
  40. }
  41. }

2.3 队列的应用练习

使用队列这一数据结构，也可以让我们很多方法变得很简单，比如我们要查询斐波那契数列中第200个数是什么，就可以用队列很方便的算出来。

斐波那契数列：一个数列，从第三项开始，以后的每一项为前两项的和

例：1，1，2，3，5，8，13，21，34…

  1. // 斐波那契数列
  2. function fibonacci(n) {
  3. let queue = new Queue();
  4. let index = 0;
  5. // 先放⼊入斐波那契序列列的前两个数值
  6. queue.inQueue(1);
  7. queue.inQueue(1);
  8. while (index < n - 2) {
  9. // 出队列列⼀一个元素
  10. let del_item = queue.outQueue();
  11. // 取队列列头部元素
  12. let head_item = queue.queueTop();
  13. let next_item = del_item + head_item;
  14. // 将计算结果放⼊入队列列
  15. queue.inQueue(next_item);
  16. index += 1;
  17. }
  18. queue.outQueue();
  19. return queue.queueTop();
  20. };
  21. console.log(fibonacci(4))
  22. console.log(fibonacci(5))
  23. console.log(fibonacci(6))
  24. console.log(fibonacci(7))
  25. console.log(fibonacci(8))
  26. console.log(fibonacci(99))

除此以外，在写前端交互的时候，页面上会有很多弹窗，我们也可以用队列来存储，这样，弹窗就会按照出现的顺序一个一个弹出来。在后端开发中，服务器的消息队列，也经常使用队列这种数据结构。

2.4 队列的变形—双端队列

2.4.1 定义

双端队列(deque，或称 double-ended queue)是一种允许我们同时从前端和后端添加和移除元素的特殊队列。（看这个定义，双端队列是不是特别像JavaSctipt中的数组？）

2.4.2 实现

前端分享会-数据结构-栈和队列 - 图4

2.4.3 应用

回文检查器

回文字符串：当一个字符串是一个中心对称的字符串，我们就称这个字符串为回文字符串

例：”a”
例：”aba”
例：”abba”

  1. // 回文检查器
  2. function palChecker(str) {
  3. // 创建一个双端队列,将字符串中的字符,依次添加到双端队列中
  4. let arr = str.split('');
  5. // 假定是回文字符串
  6. let isPalindrome = true;
  7. // 当至少有一个字符并且满足首位相等,则循环
  8. while (arr.length > 1 && isPalindrome) {
  9. let first = arr.shift();
  10. let last = arr.pop();
  11. if (first !== last) {
  12. isPalindrome = false;
  13. }
  14. }
  15. return isPalindrome;
  16. }
  18. console.log(palChecker('abba'))

队列还有其他的变形，如

，小伙伴们可以自行了解，这里就不再展开解释。