2025-11-28 20:03 南昌大学 算法工程师 发布于江西
关注
用两个栈实现队列
先进后出第一个栈，然后就后进先出第二个栈，从而实现队列
用stack1作为输入栈接收新元素，stack2作为输出栈实现队头弹出，push操作直接将元素压入stack1；pop操作时，若stack2为空，就把stack1的元素逐个弹出并压入stack2，再弹出stack2的栈顶元素即可。
以下是代码解析：
class Solution{public:
//队尾插入：新元素直接入栈1
void push(int node) {
stack1.push(node);
}
//队头删除：栈2为空时转移栈1元素，再弹出栈2栈顶
int pop() {
if(stack2.empty()){
while(!stack1.empty()){
stack2.push(stack1.top());
stack1.pop();
}
}
int ans=stack2.top();
stack2.pop();
return ans;
}
private:
stack<int> stack1; //输入栈：存新插入元素
stack<int> stack2; //输出栈：存反转后元素，用于弹出队头};
该解法的空间复杂度为O(n)，时间复杂度O(1)
用stack1作为输入栈接收新元素，stack2作为输出栈实现队头弹出，push操作直接将元素压入stack1；pop操作时，若stack2为空，就把stack1的元素逐个弹出并压入stack2，再弹出stack2的栈顶元素即可。
以下是代码解析：
class Solution{public:
//队尾插入：新元素直接入栈1
void push(int node) {
stack1.push(node);
}
//队头删除：栈2为空时转移栈1元素，再弹出栈2栈顶
int pop() {
if(stack2.empty()){
while(!stack1.empty()){
stack2.push(stack1.top());
stack1.pop();
}
}
int ans=stack2.top();
stack2.pop();
return ans;
}
private:
stack<int> stack1; //输入栈：存新插入元素
stack<int> stack2; //输出栈：存反转后元素，用于弹出队头};
该解法的空间复杂度为O(n)，时间复杂度O(1)
全部评论
相关推荐
点赞 评论 收藏
分享
不管什么都不想跳动了：本人美团百度快手都待过，建议肯定是直接留快手多一点产出后转正or直接冲字节腾讯暑期吧。一是快手从福利到基建都吊打另外两家。美团现在这个业务比较惨，本来毛利就很低，亏损严重，今年很可能要优化人力降低成本，去了别说日常，就算暑期后面都很可能被优化。百度其实实习生权限挺高的，可以接触到一些含金量高的项目，但是现在的风评不如之前了，薪资也不高。二是转正概率和薪资是跟产出挂钩的，你都在手子已经积累产出了，去其他家日常实习产出都是从0开始，肯定不可能有你在手子转正可能性大啊，现在日常压根没必要去，而且我有两个师弟都是在快手日常转正的，不用太担心，安心留在手子一边多做一点产出然后一边冲字节腾讯暑期，字节腾讯今年实习岗位非常多的，不如好好把握这个，加油。
点赞 评论 收藏
分享
查看24道真题和解析