理论基础
栈
栈存储结构
又称为堆栈，是一种先入后出的数据结构。c++中的栈常用的接口如下：
- pop(); 将顶部元素弹出；
- push(x);将元素x放入栈的顶部；
- top();返回栈的顶部元素；
- size(); 返回栈的大小；
- empty();返回队列是否为空的状态；
队列
队列存储结构
是一种先入先出的数据结构。c++中队列的常用接口如下：
- front();返回队列头部元素；
- back();返回队列尾部元素；
- pop();将队列头部元素移除；
- size();返回队列大小；
- empty();返回队列是否为空的状态；
堆
https://juejin.cn/post/6854573217269415950
232.用栈实现队列
代码：
class MyQueue { private: stack<int> stIn; stack<int> stOut; public: MyQueue() { } void push(int x) { stIn.push(x); } int pop() { while(stOut.empty()){ while(!stIn.empty()){ stOut.push(stIn.top()); stIn.pop(); } } int val = stOut.top(); stOut.pop(); return val; } int peek() { int val = this->pop(); stOut.push(val); return val; } bool empty() { return stIn.empty() && stOut.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(x）, pop() , peek() , empty()。
栈只具备先入后出的属性，而队列是先入先出。所以可以利用两个栈来灵活的移动数据（一个用于存储刚push的数据，而一个用于存储需要被弹出的数据。）从而实现队列先入先出的属性。
难点：
pop()的实现是本题的难点所在，需要注意的点是只有当需要stOut为空时才需要将push进的元素全部放入stOut，否则实现的队列结构就不是先入先出了。
总结：
本题不涉及复杂的算法，主要用于认识与了解队列这种数据哦结构。
225. 用队列实现栈
代码：
class MyStack { private: queue<int> queue1; public: MyStack() { } void push(int x) { queue1.push(x); } int pop() { int size = queue1.size()-1; while(size--){ queue1.push(queue1.front()); queue1.pop(); } int val = queue1.front(); queue1.pop(); return val; } int top() { return queue1.back(); } bool empty() { return queue1.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(); */
思路：
题目栈需要实现的操作有：push(x）, pop() , top() , empty()。
同样地，两种数据结构的属性不一样。可以利用队列的先入先出属性循环地遍历插入和弹出数据，从而实现栈所具备的属性。
难点：
本题难点用样的在于pop()的实现。pop()需要弹出并且返回最后一个push的数据。可以循环插入队列头部元素，同时弹出头部元素，一直重复，直到尾部元素被移动到了队列头部。在将元素pop就可以了。
总结：
本题的目的在于了解什么是队列，具备哪些属性。不涉及复杂的算法。
