关于美术馆网站建设的方案,山东泰山新闻,服务器搭建网站用什么系统,怎么通过域名做网站题目1#xff1a;232 用栈实现队列
题目链接#xff1a;232 用栈实现队列
题意
用两个栈实现先入先出队列#xff08;一个入栈#xff0c;一个出栈#xff09;#xff0c;实现如下功能#xff1a;
1#xff09;push#xff1a;将元素x推到队列末尾
2#xff09;…题目1232 用栈实现队列
题目链接232 用栈实现队列
题意
用两个栈实现先入先出队列一个入栈一个出栈实现如下功能
1push将元素x推到队列末尾
2pop从队列的开头移除并返回元素
3peek返回队列开头的元素
4empty若队列为空返回true否则返回false 代码
class MyQueue {
public:stackint stackIn;//入栈stackint 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 逻辑
例1que2每次都要清空
每pop一次que2都要备份一次一定要是空的才能接续不断地进行操作如果不清空的话有可能已经弹出的元素会再次回到栈中 例2que2的全部元素都要移动到que1中
因为que2中保存的是当前pop操作que1中没有用到的元素为了保证后续操作要将que2中的全部元素移动到que1中。 代码
class MyStack {
public:queueint que1;queueint 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:queueint 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)
