day10 用栈实现队列 用队列实现栈
2024-01-07 22:27:24
题目1:232 用栈实现队列
题目链接:232 用栈实现队列
题意
用两个栈实现先入先出队列(一个入栈,一个出栈),实现如下功能:
1)push:将元素x推到队列末尾
2)pop:从队列的开头移除并返回元素
3)peek:返回队列开头的元素
4)empty:若队列为空,返回true,否则,返回false
代码
class MyQueue {
public:
stack<int> stackIn;//入栈
stack<int> stackOut;//出栈
MyQueue(){}
void push(int x){
stackIn.push(x);
}
int pop(){
//stackOut出栈为空时,放入元素
if(stackOut.empty()){
while(!stackIn.empty()){
stackOut.push(stackIn.top());
stackIn.pop();
}
}
//出栈不为空时,直接弹出元素
int result = stackOut.top();
stackOut.pop();
return result;
}
int peek(){
int result = this->pop();//复用上面的pop()函数,
stackOut.push(result);//但是还需要将元素放回出栈中
return result;
}
bool empty(){
return (stackIn.empty() && stackOut.empty());
}
};
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue* obj = new MyQueue();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->peek();
* bool param_4 = obj->empty();
*/
- 时间复杂度: push和empty为O(1), pop和peek为O(n)
- 空间复杂度: O(n)
题目2: 225 用队列实现栈
题目链接:225 用队列实现栈
题意
使用两个队列实现栈,实现如下功能
push:将元素x压入栈顶
pop:移除并返回栈顶的元素
top:返回栈顶的元素
empty:栈为空,返回true,否则,返回false
两个队列
其中一个队列(que2)用来备份,把que1要弹出的元素以外的元素都备份到que2,然后弹出que1中的那个元素,再将que2中的元素放到que1中,同时清空que2
逻辑
例1:que2每次都要清空
每pop一次,que2都要备份一次,一定要是空的,才能接续不断地进行操作,如果不清空的话,有可能已经弹出的元素会再次回到栈中
例2:que2的全部元素都要移动到que1中
因为que2中保存的是当前pop操作que1中没有用到的元素,为了保证后续操作,要将que2中的全部元素移动到que1中。
代码
class MyStack {
public:
queue<int> que1;
queue<int> que2;
MyStack(){}
void push(int x){
que1.push(x);
}
int pop(){
int size = que1.size();
size--;
while(size--){
que2.push(que1.front());//que2备份que1弹出的元素
que1.pop();
}
int result = que1.front();
que1.pop();
//que1 = que2
while(!que2.empty()){
que1.push(que2.front());
que2.pop();
}
return result;
}
int top(){
return que1.back();
}
bool empty(){
return que1.empty();
}
};
/**
* Your MyStack object will be instantiated and called as such:
* MyStack* obj = new MyStack();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->top();
* bool param_4 = obj->empty();
*/
- 时间复杂度: pop为O(n),其他为O(1)
- 空间复杂度: O(n)
一个队列(★)
模拟出栈时,将队列头部(出)的size-1个元素依次重新添加到队尾(入),剩下的那个没有移动的元素就是所求
代码
class MyStack {
public:
queue<int> que;
MyStack(){}
void push(int x){
que.push(x);
}
int pop(){
int size = que.size();
size--;
while(size--){
que.push(que.front());
que.pop();
}
int result = que.front();
que.pop();
return result;
}
int top(){
return que.back();
}
bool empty(){
return que.empty();
}
};
/**
* Your MyStack object will be instantiated and called as such:
* MyStack* obj = new MyStack();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->top();
* bool param_4 = obj->empty();
*/
- 时间复杂度: pop为O(n),其他为O(1)
- 空间复杂度: O(n)
文章来源:https://blog.csdn.net/qq_43773652/article/details/135443247
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!