算法练习08 用栈实现队列

用栈实现队列

题目

在组内面试反馈的邮件中看到了用栈实现队列这样一道题目，觉得自己如果面试遇到这个题目还是有点懵的，所以特地上网上找了一下，在Leetcode上找到了这道题目LeetCode 232 用栈实现队列。

题目是这样的：使用栈实现队列的下列操作：

• push(x) – 将一个元素放入队列的尾部。
• pop() – 从队列首部移除元素。
• peek() – 返回队列首部的元素。
• empty() – 返回队列是否为空。

注意：只能使用标准的栈操作，也就是只有push to top，peek/pop from top， size和is empty操作。

实例：

const queue = new MyQueue();

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

分析

之所以对这道题目有点懵，是因为自己对栈和队列的特点不太了解

1. 栈是先进后出的，队列是先进先出的
2. 标准的栈只有push/pop/size几个方法

因为JavaScript中的数组实际上比队列和栈是更加灵活的，要用栈来模拟队列，实际上可以用数组先模拟栈，然后在模拟队列。也可以直接使用数组来模拟队列，但是只使用数组的push和pop方法。

关键是栈和队列的操作顺序如何实现，我的思路是使用了两个栈（数组）来模拟，一个主栈一个辅栈，当移除的时候，栈移除的是栈底的元素，而队列要移除的是队首的元素，所以将主栈的元素都添加到辅栈中，然后再pop辅栈栈底的元素，就是队列要移除的队首的元素。实际上和我们玩过的汉诺塔的操作过程。

添加的时候可以直接添加，但是要注意辅栈中是否有元素，如果有的话需要先将辅栈的元素移动会主栈，在进行添加。

实现

function MyQueue() {
  // 主栈
  this.queue1 = [];
  // 辅栈
  this.queue2 = [];
}

MyQueue.prototype.push = function (x) {
  while (this.queue2.length !== 0) {
    this.queue1.push(this.queue2.pop())
  }
  this.queue1.push(x);
};

MyQueue.prototype.pop = function () {
  if (this.empty()) {
    return;
  }
  while (this.queue1.length !== 0) {
    this.queue2.push(this.queue1.pop())
  }
  return this.queue2.pop();
};

MyQueue.prototype.peek = function () {
  if (this.empty()) {
    return;
  }
  while (this.queue1.length !== 0) {
    this.queue2.push(this.queue1.pop())
  }
  const temp = this.queue2.pop();
  this.queue2.push(temp);

  return temp;
};

MyQueue.prototype.empty = function () {
  return this.queue1.length === 0 && this.queue2.length === 0
};

参考

• LeetCode 232 用栈实现队列@leetcode
• 《剑指offer》— JavaScript（5）用两个栈实现队列@简书