栈队列，队列栈

这一节我们来看两个经常被拿来作为例题或者是面试题的问题。

例 1 ：「力扣」第 232 题：用栈实现队列

这道题要求我们用已经实现的栈实现队列。

题意分析：用栈来实现队列，或者用队列实现栈，肯定不是高效的做法。因此，这道题只是让我们实现功能。通过这种「逆来顺受」的方式，来加深对栈和队列的操作理解。

思路分析：思考这个问题，建议采用画图的方式帮助思考，还记得我们在介绍栈的时候说过，栈通常我们把它画成竖直摆放的容器。这里只使用一个栈肯定不能实现队列的功能。因此，我们还需要一个辅助栈，这也是 空间换时间 的思想。

我们知道栈符合「后进先出」的规律，「后进先出」再「后进先出」就是「先进先出」了，这样的思路可以理解为负负得正。因此：入队的时候，始终把数据放入原始栈，出队的时候，始终从辅助栈出队。这其中还有一些细节需要思考。

算法设计流程：我们可以使用两个栈，一个栈（stackPush）用于元素进栈，一个栈（stackPop）用于元素出栈

• pop() 或者 peek() 的时候：
  • 如果 stackPop 里面有元素，直接从 stackPop 里弹出或者 peek 元素；
  • 如果 stackPop 里面没有元素，一次性 将 stackPush 里面的 所有 元素倒入 stackPop。

在这里要注意一个细节： 一定要保证 stackPop 为空的时候，才能把元素从 stackPush 里拿到 stackPop 中 。要想明白这个细节其实不难：如果 stackPop 里还有元素，从 stackPush 里出栈的那个元素就会成为 stackPop 的新栈顶元素，就打乱了出队的顺序。相信这一点，大家不难想明白。

var MyQueue = function () {
  this.pushStack = [];
  this.popStack = [];
};
MyQueue.prototype.push = function (x) {
  // 在任何时候都可以向 pushStack 推入元素
  this.pushStack.push(x);   
};
MyQueue.prototype.pop = function () {
  this.push2pop(); // 出栈准备一下
  return this.popStack.pop();
};
MyQueue.prototype.peek = function () {
  this.push2pop(); // 出栈准备
  // 这里不出栈，只peek
  return this.popStack[this.popStack.length - 1];
};
MyQueue.prototype.empty = function () {
  return this.popStack.length === 0 && this.pushStack.length === 0;
};
// 出栈准备 push to pop
MyQueue.prototype.push2pop = function () {
  // stackPop 为空的时候，才能把元素从 stackPush 里拿到 stackPop 中
  // 否则会打乱出队顺序
  if (!this.popStack.length) {
    while (this.pushStack.length) {
      this.popStack.push(this.pushStack.pop());
    }
  }
}

复杂度分析：

• 时间复杂度：O(1)。这里用到的是均摊复杂度分析，每一个元素进 push 栈一次，出 push 栈一次，进 pop 栈一次，出 pop 栈一次，平均操作是直接使用队列的 4 倍，但 4 是一个常数倍，因此，时间复杂度仍为 O(1)
• 空间复杂度：O(N)，这里 N 是输入数据的长度

例 2：「力扣」第 225 题：用队列实现栈

这一题让我们借助已经实现的队列实现栈。有了上一题的经验，我们不难想到，可以 使用两个队列实现栈。但事实上，放入辅助队列的那些元素可以直接放在当前的队列的尾部 ，这样我们就可以用一个队列实现栈的功能。

想通这个问题，依然需要在草稿纸上做一些模拟。

具体的操作是：在 peek() 和 pop() 时，依次将队首出队到队尾。

• push() 的时候，直接在队列的尾部添加元素即可；
• 只要涉及到 peek() 或者 pop() 操作，为了满足栈「后进先出」的性质。需要让当前队尾的元素成为队首，而队列只支持队首出队，队尾入队，不难想到需要依次把队尾之前的元素出队。放到哪里呢？直接放在队尾即可。

注意：peek() 的时候，得到队尾元素以后，还得再队首元素移动到队尾一次。

var MyStack = function () {
  this.queue = [];
};
MyStack.prototype.push = function (x) {
  let curr = 0;
  // 每次从队尾进来就重新排, 把当前元素放到第一个
  this.queue.push(x);
  while (curr < this.queue.length-1) {
    this.queue.push(this.queue.shift());
    curr++;
  };
};
MyStack.prototype.pop = function () {
  // push已经排好了，直接shift就行
  if (this.queue.length > 0) {
    return this.queue.shift();
  };
};
MyStack.prototype.top = function () {
  return this.queue[0];
};
MyStack.prototype.empty = function () {
  return this.queue.length === 0;
};

练习
完成「力扣」第 151 题：最小栈。
这就是这一节的内容。下一节我们看两个设计数据结构相关的问题，分别是队列和双端队列在数组中是如何实现的。