使用两个栈实现队列
使用两个栈实现队列
栈的队列的特点
栈和队列都是用来保存数据的，无论底层是使用数组还是链表来实现，其基本原理是不变的，那就是栈的特点的先进后出，队列的特点是先进先出。
栈的常用方法
-
isEmpty()
- 判断栈是否为空
-
size()
- 返回栈中元素的个数
-
push()
- 向栈中插入数据
-
pop()
- 从栈中弹出数据并返回
-
peek()
- 返回栈顶的数据
使用栈实现队列
首先我们来考虑如何使用两个栈来实现队列。队列的特点是先进先出，如果向队列中保存”hollis”的顺序是h、o、l、l、i、s，那么取出元素的数序也应该是h、o、l、l、i、s。
而对于栈来说，如果你想要让一个元素能够第一个被弹出，就要保证他永远位于栈的顶部。也就是说，如果你希望出站的顺序是h、o、l、l、i、s，那么入站顺序需要时silloh。
我们现在已经有的数据结构是栈，如果按照h、o、l、l、i、s的顺序向一个栈中保存数据的话，这些元素在栈中的顺序应该是s、i、l、l、o、h。也就是他正常的弹出顺序应该是silloh，但是我们想要的弹出顺序是hollis。 那么如何解决这个问题呢，就需要另外一个栈来配合，两个栈互相倒换。具体如何操作呢？
有一种方案是这样的：两个栈严格区分开来使用，一个专门用来做插入（插入栈），一个专门用来做弹出（弹出栈）。这样在做插入的时候什么都不需要做，直接调用插入栈的push方法就可以了。但是在弹出的时候就要麻烦一点，先判断在弹出栈中是否包含数据，++如果包含，直接从顶部弹出，如果不包含，把插入栈中的元素挨个导入到弹出栈中。然后再从栈顶将第一个元素弹出。++
说起来好像挺绕的，没关系。接着往下看，我们先来定义一下这个队列：
class MyQueue {
stack<int> in;
stack<int> out;
}接下来，我们通过一张图来模拟下如何使用两个栈来实现队列的插入操作。
上图中可以看出来，插入还是比较简单的，只需要往插入栈中push就可以了，代码实现如下：
void push(int x) {
in.push(x);
}插入的时候简单了，那么弹出的时候可能就要经过一番操作了。再来一张图，看看如何使用两个栈来实现队列的弹出操作。 简单介绍下过程：队列中原有三个数据，插入顺序是HOL，进行以下三个操作：
1. 弹出H，
2. 插入L，
3. 弹出O。
从上面的图中可以看到，当我们尝试弹出H的时候，由于stack-out为空，需要把stack-in栈中的数据pop出来，并push进入stack-out，然后再从stack-out的栈顶就能直接弹出H了。 当我们尝试弹出O的时候，因为stack-out中包含数据，那么就直接从stack-out中往外弹数据就可以了。
代码实现如下：
int pop() {
if (!out.empty()) {
int temp = out.top();
out.pop();
return temp;
}
else {
if (in.empty()) {
return -1;
}
else {
while (!in.empty()) {
out.push(in.top());
in.pop();
}
int temp = out.top();
out.pop();
return temp;
}
}
}