代码随想录二刷Day10

今日任务

理论基础
232.用栈实现队列
225.用队列实现栈

理论基础

1. 栈和队列是STL中的两个数据结构
2. 三个STL版本：
   HP STL：其他版本STL的基础，开源
   P.J.Plauger STL：Visual C++编译器采用，非开源
   SGI STL：Linux的C++编译器GCC采用，开源
3. 栈：后进先出，不提供走访/迭代器功能，不允许遍历；不被归类为容器，而被归类为容器适配器；底层是可插拔的（可以控制用哪种容器来实现栈的功能，vector/deque/list都可以）；SGI STL默认以deque为缺省情况下的底层结构
4. 队列：先进先出，不提供走访/迭代器功能，不允许遍历；不被归类为容器，而被归类为容器适配器；SGI STL默认以deque为缺省情况下的底部结构

232. 用栈实现队列

链接：https://leetcode.cn/problems/implement-queue-using-stacks/

class MyQueue {stack in;stack out;
public:MyQueue() {}void push(int x) {in.push(x);}int pop() {if(!out.empty()){int tmp = out.top();out.pop();return tmp;}else{while(!in.empty()){int tmp = in.top();in.pop();out.push(tmp);}int tmp = out.top();out.pop();return tmp;}}int peek() {// if(!out.empty()) return out.top();// else{//     while(!in.empty()){//         int tmp = in.top();//         in.pop();//         out.push(tmp);//     }//     return out.top();// }int tmp = this->pop();out.push(tmp);return tmp;}bool empty() {if(in.empty() && out.empty()) return true;else return false;}
};/*** 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();*/

225. 用队列实现栈

链接：https://leetcode.cn/problems/implement-stack-using-queues/

class MyStack {queue in;queue out;
public:MyStack() {}void push(int x) {in.push(x);}int pop() {int res;while(!in.empty()){res = in.front();out.push(res);in.pop();}int tmp;while(!out.empty()){if(out.front() == res){out.pop();}else{tmp = out.front();in.push(tmp);out.pop();}}return res;}int top() {return in.back();}bool empty() {return in.empty() && out.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();*/

只用一个队列

class MyStack {queue q;
public:MyStack() {}void push(int x) {q.push(x);}int pop() {int res;int size = q.size();while(size--){res = q.front();if(size != 0){q.pop();q.push(res);}else q.pop();}return res;}int top() {return q.back();}bool empty() {return q.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();*/