栈(stack)又名堆栈,它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶,相对地,把另一端称为栈底。
一、实现一个栈类Stack
基于堆栈的特性,可以用数组做线性表进行存储。
初始化Stack
类的结构如下:
1 2 3 4 5 6 7 8
| function Stack(){ this.space = []; }
Stack.prototype = { constructor: Stack, };
|
接下来,就是在原型上,对入栈
、出栈
、清空栈
、读取栈顶
、读取整个栈数据
这几个接口的实现。
Stack
类默认以数组头部做栈底,尾部做栈顶。
1.1 入栈 push
入栈可以利用js数组的push
方法,在数组尾部压入数据。
1 2 3 4 5
| Stack.prototype = { push: function(value){ return this.space.push(value); } }
|
1.2 出栈 pop
出栈同样是利用js数组的pop
方法,在数组尾部推出数据。
1 2 3 4 5
| Stack.prototype = { pop: function(){ return this.space.pop(); } }
|
1.3 清空栈 clear
清空栈相对简单,将存储数据的数组重置为空数组即可。
1 2 3 4 5
| Stack.prototype = { clear: function(){ this.space = []; } }
|
1.4 读取栈顶readTop
读取栈顶数据,采用数组下标的方式进行获取。带来的一个好处就是:下标超出数组有效范围时,返回值为undefined
。
1 2 3 4 5
| Stack.prototype = { readTop: function(){ return this.space[this.space.length - 1]; } }
|
1.4 读取整个栈read
读取整个栈数据,直接返回当前数组即可。
1 2 3 4 5
| Stack.prototype = { read: function(){ return this.space; } }
|
1.5 聚合
最后,将所有功能聚合后,如下所示,一个堆栈的数据结构就搞定了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
| function Stack(){ this.space = []; }
Stack.prototype = { constructor: Stack, push: function(value){ return this.space.push(value); }, pop: function(){ return this.space.pop(); }, clear: function(){ this.space = []; }, readTop: function(){ return this.space[this.space.length - 1]; }, read: function(){ return this.space; } };
|
二、实战
学数据结构和算法是为了更好、更高效率地解决工程问题。
这里学以致用,提供了几个真实的案例,来体会下数据结构和算法的魅力:)
2.1 数组reverse
的实现
当前案例,将用堆栈来实现数组的反转功能。
1 2 3 4 5 6 7 8 9
| function reverse(arr){ var ArrStack = new Stack();
for(var i = arr.length - 1; i >= 0; i--){ ArrStack.push(arr[i]); }
return ArrStack.read(); }
|
如代码所示,可分为以下几个步骤:
- 实例化一个堆栈用于存储数据
- 将传入的数组进行倒序遍历,并逐个压入堆栈
- 最后使用
read
接口,输出数据
好像很简单,不用担心,复杂的在后面:)
2.2 十进制转换为二进制
数值转换进制的问题,是堆栈的小试牛刀。
讲解转换方法前,先来看一个小例子:
将十进制的13转换成二进制
1 2 3 4 5 6 7
| 2 | 13 1  ̄ ̄ ̄ 2 | 6 0  ̄ ̄ ̄ 2 | 3 1  ̄ ̄ ̄ ̄ 1 1
|
如上所示:13的二进制码为1101
。
将手工换算,变成堆栈存储,只需将对2取余的结果依次压入堆栈保存,最后反转输出即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| function binary(number){ var tmp = number; var ArrStack = new Stack();
if(number === 0){ return 0; }
while(tmp){ ArrStack.push(tmp % 2); tmp = parseInt(tmp / 2, 10); }
return reverse(ArrStack.read()).join(''); }
binary(14); binary(1024);
|
2.3 表达式求值
这个案例,其实可以理解为简化版的eval
方法。
案例内容是对1+7*(4-2)
的求值。
进入主题前,有必要先了解以下的数学理论:
- 中缀表示法(或中缀记法)是一个通用的算术或逻辑公式表示方法, 操作符是以中缀形式处于操作数的中间(例:3 + 4)。
- 逆波兰表示法(Reverse Polish notation,RPN,或逆波兰记法),是一种是由波兰数学家扬·武卡谢维奇1920年引入的数学表达式方式,在逆波兰记法中,所有操作符置于操作数的后面,因此也被称为后缀表示法。逆波兰记法不需要括号来标识操作符的优先级。
常规中缀记法的“3 - 4 + 5”在逆波兰记法中写作“3 4 - 5 +”
- 调度场算法(Shunting Yard Algorithm)是一个用于将中缀表达式转换为后缀表达式的经典算法,由艾兹格·迪杰斯特拉引入,因其操作类似于火车编组场而得名。
提前说明,这只是简单版实现。所以规定有两个:
- 数字要求为整数
- 不允许表达式中出现多余的空格
实现代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91
| function calculate(exp){ var valueStack = new Stack(); var operatorStack = new Stack(); var expArr = exp.split(''); var FIRST_OPERATOR = ['+', '-']; var SECOND_OPERATOR = ['*', '/']; var SPECIAL_OPERATOR = ['(', ')']; var tmp; var tmpOperator;
for(var i = 0, len = expArr.length; i < len; i++){ tmp = expArr[i]; switch(tmp){ case '(': operatorStack.push(tmp); break; case ')': while( (tmpOperator = operatorStack.pop()) !== '(' && typeof tmpOperator !== 'undefined' ){ valueStack.push(calculator(tmpOperator, valueStack.pop(), valueStack.pop())); } break; case '+': case '-': while( typeof operatorStack.readTop() !== 'undefined' && SPECIAL_OPERATOR.indexOf(operatorStack.readTop()) === -1 && (SECOND_OPERATOR.indexOf(operatorStack.readTop()) !== -1 || tmp != operatorStack.readTop()) ){ valueStack.push(calculator(operatorStack.pop(), valueStack.pop(), valueStack.pop())); } operatorStack.push(tmp); break; case '*': case '/': while( typeof operatorStack.readTop() != 'undefined' && FIRST_OPERATOR.indexOf(operatorStack.readTop()) === -1 && SPECIAL_OPERATOR.indexOf(operatorStack.readTop()) === -1 && tmp != operatorStack.readTop()){ valueStack.push(calculator(operatorStack.pop(), valueStack.pop(), valueStack.pop())); } operatorStack.push(tmp); break; default: valueStack.push(tmp); } }
while( typeof (tmpOperator = operatorStack.pop()) !== 'undefined' ){ valueStack.push(calculator(tmpOperator, valueStack.pop(), valueStack.pop())); }
return valueStack.pop();
function calculator(operator, passivityNum, initiativeNum){ var result = 0;
initiativeNum = typeof initiativeNum === 'undefined' ? 0 : parseInt(initiativeNum, 10); passivityNum = typeof passivityNum === 'undefined' ? 0 : parseInt(passivityNum, 10);
switch(operator){ case '+': result = initiativeNum + passivityNum; console.log(`${initiativeNum} + ${passivityNum} = ${result}`); break; case '-': result = initiativeNum - passivityNum; console.log(`${initiativeNum} - ${passivityNum} = ${result}`); break; case '*': result = initiativeNum * passivityNum; console.log(`${initiativeNum} * ${passivityNum} = ${result}`); break; case '/': result = initiativeNum / passivityNum; console.log(`${initiativeNum} / ${passivityNum} = ${result}`); break; default:; }
return result; } }
|
实现思路:
- 采用
调度场算法
,对中缀表达式进行读取,对结果进行合理运算。
- 临界点采用
operatorStack.readTop() !== 'undefined'
进行判定。有些书采用#
做结束标志,个人觉得有点累赘。
- 将字符串表达式用
split
进行拆分,然后进行遍历读取,压入堆栈。有提前要计算结果的,进行对应的出栈处理。
- 将计算部分结果的方法,封装为独立的方法
calculator
。由于乘除运算符前后的数字,在运算上有区别,所以不能随意调换位置。
2.4 中缀表达式转换为后缀表达式(逆波兰表示法)
逆波兰表示法,是一种对计算机友好的表示法,不需要使用括号。
下面案例,是对上一个案例的变通,也是用调度场算法
,将中缀表达式转换为后缀表达式。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88
| function rpn(exp){ var valueStack = new Stack(); var operatorStack = new Stack(); var expArr = exp.split(''); var FIRST_OPERATOR = ['+', '-']; var SECOND_OPERATOR = ['*', '/']; var SPECIAL_OPERATOR = ['(', ')']; var tmp; var tmpOperator;
for(var i = 0, len = expArr.length; i < len; i++){ tmp = expArr[i]; switch(tmp){ case '(': operatorStack.push(tmp); break; case ')': while( (tmpOperator = operatorStack.pop()) !== '(' && typeof tmpOperator !== 'undefined' ){ valueStack.push(translate(tmpOperator, valueStack.pop(), valueStack.pop())); } break; case '+': case '-': while( typeof operatorStack.readTop() !== 'undefined' && SPECIAL_OPERATOR.indexOf(operatorStack.readTop()) === -1 && (SECOND_OPERATOR.indexOf(operatorStack.readTop()) !== -1 || tmp != operatorStack.readTop()) ){ valueStack.push(translate(operatorStack.pop(), valueStack.pop(), valueStack.pop())); } operatorStack.push(tmp); break; case '*': case '/': while( typeof operatorStack.readTop() != 'undefined' && FIRST_OPERATOR.indexOf(operatorStack.readTop()) === -1 && SPECIAL_OPERATOR.indexOf(operatorStack.readTop()) === -1 && tmp != operatorStack.readTop()){ valueStack.push(translate(operatorStack.pop(), valueStack.pop(), valueStack.pop())); } operatorStack.push(tmp); break; default: valueStack.push(tmp); } }
while( typeof (tmpOperator = operatorStack.pop()) !== 'undefined' ){ valueStack.push(translate(tmpOperator, valueStack.pop(), valueStack.pop())); }
return valueStack.pop();
function translate(operator, passivityNum, initiativeNum){ var result = '';
switch(operator){ case '+': result = `${initiativeNum} ${passivityNum} +`; console.log(`${initiativeNum} + ${passivityNum} = ${result}`); break; case '-': result = `${initiativeNum} ${passivityNum} -`; console.log(`${initiativeNum} - ${passivityNum} = ${result}`); break; case '*': result = `${initiativeNum} ${passivityNum} *`; console.log(`${initiativeNum} * ${passivityNum} = ${result}`); break; case '/': result = `${initiativeNum} ${passivityNum} /`; console.log(`${initiativeNum} / ${passivityNum} = ${result}`); break; default:; }
return result; } }
rpn('1+7*(4-2)');
|
2.5 汉诺塔

汉诺塔(港台:河内塔)是根据一个传说形成的数学问题:
有三根杆子A,B,C。A杆上有 N 个 (N>1) 穿孔圆盘,盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至 C 杆:
- 每次只能移动一个圆盘;
- 大盘不能叠在小盘上面。

堆栈的经典算法应用,首推就是汉诺塔
。
理解该算法,要注意以下几点:
- 不要深究每次的移动,要抽象理解
- 第一步:所有不符合要求的盘,从A塔统一移到B塔缓存
- 第二步:将符合的盘移动到C塔
- 第三步:把B塔缓存的盘全部移动到C塔
以下是代码实现:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| var ATower = new Stack(); var BTower = new Stack(); var CTower = new Stack(); var TIER = 4;
for(var i = TIER; i > 0; i--){ ATower.push(i); }
function Hanoi(n, from, to, buffer){ if(n > 0){ Hanoi(n - 1, from, buffer, to); to.push(from.pop()); Hanoi(n - 1, buffer, to, from); } }
Hanoi(ATower.read().length, ATower, CTower, BTower);
|
汉诺塔的重点,还是靠递归去实现。把一个大问题,通过递归,不断分拆为更小的问题。然后,集中精力解决小问题即可。
三、小结
不知不觉,写得有点多ORZ。
后面章节的参考链接,还是推荐看看。也许配合本文,你会有更深的理解。
参考
[1] 中缀表示法
[2] 后缀表示法
[3] 调度场算法
[4] 汉诺塔
本文链接:
https://wangxiaokai.vip/posts/stack/
版权声明:
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 3.0 许可协议。欢迎转载,转载注明出处即可!