背景知识：
动态栈的模拟实现：http://blog.csdn.net/double_happiness/article/details/70170984
队列的模拟实现：http://blog.csdn.net/double_happiness/article/details/70176907
题目：
（1）用两个栈实现一个队列
（2）用两个队列实现一个栈
用两个栈实现一个队列
分析：
首先需要清楚的一点是栈的特性是先进后出，并且只允许在栈顶进行操作（即push和pop都在站顶进行），队列的特性则是先进先出，可以在在两端进行操作（push在队尾，pop则是在队顶进行），明白这两个特性之后问题就不难解决了；
因为栈是先进后出的，所以栈的插入操作就是在一端插入，对照到队列中就是队尾，因此push操作就是直接push，主要实现的是用栈来实现pop操作，要用栈来实现pop操作也很简单，我们在栈自身的结构下再添加一个辅助栈，辅助栈用来保存pop出来的数据，然后再将辅助栈中的元素进行pop就可以完成先入先出的特性，可能描述的不是很清楚，下面用图示来解释一下上述操作。
图示：
代码实现：
（说明：在此是针对面试题因此就不很详细的实现队列的所有内部接口，详细实现见上背景知识）
#include <iostream>
using namespace std;
#include <stack>
template<class T>
class Queue
{
public:
void Push(const T& data) //在队尾添加元素
{
input.push(data);
}
void Pop() //删除对头元素
{
while (!input.empty()) //先将输入栈中的数据导入到输出栈
{
output.push(input.top());
input.pop();
}
if (!output.empty()) //再将栈中的从栈顶依次pop出来刚好是先进去的
{
//input.push(output.top());
output.pop();
}
}
protected:
stack<int> input; //输入栈
stack<int> output; //输出栈
};
int main()
{
Queue<int> q;
q.Push(1);
q.Push(2);
q.Push(3);
q.Push(4);
q.Push(5);
q.Pop();
q.Pop();
q.Pop();
q.Pop();
q.Pop();
system("pause");
return 0;
}
思路和上面的实现方式基本上相同，需要的是完成栈先进后出的特性，这里就不作赘述，直接给出具体的代码实现。
代码实现：
#include<iostream>
using namespace std;
#include<queue>
#include<stack>
template<class T>
class Stack
{
public:
void Push(const T& data)
{
input.push(data);
}
void Pop()
{
while (input.size()>0)
{
output.push(input.front());
input.pop();
}
if (!output.empty())
{
output.pop();
}
}
protected:
queue<int> input;
queue<int> output;
};
int main()
{
Stack<int> s;
s.Push(1);
s.Push(2);
s.Push(3);
s.Push(4);
s.Push(5);
s.Pop();
s.Pop();
s.Pop();
s.Pop();
s.Pop();
system("pause");
return 0;
}