本文深入探讨了如何利用两个栈实现队列，并详细分析了其操作的时间复杂度。我们将揭示`push`操作通常为o(1)，而`pop`和`peek`操作在最坏情况下可能达到o(n)的原因，并阐明其摊还时间复杂度为o(1)。此外，文章还将提供代码示例，并讨论实现严格o(1)操作的替代方案。
核心实现原理
使用两个栈实现队列是一种常见的技术面试题，其核心思想是利用栈的后进先出（LIFO）特性来模拟队列的先进先出（FIFO）行为。通常，我们会维护两个栈：一个用于入队操作（input栈），另一个用于出队操作（output栈）。
- 入队 (push) 操作：新元素直接推入input栈。
-
出队 (pop) 或查看队首 (peek) 操作：
- 如果output栈不为空，则直接从output栈弹出或查看队首元素。
- 如果output栈为空，则需要将input栈中的所有元素依次弹出并推入output栈，这样input栈的底部元素（即最早进入队列的元素）就会成为output栈的顶部元素。完成转移后，再从output栈弹出或查看队首元素。
代码示例
以下是使用Java语言实现双栈队列的经典代码结构：
import java.util.Stack;
class MyQueue {
Stack<Integer> input;
Stack<Integer> output;
public MyQueue() {
input = new Stack<>();
output = new Stack<>();
}
/**
* 将元素 x 推到队列的末尾。
* @param x 要入队的元素
*/
public void push(int x) {
input.push(x);
}
/**
* 从队列的开头移除并返回元素。
* @return 队首元素
*/
public int pop() {
// pop操作依赖于peek操作来获取值
int val = peek();
output.pop();
return val;
}
/**
* 返回队列开头的元素。
* @return 队首元素
*/
public int peek() {
if (output.isEmpty()) {
// 如果output栈为空，则将input栈中的所有元素转移到output栈
while (!input.isEmpty()) {
output.push(input.pop());
}
}
// 此时output栈的顶部元素即为队列的队首元素
return output.peek();
}
/**
* 检查队列是否为空。
* @return 如果队列为空，则返回 true；否则返回 false。
*/
public boolean empty() {
return input.isEmpty() && output.isEmpty();
}
}复杂度分析
1. push 操作
- 时间复杂度：O(1)push操作仅涉及将一个元素推入input栈，这是一个常数时间操作。
2. pop 和 peek 操作
-
最坏情况时间复杂度：O(N) 当output栈为空时，pop或peek操作需要将input栈中的所有N个元素（假设当前队列中有N个元素）逐一弹出并推入output栈。这个转移过程需要执行N次弹出和N次推入操作，因此最坏情况下的时间复杂度是O(N)。
例如，当队列先执行了N次push操作，然后紧接着执行第一次pop或peek操作时，就会触发这个O(N)的元素转移。
-
摊还时间复杂度：O(1) 尽管单次pop或peek操作在最坏情况下可能是O(N)，但从一系列操作的整体来看，其摊还时间复杂度却是O(1)。 考虑M次操作的序列：
- 每个元素最多被推入input栈一次。
- 每个元素最多从input栈弹出一次，然后推入output栈一次。
- 每个元素最多从output栈弹出一次。 这意味着每个元素在整个生命周期中，最多执行常数次（入栈、出栈、入栈、出栈）操作。因此，M次操作的总成本是O(M)，平均到每次操作，其摊还时间复杂度为O(1)。
总结： 对于单个pop或peek操作，如果output栈为空，其复杂度是O(N)。但对于一系列操作，push、pop和peek的平均（摊还）时间复杂度都是O(1)。
性能考量与优化
虽然双栈实现队列在摊还意义上是高效的，但在某些对实时性能要求极高的场景中，最坏情况下的O(N)仍然可能成为瓶颈。如果需要严格的O(1)最坏情况时间复杂度来执行所有队列操作，可以考虑使用其他数据结构：
- 双向链表 (Doubly-Linked List)：使用双向链表实现队列，addFirst（入队）和removeLast（出队）操作都可以在O(1)时间内完成。这是实现严格O(1)队列操作的常见方式。
- 循环数组 (Circular Array)：通过维护队头和队尾指针，循环数组也能在O(1)时间内完成入队和出队操作，但需要预先分配空间或在容量不足时进行扩容。
总结
使用两个栈实现队列是一种巧妙且常用的方法。其push操作的复杂度为O(1)，而pop和peek操作在最坏情况下为O(N)，但在摊还意义上，所有操作的平均时间复杂度均为O(1)。对于需要严格O(1)最坏情况性能的场景，双向链表或循环数组是更优的选择。理解这些复杂度特性对于编写高效且符合需求的程序至关重要。
