今日任务：
● 理论基础
● 232.用栈实现队列
● 225. 用队列实现栈
理论基础
队列是先进先出，栈是先进后出
常见问题：
C++中stack 是容器么？
我们使用的stack是属于哪个版本的STL？
我们使用的STL中stack是如何实现的？
stack 提供迭代器来遍历stack空间么？
下面通俗的介绍一下这些知识点：
栈和队列是STL（C++标准库）里面的两个数据结构。在C++中，
stack不是容器，它更像是一个容器适配器（container adapter），意味着它提供了容器的某些功能，但它本身不是。stack是建立在其他容器之上的，通常是deque或list。例如：以vector为栈的底层实现：std::stack<int, std::vector<int> > third; // 使用vector为底层容器的栈
或者list为底层实现，初始化的queue：std::queue<int, std::list<int>> third; // 定义以list为底层容器的队列
我们通常说的
stack是属于标准模板库（STL）的一部分，这个库从C++98标准就开始有了，并在后续的C++11、C++14、C++17等版本中得到了更新和改进。在STL中，
stack的实现是通过将一个现有的容器类（默认是deque）包装起来实现的。它只允许你在顶部添加（push）或移除（pop）元素，不可以访问stack中的其他元素。至于迭代器，
stack不提供迭代器来遍历，因为它是设计来只有在顶部访问的，不支持遍历整个stack。如果你需要遍历，可能需要考虑使用其他容器类型。
232.用栈实现队列
本道题主要考察，栈和队列的基本操作。
本题用两个栈来实现队列。
题目
使用栈实现队列的下列操作：
push(x) -- 将一个元素放入队列的尾部。 pop() -- 从队列首部移除元素。 peek() -- 返回队列首部的元素。 empty() -- 返回队列是否为空。
示例:
MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek(); // 返回 1
queue.pop(); // 返回 1
queue.empty(); // 返回 false说明:
你只能使用标准的栈操作 -- 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）。
思路
队列是先入先出。但是栈是先入后出。
所以我们需要用两个栈来操作：先把输入放到栈1中，然后栈1的数据输入到栈2中（为了更改顺序），然后再从栈2输出数据，这样就和queue的出队列的顺序一样了。
细节：一旦queue有出队列的操作，就把stack1里的全部元素放到stack2中才行
基础操作：
stack.push()表示把数据放入Stack
stack.top()表示取出stack最上层的元素
int pop()：这是pop函数的开始，它的作用是从队列中移除并返回最前面的元素。
ps：
Stack1 表示入栈 : StackIn
Stack2 表示出栈: StackOut
伪代码
stackIn, stackOut
void push(int x){
stackIn.push(x); // 入栈
}
// 出栈
int pop(){
if (!stackOut.empty()){
while(!stackIn.empty()){
stackOut.push(stackIn.top); // 把stackIn里的数据全部放到stackOut里
stackIn.pop(); // 再把stackIn的元素pop出去，为了清空它
}
}
result = stackOut.top(); // top是获取元素
stackOut.pop(); // 这个为了把出栈的元素弹出，清空
return result;
}
// 为了得到第一个元素（peak和pop实际上代码是一样的）
int peek() {
int res = this->pop(); // 因为我们实际上是在类里面，所以可以直接用this来调用上面写的pop函数 - 复用了pop
stOut.push(res); // 但是因为pop函数弹出了元素res，所以再添加回去 （因为我们的peak只是为了查询一下第一个元素）
return res;
}
225. 用队列实现栈
本题可以用两个队列来模拟栈，也可以用一个队列来模拟。
题目
使用队列实现栈的下列操作：
push(x) -- 元素 x 入栈
pop() -- 移除栈顶元素
top() -- 获取栈顶元素
empty() -- 返回栈是否为空
注意:
你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。
思路
其实这道题目就是用一个队列就够了。
一个队列在模拟栈弹出元素的时候：只要将队列头部的元素（除了最后一个元素外）取出来，再重新添加到队列尾部，此时再去弹出元素就是栈的顺序了。
假如队列中有size个元素，那就把size-1个元素弹出，然后重新加入到队列末端。然后把剩余的那一个弹出来即可。
也就是每次stack弹出时，相当于要把queue的最后一个元素弹出！
比如：
stack： 3 2 1| 现在要弹出3
queue： 出 1 2 3 入
所以，为了要弹出3，所以先把12弹出，再加到queue后面，然后就可以弹出3了
伪代码
一个队列如何模拟栈：
Queue:
Front() ...... Back()
void push(int x){
que.push(x); // push是最好写的，就只需要把x放到queue中就行了
}
int pop(){
size = que.size();
size--;
while(size--){
que.push(que.front()); // 把size-1个元素都取出来，然后pop弹出来
que.pop();
}
result = que.front();
que.pop();
return result;
}
int top(){ // 获取栈里的第一个元素，不需要弹出
return que.back();
}
