JS算法探险之栈(Stack)

let stack = [];
stack.push(1);
stack.push(2);
==== 入栈 1、2====

stack.pop() // 2出栈
stack.pop() // 1出栈

class Stack {
 constructor() {
   this.items = []; 
 }
 // 添加element到栈顶
 push(element) {
   this.items.push(element);
 }
 // 移除栈顶的元素,同时返回被移除的元素
 pop() {
   return this.items.pop();
 }
 // 返回栈顶的元素，不对栈做任何修改
 peek() {
   return this.items[this.items.length - 1];
 }
 // 如果栈里没有任何元素就返回`true`,否则返回`false`
 isEmpty() {
   return this.items.length === 0;
 }
 // 返回栈里的元素个数
 size() {
   return this.items.length;
 } 
 // 移除栈里所有的元素
 clear() {
   this.items = [];
 } 
}

function evalRPN(tokens){
  let stack = new Stack();
  for(let token of tokens){
    switch(token){
        // 处理操作符
        case "+":
        case "-":
        case "*":
        case "/": 
            // 在源数据中，靠后的操作数
            let back = stack.pop(); 
            // 在源数据中，靠前的操作数
            let prev = stack.pop();
            // 计算操作数，并将其入栈处理
            stack.push(
                calculate(prev,back,token)
                );
            break;
        default:
            // 处理操作数，直接入栈
            stack.push(parseInt(token));
      }
    }
    // 操作符都处理完，且栈中只有一个数据
    return stack.pop();
}

fucntion calculate(prev,back,operator){
    switch(operator){
        case "+":
            return prev + back;
        case "-":
            return prev - back;
        case "*":
            return prev * back;
        case "/":
            return (prev/back)>>0; // 数据取整
        default:
            return 0;
    }
}

function asteroidCollision(asteroids){
  let stack = new Stack();
  for(let as of asteroids){
        // 当前元素向左飞行，并且该元素的绝对值比栈顶元素大
        while(!stack.empty() 
              && stack.peek()>0
              && stack.peek()<-as
              ){
                stack.pop();
              }
        
        // 当前元素向左飞行,当前元素和栈顶元素体积一样 (需要互相抵消)   
        if(stack.length 
           && as<0
           && stack.peek()==-as
           ){
            stack.pop();
        }else if(
                as >0  //当前元素向右飞行
                || stack.empty() // 栈为空 （初始化）
                // 当前元素向左飞行(在经过对比后，还是无法消除) 
                || stack.peek()<0
                ){
                  stack.push(as)
                }
    }
    return stack;
}

function isValid (s) {
    let stack = new Stack();
    // 遍历 字符串
    for(let c of s){
        // 遇到左括号，将与其匹配的右括号入栈处理
        if(c==='('){
            stack.push(')')
        }else if(c==='['){
            stack.push(']')
        }else if(c==='{'){
            stack.push('}')
        // 遇到右括号
        // 1. 判断栈内是否有括号，如果没有，那说明此时匹配不了
        // 2. 满足①的情况下，判断此时字符是否和栈顶元素匹配
        }else if(stack.length ===0 || stack.pop()!==c){
            return false;
        }
    }
    // 最后再验证一下，栈是否为空，如果不为空，说明还有未匹配的括号
    return !stack.length;
};

function dailyTemperatures(temperatures){
   // 定义一个与源数组相同的数组，用于存储最后结果
  let result = new Array(temperatures.length);
  let stack = new Stack();
  for(let i = 0;i<temperatures.length;i++){
    // stack 非空，且当前的温度大于栈顶温度
    while(!stack.empty()
          && temperatures[i]>temperatures[stack.peek()]){
          // 取出，存于stack中的满足条件的温度的下标
          let prev = stack.pop();
          // 计算等待天数 并将其存入result[prev]中
          result[prev] = i - prev;
    }
    // 将当前下标存入stack中
    stack.push(i)
  }
  return result;
}

function largestRectangleArea(heights){
  let maxArae = 0;
  for(let i=0;i<heights.length;i++){
    let min = heights[i];
    for(let j=i;j<heights.length;j++){
      min = Math.min(min,heights[j]);
      let area = min * (j -i +1);
      maxArea = Math.max(maxArea,area)
    }
  }
  return maxArea;
}

function selectionSort(arr){
  let len = arr.length;
  if(len<2) return arr; // 处理边界值
  
  let i,j,minIndex;
  // 外层循环: 控制迭代轮次
  for(i=0;i<len-1;i++){
    minIndex = i;
    // 内层循环：从内层循环中找到最小值的位置
    for(j=i+1;j<len;j++){
      // 在未排区域寻找最小的数，并记录其位置j
      if(arr[j]<arr[minIndex]) minIndex = j;
    }
    // 内层循环完毕，最小值确定，和已排区间最后一位交互位置
    swap(arr,i,minIndex);
  }
  return arr;
}

function largestRectangleArea(heights){
  let stack = new Stack();
  stack.push(-1);
  
  let maxArea = 0;
  for(let i =0;i<heights.length;i++){
    // 一边遍历，一边计算，当前高度，比栈顶高度小的数据
    // 此时求的是以栈顶元素为高的面积
    // 直到当前元素比栈顶元素都小时，才退出
    while(stack.peek()!=-1
       && heights[stack.peek()] >= heights[i]){
       let height = heights[stack.pop()];
       let width = i - stack.peek() -1;
       maxArea = Math.max(maxArea,height * width)
       }
    // 此时当前元素高度，比栈顶元素高，入栈处理
    stack.push(i);
  }
  // 在处理完后，栈中还存在元素
  // 这元素在后续的遍历中没找到比它矮的，所以，还需要进行相同操作
  while(stack.peek()!=-1){
    let height = heights[stack.pop()];
    let width = heights.length - stack.peek() -1;
    maxArea = Math.max(maxArea,height * width)
  }
  return maxArea;
}