每天一道leetcode(Day 65)

剑指 Offer 09. 用两个栈实现队列

题目描述

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead  操作返回 -1 )

示例

• 示例 1：

输入：
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
输出：[null,null,3,-1]

• 示例 2：

输入：
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]

解题思路

两个栈一个负责入队操作(pushStack)，一个负责出队操作(popStack)。当元素入队时，则在 pushStack 栈顶压入元素；要出队时，考虑到栈和队列的特点(栈是先进后出，队是先进先出)，所以将 pushStack 中的元素依次出栈然后压入 popStack 中，popStack 中元素的出栈顺序即为队列的出队顺序；

注意：在 popStack 出栈之前需要判断栈是否为空，如果不为空则直接出栈栈顶元素即可；若为空，则将 pushStack 中的元素按顺序出栈后在压入 popStack 即可；否则出队顺序会乱掉；
具体操作如下图所示：

代码

const CQueue = function () {
  this.pushStack = [];
  this.popStack = [];
};

/**
 * @param {number} value
 * @return {void}
 */
CQueue.prototype.appendTail = function (value) {
  this.pushStack.push(value);
};

/**
 * @return {number}
 */
CQueue.prototype.deleteHead = function () {
  if (this.popStack.length) {
    return this.popStack.pop();
  } else {
    if (this.pushStack.length) {
      while (this.pushStack.length) {
        this.popStack.push(this.pushStack.pop());
      }
      return this.popStack.pop();
    } else {
      return -1;
    }
  }
};

参考

剑指 Offer 09. 用两个栈实现队列