栈算法题

1.用栈实现队列【L232】

1. 双栈

var MyQueue = function() {
  this.inStack = [];
  this.outStack = [];
};

MyQueue.prototype.push = function(x) {
  this.inStack.push(x);
};

MyQueue.prototype.pop = function() {
  if (!this.outStack.length) {
    this.in2out();
  }
  return this.outStack.pop();
};

MyQueue.prototype.peek = function() {
  if (!this.outStack.length) {
    this.in2out();
  }
  return this.outStack[this.outStack.length - 1];
};

MyQueue.prototype.empty = function() {
  return this.outStack.length === 0 && this.inStack.length === 0;
};

MyQueue.prototype.in2out = function() {
  while (this.inStack.length) {
    this.outStack.push(this.inStack.pop());
  }
};

有效的括号【L20】

1. 栈

// 解法一
let isValid = function(s) {
  let stack = [],
    length = s.length;
  if (length % 2) return false;
  for (let item of s) {
    switch (item) {
      case "{":
      case "[":
      case "(":
        stack.push(item);
        break;
      case "}":
        if (stack.pop() !== "{") return false;
        break;
      case "]":
        if (stack.pop() !== "[") return false;
        break;
      case ")":
        if (stack.pop() !== "(") return false;
        break;
    }
  }
  return !stack.length;
};

// 解法二
var isValid = function(s) {
  s = s.split("");
  let sl = s.length;
  if (sl % 2) return false;
  let map = new Map([
    [")", "("],
    ["]", "["],
    ["}", "{"],
  ]);
  let stack = [];
  for (let i of s) {
    if (map.get(i)) {
      if (stack[stack.length - 1] !== map.get(i)) return false;
      else stack.pop();
    } else {
      stack.push(i);
    }
  }
  return !stack.length;
};