第四章栈（1）

一、Stack（）类

function Stack(){ this.dataStore=[]; this.top=0; this.push=push; this.pop=pop; this.peek=peek; this.clear=clear; this.length=length; this.isEmpty=isEmpty; } function push(element){ this.dataStore[this.top++]=element; return this.top; } function pop(){ return this.dataStore[--this.top]; } function peek(){ return this.dataStore[this.top-1]; } function length(){ return this.top; } function clear(){ this.top=0; } function isEmpty(){ if(this.length()<=0){ return true; }else{ return false; } } //测试Stack类的实现 let s=new Stack(); s.push("Tom"); s.push("Jack"); s.push("Bryan"); console.log("length: " + s.length());//3 console.log(s.peek());//Bryan let popped = s.pop(); console.log("The popped element is: " + popped);//Bryan console.log(s.peek());//Jack s.push("Cynthia"); console.log(s.peek());//Cynthia s.clear(); console.log("length: " + s.length());//0 console.log(s.peek());//undefined s.push("Clayton"); console.log(s.peek());//Clayton

二、栈的应用

1.数制间的相互转换:假设想将数字n转换为以b为基数的数字，实现转换的算法如下
   (1) 最高位为 n % b,将此位压入栈
   (2) 使用 n/b代替n
   (3) 重复步骤1 和 2，直到 n 等于 0，且没有余数。
   (4) 持续将栈内元素弹出,直到栈为空,依次将这些元素排列,就得到转换后数字的字符串形式

function mulBase(num,base){ let s=new Stack(); do{ s.push(num%base); num=Math.floor(num /= base); }while(num>0); let converted=""; while(s.length()>0){ converted +=s.pop(); } return converted; } let num=31; let base=2; let newNum=mulBase(num,base); console.log(num+" converted to base "+base+" is "+newNum);//11111 num =125; base=8; newNum=mulBase(num,base); console.log(num+" converted to base "+base+" is "+newNum);//175

2.判断给定字符串是否是回文

function isPalindrome(word){ let s=new Stack(); for(let i=0;i<word.length;i++){ s.push(word[i]); } let rword=""; while(s.length()>0){ rword +=s.pop(); } if(word==rword){ return true; }else{ return false; } } let word="hello"; if(isPalindrome(word)){ console.log(word+" is a palindrome"); }else{ console.log(word+"is not a palindrome"); } word='racecar'; if(isPalindrome(word)){ console.log(word+" is a palindrome"); }else{ console.log(word+"is not a palindrome"); }

3.递归

function factorial(n){ if(n==0){ return 1; }else{ return n*factorial(n-1); } } function fact(n){ let s=new Stack(); while(n>1){ s.push(n--); } let product=1; while(s.length()>0){ product *=s.pop(); } return product; } console.log(factorial(6));//720 console.log(fact(6));//720

三、习题

1.栈可以用来判断一个算术表达式中的括号是否匹配。编写一个函数，该函数接受一个算术表达式作为参数，返回括号缺失的位置。下面是一个括号不匹配的算术表达式的例子：2.3 + 23 / 12 + (3.14159×0.24。

function signUp(stack,ele){ switch(ele){ case "{": case "[": case "(": stack.push(ele); break; case "}": case "]": case ")": let topEle=stack.pop(); console.log(stack.top); if((topEle=='{'&& ele=='}')||(topEle=='['&& ele==']')||(topEle=='('&& ele==')')){ console.log('ok'); }else{ console.log("括号不匹配"); return; } break; } } let stack=new Stack(); let str="2.3 + 23 / 12 + ( 3.14159 × 0.24 "; str=str.split(" "); for(let i=0;i<str.length;i++){ signUp(stack,str[i]); } if(!stack.isEmpty()){ console.log("括号不匹配"); }