09. 用两个栈实现队列

来源

https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/

题目

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 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]

提示：

• 1 <= values <= 10000
• 最多会对 appendTail、deleteHead 进行 10000 次调用

思路

一个栈stackIn用来压入，一个栈stackOut用来弹出，弹出时，如果stackOut没有元素，则把stackOut的元素依次弹出压入stackOut中，此时元素的顺序会逆转（先入变成了先出），然后弹出；如果stackOut有元素，则直接弹出。

复杂度：压入 O(1),弹出 O(n)。

一定要在stackOut清空之后，再把stackIn的元素灌入stackOut，否则先入的就不能先出了，顺序就乱了。

解题

var CQueue = function () {
  this.stackIn = [];
  this.stackOut = [];
  // 只用 push 和 pop
};

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

/**
 * @return {number}
 */
CQueue.prototype.deleteHead = function () {
  if (this.stackOut.length === 0 && this.stackIn.length === 0) return -1;
  if (this.stackOut.length === 0) {
    while (this.stackIn.length > 0) {
      this.stackOut.push(this.stackIn.pop());
    }
  }
  return this.stackOut.pop();
};

/**
 * Your CQueue object will be instantiated and called as such:
 * var obj = new CQueue()
 * obj.appendTail(value)
 * var param_2 = obj.deleteHead()
 */

题目 2

用两个队列实现栈

https://leetcode-cn.com/problems/implement-stack-using-queues/

思路

把元素从一个队列灌入另一个队列，直到剩最后一个元素，弹出此元素，然后两个队列指针互换。

复杂度：压入 O(1),弹出 O(n)。

解题

/**
 * Initialize your data structure here.
 */
var MyStack = function () {
  this.queueIn = [];
  this.queueOut = [];
  // 只能用push、shift
};

/**
 * Push element x onto stack.
 * @param {number} x
 * @return {void}
 */
MyStack.prototype.push = function (x) {
  this.queueIn.push(x);
};

/**
 * Removes the element on top of the stack and returns that element.
 * @return {number}
 */
MyStack.prototype.pop = function () {
  if (this.queueIn.length === 0) return null;
  while (this.queueIn.length > 1) {
    this.queueOut.push(this.queueIn.shift());
  }
  const res = this.queueIn.shift();
  const temp = this.queueIn;
  this.queueIn = this.queueOut;
  this.queueOut = temp;
  return res;
};

/**
 * Get the top element.
 * @return {number}
 */
MyStack.prototype.top = function () {
  if (this.queueIn.length === 0) return null;
  while (this.queueIn.length > 1) {
    this.queueOut.push(this.queueIn.shift());
  }
  const res = this.queueIn.shift();
  this.queueOut.push(res);
  const temp = this.queueIn;
  this.queueIn = this.queueOut;
  this.queueOut = temp;
  return res;
};

/**
 * Returns whether the stack is empty.
 * @return {boolean}
 */
MyStack.prototype.empty = function () {
  return this.queueIn.length === 0;
};

/**
 * 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()
 */

从零开始学算法
https://github.com/daqi/re0-algorithm/issues
欢迎 start & watch