【答案解析】题目要求用两个栈来模拟队列，栈A与栈B模拟队列Q，A为插入栈，B为弹出栈，以实现队列Q。
假设A和B都为空，可以认为栈A提供入队列的功能，栈B提供出队列的功能。
入队列：入栈A。
出队列分两种情况考虑：
1)如果栈B不为空，则直接弹出栈B的数据。
2)如果栈B为空，则依次弹出栈A的数据，放入栈B中，再弹出栈B的数据。
#include＜iostream＞
#include＜stack＞
using namespace std;
template ＜typename T＞
class QueueByDoubleStack
{
public:
size_t size();
bool empty();
void push(T t);
void pop();
T top();
private:
stack＜T＞ s1;
stack＜T＞ s2;
};
template ＜typename T＞
size_t QueueByDoubleStack＜T＞::size()
{
retum s1.size()+s2.size();
}
template ＜typename T＞
bool QueueByDoubleStack＜T＞::empty()
{
return s1.empty() && s2.empty();
}
template ＜typename T＞
void QueueByDoubleStack＜T＞::push(T t)
{
s1.push(t);
}
template ＜typename T＞
void QueueByDoubleStack＜T＞::pop()
{
if (s2.empty())
{
while(!s1.empty())
{
s2.push(s1.top());
s1.pop();
}
}
s2.pop();
}
template ＜typename T＞
T QueueByDoubleStack＜T＞::top()
{
if(s2.empty())
{
while(!s1.empty())
{
s2.push(s1.top());
s1.pop();
}
}
return s2.top();
}
int main()
{
QueueByDoubleStack＜int＞ q;
for (int i=0;i＜10;++i)
{
q.push(i);
}
while(!q.empty())
{
cout＜＜q.top()＜＜ ";
q.pop();
}
cout＜＜endl;
return 0;
}
程序输出结果：
0 1 2 3 4 5 6 7 8 9
引申：如何使用两个队列实现栈?
可以采用两种方法实现，入栈：所有元素依次入队列q1。例如，将A、B、C、D四个元素入栈，从队列尾部到队列首部依次为D、C、B、A，出栈的时候判断栈元素个数是否为1，如果为1，则队列q1出列；如果不为1，则队列q1所有元素出队列，入队列q2，最后一个元素不入队列B，输出该元素，队列q2所有元素入队列q1。例如，将D、C、B、A出列，D输出来，C、B、A入队列q2，最后返回到队列q1中，实现了后进先出。