RE4wwtR.jpg

20. 有效的括号

利用栈先进后出的特性

let isValid = function(s) {
  let map = {
    '{': '}',
    '[': ']',
    '(': ')'
  }
  let stack = []
  for (let i = 0; i < s.length; i++) {
    if (map[s[i]]) {
      stack.push(s[i])
    } else if (s[i] !== map[stack.pop()]) {
      return false
    }
  }
  return stack.length === 0
}

232. 用栈实现队列

栈的特点是先进后出，队列的特点是先进先出

/**
 * Initialize your data structure here.
 */
var MyQueue = function() {
    this.input = []
    this.output = []
};

/**
 * Push element x to the back of queue. 
 * @param {number} x
 * @return {void}
 */
MyQueue.prototype.push = function(x) {
    this.input.push(x)
};

/**
 * Removes the element from in front of queue and returns that element.
 * @return {number}
 */
MyQueue.prototype.pop = function() {
    while(this.input.length) {
        this.output.push(this.input.pop())
    }
    var first = this.output.pop()

    while(this.output.length) {
        this.input.push(this.output.pop())
    }
    return first
};

/**
 * Get the front element.
 * @return {number}
 */
MyQueue.prototype.peek = function() {
    return this.input[0]
};

/**
 * Returns whether the queue is empty.
 * @return {boolean}
 */
MyQueue.prototype.empty = function() {
    return !this.input.length && !this.output.length
};

844. 比较含退格的字符串

var backspaceCompare = function (S, T) {
 // 先进后出 用stack
 let filterStr = (str) => {
   let stack = [];
   for (let p of str) {
     p === '#' ? stack.pop() : stack.push(p);
   }
   return stack.join('');
 }
 return filterStr(S) === filterStr(T);
};