题解 | #用两个栈实现队列# 更新注释 时间复杂度是O()
用两个栈实现队列
https://www.nowcoder.com/practice/54275ddae22f475981afa2244dd448c6
class Solution
{
// 熟悉 栈和队列的概念和性质
// 常用的操作
public:
void push(int node) {
stack1.push(node); // 就直接进入第一个栈
}
int pop() {
if(!stack2.empty()) // 若第二个栈非空 就弹出 返回
{
int ans = stack2.top();
stack2.pop();
return ans;
}
else // 否则 先把栈1插入的 转移到栈2 这样保证了顺序反过来 变成队列的先入先出
{
while(!stack1.empty())
{
int tmp = stack1.top();
stack2.push(tmp);
stack1.pop();
}
int ans = stack2.top();
stack2.pop();
return ans;
// 对于删除操作，虽然看起来是 O(n)O(n) 的时间复杂度，但是仔细考虑下每个元素只会「至多被插入和弹出 stack2 一次」，因此均摊下来每个元素被删除的时间复杂度仍为 O(1)。
}
}
private:
stack<int> stack1;
stack<int> stack2;
};
查看23道真题和解析