力扣225题：用队列实现栈 - 双队列解法详解
2天前
内容简介
本文详细解析了力扣225题"用队列实现栈"的双队列解法。通过两个队列的巧妙配合，实现了栈的后进先出(LIFO)特性。文章包含完整注释代码、算法思路讲解和复杂度分析，帮助读者掌握队列与栈相互转换的核心技巧。
算法思路
1.双队列结构：使用主队列s1和辅助队列s2
2.入栈操作：直接压入主队列s1
3.出栈操作：将主队列s1的前n-1个元素转移到辅助队列s2，弹出最后一个元素
4.栈顶元素：与出栈操作类似，但保留最后一个元素并重新压回队列
5.判空条件：主队列s1为空时栈为空
代码实现（带详细注释）
class MyStack {
public:
queue<int> s1; // 主队列，存储栈元素
queue<int> s2; // 辅助队列，用于操作时的临时存储
MyStack() {
// 构造函数，无需特殊初始化
}
// 入栈操作：直接压入主队列
void push(int x) {
s1.push(x);
}
// 出栈操作：移除并返回栈顶元素
int pop() {
// 将主队列前n-1个元素转移到辅助队列
while (s1.size() > 1) {
s2.push(s1.front()); // 将s1队首元素压入s2
s1.pop(); // 弹出s1队首元素
}
int res = s1.front(); // 获取最后一个元素(栈顶)
s1.pop(); // 弹出栈顶元素
// 将辅助队列元素转移回主队列
while (!s2.empty()) {
s1.push(s2.front());
s2.pop();
}
return res; // 返回栈顶元素
}
// 获取栈顶元素但不移除
int top() {
// 将主队列前n-1个元素转移到辅助队列
while (s1.size() > 1) {
s2.push(s1.front());
s1.pop();
}
int res = s1.front(); // 获取最后一个元素(栈顶)
s1.pop(); // 弹出栈顶元素
s2.push(res); // 将栈顶元素重新压入辅助队列
// 将辅助队列元素转移回主队列
while (!s2.empty()) {
s1.push(s2.front());
s2.pop();
}
return res; // 返回栈顶元素
}
// 判断栈是否为空
bool empty() {
return s1.empty(); // 主队列为空时栈为空
}
};复杂度分析
push操作：O(1)，直接压入主队列
pop/top操作：O(n)，需要转移n-1个元素
空间复杂度：O(n)，需要两个队列存储所有元素
优化方向
单队列实现：可以仅使用一个队列实现，通过循环队列的方式
减少转移次数：优化元素转移逻辑
异常处理：添加对空栈pop/top操作的处理
总结
双队列实现栈是数据结构转换的经典问题，通过主队列和辅助队列的配合，巧妙地用先进先出(FIFO)的队列实现了后进先出(LIFO)的栈特性。理解这种解法有助于掌握队列和栈的核心概念及其相互转换技巧。
原创内容 转载请注明出处
