likes
comments
collection
share

面试官：请你用两个栈模拟一个队列

作者站长头像
站长
· 阅读数 1

思路

既然是用栈模拟队列，我们首先得明确两个概念即栈和队列。学过数据结构的同学应该对这个概念不陌生，可以直接跳过概念部分。

队列的基本概念

队列的概念大家应该都不陌生，大家从小到达排过的队应该不少。如果用平时大家经常说的一句话来形容的队列，那就是先到先得。看看百度百科的定义：

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

从上述定义中我们可以看出，实现一个队列，除了线性表本身有的size()、empty()的API，还要实现push()，即从表尾插入一个元素; pop()，从表头删除一个元素，以及一个front()，取出表头的数据，和back()，取出表尾的元素。

我们来看一个具体的例子：

现有5个元素1,2,3,4,5依次入队，请问其依次出队的顺序是？

凭生活经验也知道是1,2,3,4,5，很容易看出队列的特点是先进先出

栈的基本概念

百度百科中，是这样解释栈的：

栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

从上述定义中可以看出，实现一个栈，除了线性表本身有的size()、empty()的API，还要实现push()，即从表尾插入一个元素; pop()，从表尾删除一个元素，以及一个top()，取出表尾的数据。通常，我们管这个表尾叫栈顶，另一端叫栈底部（可参考下图）。

下面我们来来看栈的特点：

现有5个元素1,2,3,4,5依次入栈，请问其依次出栈的顺序是？

面试官：请你用两个栈模拟一个队列

5,4,3,2,1

善于总结的读者不难看出，栈的特点是后入先出，这个特点对我们解题很关键。

分析

我们现有的条件是两个表，每个表都有push()、pop()、top()、size()、empty()这五个API供我们使用，然后我们要实现的数据结构是一个具有push()、pop()、front()、back()、size()、empty()六个API的线性表，其中最核心的区别就是pop()的实现，因为两者的pop()刚好是相反的。但是，我们有两个栈呀！一个栈是后进先出，数学中有一种思想是负负得正，那么两个栈是不是可以实现先进先出呢？我们来看张图(拿iPad画的，效果不太理想)

面试官：请你用两个栈模拟一个队列

我们还是以1,2,3,4,5为例，先将1,2,3,4,5入到inStack里，然后依次将元素出栈，入到outStack里，然后我们看出栈顺序，是不是就变成 了1,2,3,4,5呢？看到这里，相信聪明的你一定有了实现的思路了吧！下面我们来看看JS的实现。

实现

JS中没有替我们实现Stack和Queue，但是JS中的数组非常强大，可以看做是一个双向队列，可以从两头存取并能按照索引取值，所以这里我们用JS中的数组代替栈，只能用pop()和push()。

class Queue {
  constructor() {
    //inStack处理输入
    this.inStack = [];
    //outStack处理输出
    this.outStack = [];
  }

  /**
   * @description 模拟队列在队尾插入数据
   * @param {number} val
   */
  push(val) {
    this.inStack.push(val);
  }

  /**
   * @description 模拟队列从队头删除数据
   * @returns {number} 返回删除的值
   */
  pop() {
    //输出栈中的数据为空，则要从输入栈里倒一次
    if (!this.outStack.length) {
      while (this.inStack.length) {
        this.outStack.push(this.inStack.pop());
      }
    }
    return this.outStack.pop();
  }

  /**
   * @description 读取队头的数据
   */
  front() {
    //输出栈中的数据为空，则要从输入栈里倒一次
    if (!this.outStack.length) {
      while (this.inStack.length) {
        this.outStack.push(this.inStack.pop());
      }
    }
    //取出输出栈栈顶的值
    return this.outStack[this.outStack.length - 1];
  }

  /**
   * @description 取队尾元素
   * @returns {number} 返回队尾元素
   */
  back() {
    //如果输入栈不为空，则栈顶元素就是队尾元素
    if (this.inStack.length) {
      return this.inStack[this.inStack.length - 1];
      //否则，输出栈栈底元素就是队尾元素。
    } else {
      //PS:标准Stack中是没有取出栈底元素的方法的，这里只是为了实现完整的队列，真实的题目可以参考LeetCode 232
      return this.outStack[0];
    }
  }

  /**
   * @description 判断队列是否为空
   * @returns {boolean}
   */
  empty() {
    return !this.inStack.length && !this.outStack.length;
  }
}

// a simple test
const q = new Queue();
q.push(1);
q.push(2);
q.push(3);
q.push(4);
q.push(5);
console.log(q.front());
console.log(q.back());
q.pop();
console.log(q.front());

输出结果

$ node stack_mock_queue.js 
1
5
2

时/空间复杂度

一个好的算法，是要经得起时间复杂度和空间复杂度的考量的。

本题中，很容易得出空间复杂度是O(n)，因为你向队列里push n个元素，队列的长度就为n。

再来看时间复杂度，很明显push()操作的时间复杂度是O(1)，至于pop()，是本题的一个核心方法，也是本题的难点所在。我们借用极限的思想来分析其时间复杂度。

假设调用者连续进行1000次push操作，然后再连续进行1000次pop操作，不难分析，1000次的pop操作中，只有第一次的时间复杂度会达到O(n)，因为要将数据从输入栈倒进输出栈，后面每次都是O(1)，这样均摊下来，可以近似认为每次操作时间复杂度是O(1)。

再看另一种极端情况，假设调用者进行2000次操作，每push一次就pop一次，每次pop都会倒一次，但是注意这个倒一次的时间复杂度也很低，因为只有一个数据，那么其时间复杂度也是常量级，即为O(1)。

综上，在两种极端情况下，其均摊时间复杂度都为O(1)，其他情况只可能介于两者之间，所以一般情况下的均摊时间复杂度也为O(1)。这里，学过高等数学的同学可以类比一下夹逼定理应该就很好理解了。