当前位置:Gxlcms > JavaScript > JavaScript中栈和队列的算法解析

JavaScript中栈和队列的算法解析

时间:2021-07-01 10:21:17 帮助过:6人阅读

本篇文章给大家带来的内容是关于JavaScript中栈和队列的算法解析,有一定的参考价值,有需要的朋友可以参考一下,希望对你有所帮助。

一、认识数据结构

什么是数据结构?下面是维基百科的解释

数据结构是计算机存储、组织数据的方式

数据结构意味着接口或封装:一个数据结构可被视为两个函数之间的接口,或者是由数据类型联合组成的存储内容的访问方法封装

我们每天的编码中都会用到数据结构,因为数组是最简单的内存数据结构,下面是常见的数据结构

  • 数组(Array)

  • 栈(Stack)

  • 队列(Queue)

  • 链表(Linked List)

  • 树(Tree)

  • 图(Graph)

  • 堆(Heap)

  • 散列表(Hash)

下面来学习学习栈和队列..

二、栈

2.1 栈数据结构

栈是一种遵循后进先出(LIFO)原则的有序集合。新添加的或待删除的元素都保存在栈的同一端,称作栈顶,另一端就叫栈底。在栈里,新元素都接近栈顶,旧元素都接近栈底。

2423822761-5c3e06d4d3e4a_articlex.png

类比生活中的物件:一摞书或者推放在一起的盘子

2.2 栈的实现

普通的栈常用的有以下几个方法:

push 添加一个(或几个)新元素到栈顶

pop 溢出栈顶元素,同时返回被移除的元素

peek 返回栈顶元素,不对栈做修改

isEmpty 栈内无元素返回true,否则返回false

size 返回栈内元素个数

clear 清空栈

  1. class Stack {
  2. constructor() {
  3. this._items = []; // 储存数据
  4. }
  5. // 向栈内压入一个元素
  6. push(item) {
  7. this._items.push(item);
  8. }
  9. // 把栈顶元素弹出
  10. pop() {
  11. return this._items.pop();
  12. }
  13. // 返回栈顶元素
  14. peek() {
  15. return this._items[this._items.length - 1];
  16. }
  17. // 判断栈是否为空
  18. isEmpty() {
  19. return !this._items.length;
  20. }
  21. // 栈元素个数
  22. size() {
  23. return this._items.length;
  24. }
  25. // 清空栈
  26. clear() {
  27. this._items = [];
  28. }
  29. }

现在再回头想想数据结构里面的栈是什么。

突然发现并没有那么神奇,仅仅只是对原有数据进行了一次封装而已。而封装的结果是:并不去关心其内部的元素是什么,只是去操作栈顶元素,这样的话,在编码中会更可控一些。

2.3 栈的应用

(1)十进制转任意进制

要求: 给定一个函数,输入目标数值和进制基数,输出对应的进制数(最大为16进制)

  1. baseConverter(10, 2) ==> 1010
  2. baseConverter(30, 16) ==> 1E

分析: 进制转换的本质:将目标值一次一次除以进制基数,得到的取整值为新目标值,记录下余数,直到目标值小于0,最后将余数逆序组合即可。利用栈,记录余数入栈,组合时出栈

  1. // 进制转换
  2. function baseConverter(delNumber, base) {
  3. const stack = new Stack();
  4. let rem = null;
  5. let ret = [];
  6. // 十六进制中需要依次对应A~F
  7. const digits = '0123456789ABCDEF';
  8. while (delNumber > 0) {
  9. rem = Math.floor(delNumber % base);
  10. stack.push(rem);
  11. delNumber = Math.floor(delNumber / base);
  12. }
  13. while (!stack.isEmpty()) {
  14. ret.push(digits[stack.pop()]);
  15. }
  16. return ret.join('');
  17. }
  18. console.log(baseConverter(100345, 2)); //
输出11000011111111001 console.log(baseConverter(100345, 8)); //输出303771 console.log(baseConverter(100345, 16)); //输出187F9

(2)逆波兰表达式计算

要求: 逆波兰表达式,也叫后缀表达式,它将复杂表达式转换为可以依靠简单的操作得到计算结果的表达式,例如(a+b)*(c+d)转换为a b + c d + *

  1. ["4", "13", "5", "/", "+"] ==> (4 + (13 / 5)) = 6
  2. ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
  3. ==> ((10 * (6 / ((9 + 3) * -11))) + 17) + 5

分析: 以符号为触发节点,一旦遇到符号,就将符号前两个元素按照该符号运算,并将新的结果入栈,直到栈内仅一个元素

  1. function isOperator(str) {
  2. return ['+', '-', '*', '/'].includes(str);
  3. }
  4. // 逆波兰表达式计算
  5. function clacExp(exp) {
  6. const stack = new Stack();
  7. for (let i = 0; i < exp.length; i++) {
  8. const one = exp[i];
  9. if (isOperator(one)) {
  10. const operatNum1 = stack.pop();
  11. const operatNum2 = stack.pop();
  12. const expStr = `${operatNum2}${one}${operatNum1}`;
  13. const res = eval(expStr);
  14. stack.push(res);
  15. } else {
  16. stack.push(one);
  17. }
  18. }
  19. return stack.peek();
  20. }
  21. console.log(clacExp(["4", "13", "5", "/", "+"])); // 6.6

(3)利用普通栈实现一个有min方法的栈

思路: 使用两个栈来存储数据,其中一个命名为dataStack,专门用来存储数据,另一个命名为minStack,专门用来存储栈里最小的数据。始终保持两个栈中的元素个数相同,压栈时判别压入的元素与minStack栈顶元素比较大小,如果比栈顶元素小,则直接入栈,否则复制栈顶元素入栈;弹出栈顶时,两者均弹出即可。这样minStack的栈顶元素始终为最小值。

  1. class MinStack {
  2. constructor() {
  3. this._dataStack = new Stack();
  4. this._minStack = new Stack();
  5. }
  6. push(item) {
  7. this._dataStack.push(item);
  8. // 为空或入栈元素小于栈顶元素,直接压入该元素
  9. if (this._minStack.isEmpty() || this._minStack.peek() > item) {
  10. this._minStack.push(item);
  11. } else {
  12. this._minStack.push(this._minStack.peek());
  13. }
  14. }
  15. pop() {
  16. this._dataStack.pop();
  17. return this._minStack.pop();
  18. }
  19. min() {
  20. return this._minStack.peek();
  21. }
  22. }
  23. const minstack = new MinStack();
  24. minstack.push(3);
  25. minstack.push(4);
  26. minstack.push(8);
  27. console.log(minstack.min()); // 3
  28. minstack.push(2);
  29. console.log(minstack.min()); // 2

三、队列

3.1 队列数据结构

队列是遵循先进先出(FIFO,也称为先来先服务)原则的一组有序的项。队列在尾部添加新元素,并从顶部移除元素。最新添加的元素必须排在队列的末尾

2340553888-5c3e073e9f4f8_articlex.png

类比:日常生活中的购物排队

3.2 队列的实现

普通的队列常用的有以下几个方法:

  • enqueue 向队列尾部添加一个(或多个)新的项

  • dequeue 移除队列的第一(即排在队列最前面的)项,并返回被移除的元素

  • head 返回队列第一个元素,队列不做任何变动

  • tail 返回队列最后一个元素,队列不做任何变动

  • isEmpty 队列内无元素返回true,否则返回false

  • size 返回队列内元素个数

  • clear 清空队列

  1. class Queue {
  2. constructor() {
  3. this._items = [];
  4. }
  5. enqueue(item) {
  6. this._items.push(item);
  7. }
  8. dequeue() {
  9. return this._items.shift();
  10. }
  11. head() {
  12. return this._items[0];
  13. }
  14. tail() {
  15. return this._items[this._items.length - 1];
  16. }
  17. isEmpty() {
  18. return !this._items.length;
  19. }
  20. size() {
  21. return this._items.length;
  22. }
  23. clear() {
  24. this._items = [];
  25. }
  26. }

与栈类比,栈仅能操作其头部,队列则首尾均能操作,但仅能在头部出尾部进。当然,也印证了上面的话:栈和队列并不关心其内部元素细节,也无法直接操作非首尾元素。

3.3 队列的应用

(1)约瑟夫环(普通模式)

要求: 有一个数组a[100]存放0~99;要求每隔两个数删掉一个数,到末尾时循环至开头继续进行,求最后一个被删掉的数。

分析: 按数组创建队列,依次判断元素是否满足为指定位置的数,如果不是则enqueue到尾部,否则忽略,当仅有一个元素时便输出

  1. // 创建一个长度为100的数组
  2. const arr_100 = Array.from({ length: 100 }, (_, i) => i*i);
  3. function delRing(list) {
  4. const queue = new Queue();
  5. list.forEach(e => { queue.enqueue(e); });
  6. let index = 0;
  7. while (queue.size() !== 1) {
  8. const item = queue.dequeue();
  9. index += 1;
  10. if (index % 3 !== 0) {
  11. queue.enqueue(item);
  12. }
  13. }
  14. return queue.tail();
  15. }
  16. console.log(delRing(arr_100)); // 8100 此时index=297

(2)菲波那切数列(普通模式)

要求: 使用队列计算斐波那契数列的第n项
分析: 斐波那契数列的前两项固定为1,后面的项为前两项之和,依次向后,这便是斐波那契数列。

  1. function fibonacci(n) {
  2. const queue = new Queue();
  3. queue.enqueue(1);
  4. queue.enqueue(1);
  5. let index = 0;
  6. while(index < n - 2) {
  7. index += 1;
  8. // 出队列一个元素
  9. const delItem = queue.dequeue();
  10. // 获取头部值
  11. const headItem = queue.head();
  12. const nextItem = delItem + headItem;
  13. queue.enqueue(nextItem);
  14. }
  15. return queue.tail();
  16. }
  17. console.log(fibonacci(9)); // 34

(3)用队列实现一个栈

要求: 用两个队列实现一个栈
分析: 使用队列实现栈最主要的是在队列中找到栈顶元素并对其操作。具体的思路如下:

  1. 两个队列,一个备份队列emptyQueue,一个是数据队列dataQueue

  2. 在确认栈顶时,依次dequeue至备份队列,置换备份队列和数据队列的引用即可

  1. class QueueStack {
  2. constructor() {
  3. this.queue_1 = new Queue();
  4. this.queue_2 = new Queue();
  5. this._dataQueue = null; // 放数据的队列
  6. this._emptyQueue = null; // 空队列,备份使用
  7. }
  8. // 确认哪个队列放数据,哪个队列做备份空队列
  9. _initQueue() {
  10. if (this.queue_1.isEmpty() && this.queue_2.isEmpty()) {
  11. this._dataQueue = this.queue_1;
  12. this._emptyQueue = this.queue_2;
  13. } else if (this.queue_1.isEmpty()) {
  14. this._dataQueue = this.queue_2;
  15. this._emptyQueue = this.queue_1;
  16. } else {
  17. this._dataQueue = this.queue_1;
  18. this._emptyQueue = this.queue_2;
  19. }
  20. };
  21. push(item) {
  22. this.init_queue();
  23. this._dataQueue.enqueue(item);
  24. };
  25. peek() {
  26. this.init_queue();
  27. return this._dataQueue.tail();
  28. }
  29. pop() {
  30. this.init_queue();
  31. while (this._dataQueue.size() > 1) {
  32. this._emptyQueue.enqueue(this._dataQueue.dequeue());
  33. }
  34. return this._dataQueue.dequeue();
  35. };
  36. };

学习了栈和队列这类简单的数据结构,我们会发现。数据结构并没有之前想象中那么神秘,它们只是规定了这类数据结构的操作方式:栈只能对栈顶进行操作,队列只能在尾部添加在头部弹出;且它们不关心内部的元素状态。

以上就是JavaScript中栈和队列的算法解析的详细内容,更多请关注Gxl网其它相关文章!

人气教程排行