day10 用栈实现队列 用队列实现栈

题目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 = que2while(!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)