Skip to main content
 首页 » 编程设计

javascript实现数据结构与算法系列:栈-顺序存储表示和链式表示及示例

2022年07月16日27lhb25

栈(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);

栈与递归调用的实现:

栈的另一个重要应用是在程序设计语言中实现递归调用。

递归调用:一个函数(或过程)直接或间接地调用自己本身,简称递归(Recursive)。

递归是程序设计中的一个强有力的工具。因为递归函数结构清晰,程序易读,正确性很容易得到证明。

为了使递归调用不至于无终止地进行下去,实际上有效的递归调用函数(或过程)应包括两部分:递推规则(方法),终止条件。

为保证递归调用正确执行,系统设立一个“递归工作栈”,作为整个递归调用过程期间使用的数据存储区。

每一层递归包含的信息如:参数、局部变量、上一层的返回地址构成一个“工作记录” 。每进入一层递归,就产生一个新的工作记录压入栈顶;每退出一层递归,就从栈顶弹出一个工作记录。

从被调函数返回调用函数的一般步骤:

(1) 若栈为空,则执行正常返回。

⑵ 从栈顶弹出一个工作记录。

⑶ 将“工作记录”中的参数值、局部变量值赋给相应的变量;读取返回地址。

⑷ 将函数值赋给相应的变量。

(5) 转移到返回地址。

相关:

javascript实现数据结构与算法系列


本文参考链接:https://www.cnblogs.com/webFrontDev/p/3683325.html