232.用栈实现队列

发表于 分类于 阅读次数：

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

  • void push(int x) 将元素 x 推到队列的末尾
  • int pop() 从队列的开头移除并返回元素
  • int peek() 返回队列开头的元素
  • boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

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

示例 1：

1
2
3
4
5
6
7
8
9
10
11
12
13
输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]

解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

解题思路

这是一道经典的数据结构设计题，考察对栈和队列的理解。

核心思想

  • 使用两个栈：input栈和output栈
  • push操作：直接压入input栈
  • pop/peek操作：如果output栈为空，将input栈的元素全部倒入output栈

方法一：双栈法（推荐）

时间复杂度 O(1) 均摊、空间复杂度 O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
 * Initialize your data structure here.
 */
var MyQueue = function() {
    this.input = [];
    this.output = [];
};

/**
 * Push element x to the back of queue. 
 * @param {number} x
 * @return {void}
 */
MyQueue.prototype.push = function(x) {
    this.input.push(x);
};

/**
 * Removes the element from in front of queue and returns that element.
 * @return {number}
 */
MyQueue.prototype.pop = function() {
    this.peek();
    return this.output.pop();
};

/**
 * Get the front element.
 * @return {number}
 */
MyQueue.prototype.peek = function() {
    if (this.output.length === 0) {
        while (this.input.length > 0) {
            this.output.push(this.input.pop());
        }
    }
    return this.output[this.output.length - 1];
};

/**
 * Returns whether the queue is empty.
 * @return {boolean}
 */
MyQueue.prototype.empty = function() {
    return this.input.length === 0 && this.output.length === 0;
};

方法二：优化版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
var MyQueue = function() {
    this.stack1 = []; // 用于push
    this.stack2 = []; // 用于pop/peek
};

MyQueue.prototype.push = function(x) {
    this.stack1.push(x);
};

MyQueue.prototype.pop = function() {
    this.peek();
    return this.stack2.pop();
};

MyQueue.prototype.peek = function() {
    if (this.stack2.length === 0) {
        while (this.stack1.length > 0) {
            this.stack2.push(this.stack1.pop());
        }
    }
    return this.stack2[this.stack2.length - 1];
};

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

方法三：使用数组模拟

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var MyQueue = function() {
    this.queue = [];
};

MyQueue.prototype.push = function(x) {
    this.queue.push(x);
};

MyQueue.prototype.pop = function() {
    return this.queue.shift();
};

MyQueue.prototype.peek = function() {
    return this.queue[0];
};

MyQueue.prototype.empty = function() {
    return this.queue.length === 0;
};

方法四：延迟倒栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
var MyQueue = function() {
    this.input = [];
    this.output = [];
};

MyQueue.prototype.push = function(x) {
    this.input.push(x);
};

MyQueue.prototype.pop = function() {
    if (this.output.length === 0) {
        this.transfer();
    }
    return this.output.pop();
};

MyQueue.prototype.peek = function() {
    if (this.output.length === 0) {
        this.transfer();
    }
    return this.output[this.output.length - 1];
};

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

MyQueue.prototype.transfer = function() {
    while (this.input.length > 0) {
        this.output.push(this.input.pop());
    }
};

解题要点

  1. 双栈法：

    • input栈：用于push操作
    • output栈：用于pop/peek操作
    • 当output栈为空时，将input栈的元素全部倒入output栈

  2. 时间复杂度：

    • push操作：O(1)
    • pop/peek操作：O(1) 均摊
    • 每个元素最多被压入和弹出两次

  3. 空间复杂度：

    • O(n)，其中n是队列中的元素个数

面试要点

  • 高频考点：这道题是面试中的高频设计题
  • 数据结构：考察对栈和队列的理解
  • 均摊复杂度：了解均摊时间复杂度的概念
  • 设计思维：考察系统设计能力

相关题目

扩展思考

  1. 为什么使用双栈法？

    • 栈是后进先出，队列是先进先出
    • 通过两个栈的组合实现队列的先进先出特性
    • 延迟倒栈策略提高效率

  2. 时间复杂度分析

    • push操作：O(1)
    • pop/peek操作：O(1) 均摊
    • 每个元素最多被压入和弹出两次

  3. 均摊复杂度

    • 虽然单次pop操作可能是O(n)
    • 但每个元素最多被操作两次
    • 因此均摊复杂度是O(1)

  4. 边界情况

    • 空队列：返回-1或抛出异常
    • 只有一个元素：正常操作
    • 大量元素：测试性能

  5. 实际应用

    • 浏览器前进后退
    • 函数调用栈
    • 表达式求值

  6. 变种问题

    • 用队列实现栈
    • 设计循环队列
    • 设计优先队列

最后更新: 2021-10-09