栈（Stack）是限定仅在表尾进行插入或删除操作的线性表。表尾为栈顶（top），表头为栈底（bottom），不含元素的空表为空栈。
栈又称为后进先出（last in first out）的线性表。
堆栈可以用链表和数组两种方式实现，一般为一个堆栈预先分配一个大小固定且较合适的空间并非难事，所以较流行的做法是 Stack 结构下含一个数组。如果空间实在紧张，也可用链表实现，且去掉表头。
栈的链式表示结构图：
用js数组可以非常简单地实现栈的顺序表示，故这里不赘述。这里主要讲解一下栈的链式表示。
1 // 找的链式表示 2 function Stack() { 3 this.top = null; 4 this.size = 0; 5 } 6 module.exports = Stack; 7 Stack.prototype = { 8 constructor: Stack, 9 push: function (data) { 10 var node = { 11 data: data, 12 next: null 13 }; 14 15 node.next = this.top; 16 this.top = node; 17 this.size++; 18 }, 19 peek: function () { 20 return this.top === null ? 21 null : 22 this.top.data; 23 }, 24 pop: function () { 25 if (this.top === null) return null; 26 27 var out = this.top; 28 this.top = this.top.next; 29 30 if (this.size > 0) this.size--; 31 32 return out.data; 33 }, 34 clear: function () { 35 this.top = null; 36 this.size = 0; 37 }, 38 displayAll: function () { 39 if (this.top === null) return null; 40 41 var arr = []; 42 var current = this.top; 43 44 for (var i = 0, len = this.size; i < len; i++) { 45 arr[i] = current.data; 46 current = current.next; 47 } 48 49 return arr; 50 } 51 }; 52 53 var stack = new Stack(); 54 55 stack.push(1); 56 stack.push(‘asd‘); 57 58 stack.pop(); 59 stack.push({a: 1}); 60 console.log(stack);
相关单元测试：
1 describe(‘stack tests‘, function(){ 2 var stack = new Stack(); 3 4 it(‘should push into stack‘, function(){ 5 stack.push(1); 6 expect(stack.peek()).toBe(1); 7 stack.push(‘asd‘); 8 expect(stack.peek()).toBe(‘asd‘); 9 expect(stack.size).toBe(2); 10 }); 11 12 it(‘should pop from stack‘, function(){ 13 stack.pop(); 14 expect(stack.peek()).toBe(1); 15 expect(stack.size).toBe(1); 16 stack.push({a: 1}); 17 expect(stack.peek()).toEqual({a: 1}); 18 expect(stack.size).toBe(2); 19 }); 20 21 it(‘should be an empty stack‘, function(){ 22 stack.pop(); 23 expect(stack.peek()).toBe(1); 24 stack.pop(); 25 expect(stack.peek()).toBe(null); 26 expect(stack.size).toBe(0); 27 }); 28 });
示例1：数值进制转换
公式： N = (N / d) * d + N % d
N：十进制数值， d：需要转换的进制数
1 function numTransform(number, rad) { 2 var s = new Stack(); 3 4 while (number) { 5 s.push(number % rad); 6 number = parseInt(number / 8, 10); 7 } 8 9 var arr = []; 10 while (s.top) { 11 arr.push(s.pop()); 12 } 13 console.log(arr.join(‘‘)); 14 } 15 16 numTransform(1348, 8); 17 numTransform(1348, 2);
示例2：括号匹配检查
1 function bracketsMatch(str) { 2 var stack = new Stack(); 3 var text = ‘‘; 4 5 for (var i = 0, len = str.length; i < len; i++) { 6 var c = str[i]; 7 if (c === ‘[‘) { 8 stack.push(c); 9 } else if (c === ‘]‘) { 10 if (!stack.top || stack.pop() !== ‘[‘) throw new Error(‘unexpected brackets:‘ + c); 11 } else { 12 text += c; 13 } 14 } 15 console.log(text); 16 } 17 18 console.log(bracketsMatch(‘[asd]‘)); 19 20 function Matcher(left, right) { 21 this.left = left; 22 this.right = right; 23 this.stack = new Stack(); 24 } 25 Matcher.prototype = { 26 match: function (str) { 27 var text = ‘‘; 28 29 for (var i = 0, len = str.length; i < len; i++) { 30 var c = str[i]; 31 if (c === this.left) { 32 this.stack.push(c); 33 } else if (c === this.right) { 34 if (!this.stack.top || this.stack.pop() !== this.left) { 35 throw new Error(‘unexpected brackets:‘ + c); 36 } else { 37 text += ‘,‘; 38 } 39 } else { 40 text += c; 41 } 42 } 43 console.log(text); 44 return text; 45 } 46 }; 47 var m = new Matcher(‘{‘, ‘}‘); 48 m.match(‘[{123}123‘);
示例3：行编辑
1 function LineEditor(str) { 2 this.stack = new Stack(); 3 this.str = str || ‘‘ 4 } 5 LineEditor.prototype = { 6 getResult: function () { 7 var stack = this.stack; 8 var str = this.str; 9 for (var i = 0, len = str.length; i < len; i++) { 10 var c = str[i]; 11 switch (c) { 12 case ‘#‘: 13 stack.pop(); 14 break; 15 case ‘@‘: 16 stack.clear(); 17 break; 18 default: 19 stack.push(c); 20 break; 21 } 22 } 23 24 var result = ‘‘; 25 var current = stack.top; 26 while (current) { 27 result = current.data + result; 28 current = current.next; 29 } 30 31 return result; 32 } 33 }; 34 35 var le = new LineEditor(‘whli##ilr#e(s#*s)36 \noutcha@putchar(*s=#++)‘); 37 console.log(le.getResult());
示例4：表达式求值
1 // from： http://wuzhiwei.net/ds_app_stack/ 2 3 var prioty = { 4 "+": 1, 5 "-": 1, 6 "%": 2, 7 "*": 2, 8 "/": 2, 9 "^": 3, 10 "(": 0, 11 ")": 0, 12 "`": -1 13 }; 14 15 function doop(op, opn1, opn2) { 16 switch (op) { 17 case "+": 18 return opn1 + opn2; 19 case "-": 20 return opn1 - opn2; 21 case "*": 22 return opn1 * opn2; 23 case "/": 24 return opn1 / opn2; 25 case "%": 26 return opn1 % opn2; 27 case "^": 28 return Math.pow(opn1, opn2); 29 default: 30 return 0; 31 } 32 } 33 34 function opcomp(a, b) { 35 return prioty[a] - prioty[b]; 36 } 37 38 function calInfixExpression(exp) { 39 var cs = []; 40 var ns = []; 41 exp = exp.replace(/\s/g, ""); 42 exp += ‘`‘; 43 if (exp[0] === ‘-‘) { 44 exp = "0" + exp; 45 } 46 var c; 47 var op; 48 var opn1; 49 var opn2; 50 for (var i = 0; i < exp.length; ++i) { 51 c = exp[i]; 52 // 如果是操作符 53 if (c in prioty) { 54 // 如果右边不是左括号且操作符栈的栈顶元素优先权比右边大 55 // 循环遍历进行连续运算 56 while (c != ‘(‘ && cs.length && opcomp(cs[cs.length - 1], c) >= 0) { 57 // 出栈的操作符 58 op = cs.pop(); 59 // 如果不是左括号或者右括号，说明是运算符 60 if (op != ‘(‘ && op != ‘)‘) { 61 // 出栈保存数字的栈的两个元素 62 opn2 = ns.pop(); 63 opn1 = ns.pop(); 64 // 将与操作符运算后的结果保存到栈顶 65 ns.push(doop(op, opn1, opn2)); 66 } 67 } 68 // 如果右边不是右括号，保存到操作符栈中 69 if (c != ‘)‘) cs.push(c); 70 } else { 71 // 多位数的数字的情况 72 while (!(exp[i] in prioty)) { 73 i++; 74 c += exp[i]; 75 } 76 ns.push(parseFloat(c)); 77 i--; 78 } 79 } 80 return ns.length ? ns[0] : NaN; 81 } 82 83 var exp1 = calInfixExpression(‘5+3*4/2-2^3+5%2‘); 84 console.log(exp1);
栈 -- 顺序存储表示和链式表示及示例,布布扣,bubuko.com
原文：http://www.cnblogs.com/webFrontDev/p/3683325.html
