LeetCode题解：225. 用队列实现栈，两个队列，压入 -O(1)， 弹出 -O(n)，JavaScript，详细注释

[chencl1986]

原题链接：https://leetcode-cn.com/problems/implement-stack-using-queues/

解题思路：

参考了官方题解的方法一 （两个队列，压入 -O(1)O(1)， 弹出 -O(n)O(n)）。

入栈时直接将元素存入队列q1，出栈时将q1的非队尾元素存入队列q2，q1中剩下的元素即为栈顶。

1. 使用两个对列，q1用来存储栈，q2保持为空。
2. 每次入栈都将元素存入q1，此时栈顶元素在q1队尾，无法被查看，需要用一个变量缓存栈顶的值，供top方法获取。
3. 出栈时将q1的非队尾元素存入队列q2，q1中剩下的元素即为栈顶，将其出队即为出栈操作。

/**
 * Initialize your data structure here.
 */
var MyStack = function () {
  this.q1 = []; // 保存栈
  this.q2 = []; // 用于pop时缓存队列中除栈顶外的其他元素
  this.tail = null; // 保存栈顶元素
};

/**
 * Push element x onto stack.
 * @param {number} x
 * @return {void}
 */
MyStack.prototype.push = function (x) {
  this.q1.push(x); // 入栈时将元素直接存入队列
  this.tail = x; // 由于存入队列的元素无法被作为栈顶查看，因此需要用变量存储此时的栈顶元素
};

/**
 * Removes the element on top of the stack and returns that element.
 * @return {number}
 */
MyStack.prototype.pop = function() {
  // 如果队列长度<=1，则出栈之后栈顶为空
  if (this.q1.length <= 1) {
    this.tail = null;
  }

  // 将队列元素除队尾外都移动到q2，q1中剩下的1个元素即为栈顶元素
  while (this.q1.length > 1) {
    this.tail = this.q1.shift();
    this.q2.push(this.tail);
  }

  // 队列中只剩1个元素，即为栈顶
  const top = this.q1.shift();

  // 将q1和q2对调，保证每次操作的队列都为q1。
  const temp = this.q1;
  this.q1 = this.q2;
  this.q2 = temp;

  // 返回出栈的元素
  return top;
};

/**
 * Get the top element.
 * @return {number}
 */
MyStack.prototype.top = function () {
  return this.tail;
};

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