昨天 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)
全部评论
相关推荐
查看27道真题和解析 点赞 评论 收藏
分享