化栈为队

leetcode-栈- [剑指 Offer 09] 用两个栈实现队列 [面试题 03.04] 化栈为队

解题思路

两题都是相同题型通过栈实现队列 栈是先进后出的 所以只能使用数组的 push 和 pop 方法 myQueue.peek() 返回栈顶元素，但不在堆栈中删除它。 myQueue.pop() 返回栈顶元素，并在进程中删除它。 myQueue.empty() 如果队列是空的，则返回true，当堆栈包含元素时，返回false

   // 如 现在有两个栈
  stack1 = []
  stack2 = []
  // 我们用 push  往stack1里加入几个元素 
  stack1 = [1, 2, 3]
  // 现在我们要一个一个地取出头部的元素
  // 我们可以循环 stack1,  把 stack1 元素一个个取出来 放入到 stack2中
  stack1 = []
  stack2 = [3, 2, 1]
  // 这样就可以用 pop 取出 头部元素了, 其实就是翻转数组
  // 如果stack2不为空 我们就一直从 stack2 中取, 直到为空了 又重新把 stack1 中的元素放入 stack2 中
  //如
  stack1 = [4, 5]
  stack2 = [3, 2]
  // 现在 2 中有元素, 要出队的话直接从 2 中出, 直到为空
  stack2.pop()
  stack2.pop()   // 现在为空了
  // 重新循环 1 , 回到了上面开始的情况
  stack1 = []
  stack2 = [5, 4]

一 用两个栈实现队列

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

题解

var CQueue = function () {
  this.stack1 = [];
  this.stack2 = [];
};
/**
 * @param {number} value
 * @return {void}
 */
CQueue.prototype.appendTail = function (value) {
  this.stack1.push(value);
};
/**
 * @return {number}
 */
CQueue.prototype.deleteHead = function () {
  //为空将stack1的数组赋值给stack2;
  if (this.stack2.length === 0) {
    while (this.stack1.length > 0) {
      this.stack2.push(this.stack1.pop());
    }
  }
  return this.stack2.pop() || -1;
};
/**
 * Your CQueue object will be instantiated and called as such:
 * var obj = new CQueue()
 * obj.appendTail(value)
 * var param_2 = obj.deleteHead()
 */

二 化栈为队

实现一个MyQueue类，该类用两个栈来实现一个队列。

示例：

MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek();  // 返回 1
queue.pop();   // 返回 1
queue.empty(); // 返回 false

说明：

• 你只能使用标准的栈操作 — 也就是只有 push to top, peek/pop from top, size 和 is empty 操作是合法的。
• 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
• 假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）。

题解:

/**
 * Initialize your data structure here.
 */
var MyQueue = function () {
  this.stack1 = [];
  this.stack2 = [];
};
/**
 * Push element x to the back of queue.
 * @param {number} x
 * @return {void}
 */
MyQueue.prototype.push = function (x) {
  this.stack1.push(x);
};
/**
 * Removes the element from in front of queue and returns that element.
 * @return {number}
 */
MyQueue.prototype.pop = function () {
  if (!this.stack2.length) {
    while (this.stack1.length) {
      this.stack2.push(this.stack1.pop());
    }
  }
  return this.stack2.pop();
};
/**
 * Get the front element.
 * @return {number}
 */
MyQueue.prototype.peek = function () {
  if (!this.stack2.length) {
    while (this.stack1.length) {
      this.stack2.push(this.stack1.pop());
    }
  }
  return this.stack2[this.stack2.length - 1];
};
/**
 * Returns whether the queue is empty.
 * @return {boolean}
 */
MyQueue.prototype.empty = function () {
  return !this.stack2.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()
 */
let queue = new MyQueue();
queue.push(1);
queue.push(2);
console.log(queue.peek());// 返回 1
console.log(queue.pop());// 返回 1
console.log(queue.empty());  // 返回 false