数据结构与算法Javascript描述（一）栈

水深无声 2022-08-21 02:12 183阅读 0赞

栈的特点： 后入先出。

Stack类：

<span style="white-space:pre">			</span>function Stack() {
    				this.dataSource = [];
    				this.top = 0;
    				this.push = push;
    				this.pop = pop;
    				this.peek = peek;
    				this.clear = clear;
    				this.length = length;
    
    			}
    			function push(element){
    				this.dataSource[this.top++] = element;
    			}
    			function pop() {
    				return this.dataSource[--this.top];
    			}
    			function peek() {
    				return this.dataSource[this.top-1];
    			}
    			function clear() {
    				this.top = 0;
    			}
    			function length() {
    				return this.top;
    			}

使用举例：

1、数制间的相互转换（此算法只针对基数为2~9 的情况。）

可以利用栈将一个数字从一种数制转换为另一种数制。例如，将数字n转换为以b为基数的数字，实现如下。

（1）最高位为n%b,将此位压入栈。

（2）使用n/b代替n。

（3）重复步骤1 和2，直到n 等于0，且没有余数。

（4）持续将栈内元素弹出，直到栈为空，依次将这些元素排列，就得到转换后数字的字符串形式。

//将一个数转换为指定进制的数
    			function mulBase(num, base) {
    				var s = new Stack();
    				do{
    					s.push(num%base);
    					num = Math.floor(num/=base);
    				}while(num>0)
    				var converted = "";
    				while(s.length()>0) {
    					converted += s.pop();
    				}
    				return converted;
    			}

2、回文

字符串完整压入栈内后，通过持续弹出栈中的每个字母就可以得到一个新字符串，该字符串刚好与原来的字符串顺序相反。我们只需要比较这两个字符串即可，如果它们相等，就是一个回文。

//判断字符串是否为回文
    			function isPalindrome(word) {
    				var s = new Stack();
    				var i,len;
    				for(i=0,len = word.length;i<len;i++){
    					s.push(word.charAt(i));
    				}
    				var reverse = "";
    				while(s.length()>0) {
    					reverse += s.pop();
    				}
    				if(word === reverse){
    					return 1;
    				}else {
    					return 0;
    				}
    			}

3、判断一个算术表达式中的括号是否匹配

//判断算术表达式中括号是否匹配
    			function isMatch(expression) {
    				var s = new Stack(),
    				    i = 0,
    				    len = expression.length,
    				    match = true,
    				    chsr = '';
    				while(i<len) {
    					chsr = expression[i];
    					if(chsr === '('){
    						s.push(expression[i]);
    					}else if(chsr === ')') {
    						s.pop();
    					}
    					i++;
    				}
    				if(s.length()>0) {
    					return false;
    				} else {
    					return true;
    				}
    			}

4、将中缀表达式转换为后缀表达式

//将中缀表达式转换为后缀表达式
    			function inTopostFix(expression) {
    				var order = {'*':1, '/':1,"+":0,"-":0},
    					i = 0,
    					len = expression.length,
    					s = new Stack(),//符号栈
    					numStack = new Stack(),//数字栈
    					str = '',
    					c = '',
    					opera = '',
    					num = 0,
    					curOp = '',
    					num1 = 0,
    					num2 = 0;
    				while(i < len) {
    					c = expression.charAt(i);
    					if(!isNaN(parseInt(c))) {//当前字符是数字则压入数字栈
    						str = str + c + ' ';
    						numStack.push(c);
    					}else {
    						if(c === ')') {//当前字符是‘)’，符号和数字相应的出栈
    							while(s.length()&&s.peek() !== '(') {
    								curOp = s.pop();
    								str += curOp;
    								num1 = parseInt(numStack.pop());
    								num2 = parseInt(numStack.pop());
    								num = operator(num2, num1, curOp);
    								numStack.push(num);
    							}
    							s.pop();
    						}else if(c === '(' || c === '+' || c === '-'){
    							s.push(c);
    						}else  {//当前字符为'*'或'/'，则比较栈顶符号与当前符号的优先级
    							if(s.length()) {
    								opera = s.peek();
    								s.push(c);
    								str = str + expression.charAt(++i) + ' ';
    								numStack.push(expression.charAt(i));
    								if(order[opera] < order[s.peek()]) {
    									while(s.length()) {
    										curOp = s.pop();
    										str += curOp;
    										num1 = parseFloat(numStack.pop());
    										num2 = parseFloat(numStack.pop());
    										num = operator(num2, num1, curOp);
    										numStack.push(num);
    									}
    								}
    							}else {
    								s.push(c);
    							}
    						}
    					}
    					i++;
    				}
    				console.log(num);
    				return str;
    			}
    			function operator(num1, num2, op) {
    				var sum = 0;
    				switch(op) {
    					case '+':
    						sum = num1 + num2;
    						break;
    					case '-':
    						sum = num1 - num2;
    						break;
    					case '*':
    						sum = num1 *num2;
    						break;
    					case '/':
    						sum = num1 / num2;
    						break;
    					default: 
    					 	sum = 0;
    					 	break;
    				}
    				return sum;
    			}
    			console.log(inTopostFix("1+3*2-7/2"));