JavaScript描述数据结构之栈

栈

特点:先进后出

栈的实现

function Stack(){
  this.dataStore = [];//用数组保存栈内元素
  this.top = 0;//栈顶；
  this.push = push;
  this.pop = pop;
  this.peek = peek;
  this.length= length;
}
//入栈
function push(element){
   this.dataStore[this.top++] = element;
}
//出栈
function pop(){
  return this.dataStore[--this.top];
}
//读取栈顶元素
function peek(){
  return this.dataStore[this.top - 1];
}
//读取栈的长度
function length(){
 return this.dataStore.length;
}

使用栈的实例

• 数制间的转换

将数值n转换为以b为基数的数字，实现转换的算法思路：
（1）最高位为n%b,将此位压入栈；
（2）使用n/b代替n.
（3）重复步骤1和2，知道n等于0，且没有余数
（4）持续将栈内元素弹出，直道栈为空，依次将这些元素排列

function mulBase(n,b){
  var s =new Stack();
  var num = n;
  do{
    s.push(n%b);
    num = Math.floor(num /=b);
  }while(num >0)
  var c = "";
  while(s.length()>0){
    c += s.pop();
  }
  return s;
}

• 回文

回文是指一个单词从前往后和从后往前写都是一样的

function isPalindrome(word){
  var s = new Stack();
  for(var i=0;i<word.length;i++){
    s.push(word[i]);
  }
  var rword = "";
  while(s.length()>0){
    rword += s.pop();
  }
  if(word == rword){
    return true;
  }
  return false;
}

• 使用栈来判断一个算术表达式中的括号是否匹配，比如：2.3+23/12+（3.14*0.24

   function check(w){
        var s = new Stack();
        var arr = w.split("");
        //console.log(arr)
        var value = "";
        for(var i=0;i<arr.length;i++){
            if(["{","(","["].indexOf(arr[i]) != -1){
                s.push(arr[i]);
            }else{
                if(s.length() > 0){
                    switch(arr[i]){
                        case "}":value = s.peek();if(value == "{"){s.pop();break;}else{return i}
                        case ")":value = s.peek();if(value == "("){s.pop();break;}else{return i}
                        case "]":value = s.peek();if(value == "["){s.pop();break;}else{return i}
                        default:break;
                    }
                }
            }
        }
        
        if(s.length()>0){
            console.log(111)
            return w.length;
        }else{
            return -1;
        }
    }
    
    var expression = '2.3 + 23 / 12 + (3.14159 * 0.24' ;
    var end = check(expression)
    console.log(end);