Day 11 | 232.用栈实现队列、225.用队列实现栈、20.有效的括号、1047.删除字符串中的所有相邻重复项

Leetcode 232.用栈实现队列

题目：232.用栈实现队列

初始思路

之前写过用数组实现队列，但是调用了数组的一些API，这里题目要求必须要用两个栈。

代码

var MyQueue = function () {
    // 输入和输出栈
    this.stackIn = []
    this.stackOut = []
};
/** 
 * @param {number} x
 * @return {void}
 * 将元素 x 推到队列的末尾
 */
MyQueue.prototype.push = function (x) {
    this.stackIn.push(x)
};
/**
 * @return {number}
 * 从队列的开头移除并返回元素
 */
MyQueue.prototype.pop = function () {
    const size = this.stackOut.length
    // 如果输出栈不为空的话，直接弹出即可
    if (size) {
        return this.stackOut.pop()
    }
    // 如果输出栈为空的话，要把输出栈的所有元素搬到输出栈中开始弹出
    while (this.stackIn.length) {
        this.stackOut.push(this.stackIn.pop())
    }
    return this.stackOut.pop()
};
/**
 * @return {number}
 * 返回队列开头的元素
 */
MyQueue.prototype.peek = function () {
    // pop函数返回队列开头的元素
    const x = this.pop()
    // 改变了队列，再改回去
    this.stackOut.push(x)
    return x
};
/**
 * @return {boolean}
 * 如果队列为空，返回 true ；否则，返回 false
 */
MyQueue.prototype.empty = function () {
    return !this.stackIn.length && !this.stackOut.length
};
/**
 * Your MyQueue object will be instantiated and called as such:
 * var obj = new MyQueue()
 * obj.push(x)
 * var param_2 = obj.pop()
 * var param_3 = obj.peek()
 * var param_4 = obj.empty()
 */

感想

1. 使用输入和输出栈。
2. 在push数据的时候，只要数据放进输入栈就好
3. 在pop的时候，操作就复杂一些，输出栈如果为空，就把进栈数据全部导入进来（注意是全部导入），再从出栈弹出数据，如果输出栈不为空，则直接从出栈弹出数据就可以了。
4. peek很巧妙，通过pop直接获取队列开头的元素，然后再放回去。
5. 如何判断队列为空呢？如果进栈和出栈都为空的话，说明模拟的队列为空了。

Leetcode 225.用队列实现栈

题目：225.用队列实现栈

初始思路

还是用数组，如果是队列的话，那数组只能用push和shift方法，因为只能在队列开头操作

代码

var MyStack = function () {
    this.queue = []
};
/** 
 * @param {number} x
 * @return {void}
 * 将元素 x 压入栈顶。
 */
MyStack.prototype.push = function (x) {
    this.queue.push(x)
};
/**
 * @return {number}
 * 移除并返回栈顶元素。
 */
MyStack.prototype.pop = function () {
    let size = this.queue.length
    while (size-- > 1) {
        this.queue.push(this.queue.shift())
    }
    return this.queue.shift()
};
/**
 * @return {number}
 * 返回栈顶元素。
 */
MyStack.prototype.top = function () {
    const x = this.pop()
    this.queue.push(x)
    return x
};
/**
 * @return {boolean}
 * 如果栈是空的，返回 true ；否则，返回 false 。
 */
MyStack.prototype.empty = function () {
    return !this.queue.length
};
/**
 * Your MyStack object will be instantiated and called as such:
 * var obj = new MyStack()
 * obj.push(x)
 * var param_2 = obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.empty()
 */

var MyStack = function () {
    this.queue1 = [];
    this.queue2 = [];
};
/**
 * Push element x onto stack. 
 * @param {number} x
 * @return {void}
 */
MyStack.prototype.push = function (x) {
    this.queue1.push(x);
};
/**
 * Removes the element on top of the stack and returns that element.
 * @return {number}
 */
MyStack.prototype.pop = function () {
    // 减少两个队列交换的次数， 只有当queue1为空时，交换两个队列
    // 也就是当queue1中的元素都弹出完毕的时候
    if (!this.queue1.length) {
        [this.queue1, this.queue2] = [this.queue2, this.queue1];
    }
    // 把queue1中除了最后一个元素都放入queue2
    while (this.queue1.length > 1) {
        this.queue2.push(this.queue1.shift());
    }
    // 弹出最后面的元素
    return this.queue1.shift();
};
/**
 * Get the top element.
 * @return {number}
 */
MyStack.prototype.top = function () {
    const x = this.pop();
    this.queue1.push(x);
    return x;
};
/**
 * Returns whether the stack is empty.
 * @return {boolean}
 */
MyStack.prototype.empty = function () {
    return !this.queue1.length && !this.queue2.length;
};

感想

1. 单队列实现很精妙。在pop方法中，把除了栈顶的元素先弹出在压入，不会改变顺序。
2. 两个队列实现中，pop方法：把que1最后面的元素以外的元素都备份到que2，然后弹出最后面的元素，再把其他元素从que2导回que1。

Leetcode 20.有效的括号

题目：20.有效的括号

初始思路

以前在数据结构课上听过，应该是栈的经典应用。在压栈过程中，如果左括号遇到了匹配的右括号就弹栈。

代码

var isValid = function (s) {
    let stack = []
    for (let i = 0; i < s.length; i++) {
        let ch = s[i]
        // 如果是左括号就入栈
        if (ch === '(' || ch === '[' || ch === '{') {
            stack.push(ch)
        } else if (ch === ')' || ch === ']' || ch === '}') {
            // 如果是右括号就和栈顶元素进行匹配
            // 栈顶元素
            const p = stack[stack.length - 1]
            if ((ch === ')' && p === '(') || (ch === ']' && p === '[') || (ch === '}' && p === '{')) {
                // 如果匹配成功就弹出栈顶这个左括号，继续匹配
                stack.pop()
            } else {
                return false
            }
        }
    }
    // 当栈内元素都弹出的时候，匹配完成
    return stack.length === 0
};

var isValid = function (s) {
  const stack = [];
  for (let i = 0; i < s.length; i++) {
    let c = s[i];
    switch (c) {
      case '(':
        stack.push(')');
        break;
      case '[':
        stack.push(']');
        break;
      case '{':
        stack.push('}');
        break;
      default:
        if (c !== stack.pop()) {
          return false;
        }
    }
  }
  return stack.length === 0;
};
// 简化版本
var isValid = function(s) {
    const stack = [], 
        map = {
            "(":")",
            "{":"}",
            "[":"]"
        };
    for(const x of s) {
        if(x in map) {
            stack.push(x);
            continue;
        };
        if(map[stack.pop()] !== x) return false;
    }
    return !stack.length;
};

感想

1. 实现起来其实不困难，挺好写的。但是简单写起来有些繁琐，比起简化版版本来说有些笨拙。

Leetcode 1047.删除字符串中的所有相邻重复项

题目：1047.删除字符串中的所有相邻重复项

初始思路

自己尝试用栈模拟了一下，感觉挺对的。再看一下题解，原来自己模拟的不对，好吧！

代码

var removeDuplicates = function (s) {
    let stack = []
    for (const ch of s) {
        // 栈顶元素
        let p = stack[stack.length - 1]
        if (stack.length && p === ch) {
            // 如果栈不为空并且匹配上了就弹出
            stack.pop()
        } else {
            stack.push(ch)
        }
    }
    return stack.join('')
};

var removeDuplicates = function (s) {
    // 解构赋值成数组
    s = [...s]
    // 指向栈顶元素的下标
    let top = -1
    for (let i = 0; i < s.length; i++) {
        // 栈为空哦或者不匹配
        if (top === -1 || s[top] !== s[i]) {
            // 入栈
            s[++top] = s[i]
        } else {
            // 出栈
            top--
        }
    }
    // 栈顶元素下标 + 1 为栈的长度
    s.length = top + 1
    return s.join('')
}

感想

1. 思路挺简单的。
2. 为什么还能用双指针？