面试题：使用两个栈来实现一个队列，完成队列的Push和Pop操作

栈的特性：先进后出

队列的特性：先进先出

解析：使用两个栈来实现一个队列，其实就是组合两个栈，来实现队列，栈是先进后出，队列是先进先出，可使用以下操作使用栈来实现队列：

一、入队列：

把需要存放的元素插入到栈1中

代码：

void push(const T&data){
        stack1.push(data);
    }           

二、出队列：

把栈1中的元素依次插入到栈2中

ps：此时栈顶元素就是需要出队列的元素

代码：

void Pop()
    {
        //如果两个栈都是空栈，此时说明队列是空的
        if (stack1.empty() && stack2.empty())
            cout << "this queue is empty" << endl;
        //如果栈2中有元素，那出队列就出栈2中的
        if (!stack2.empty()){
            stack2.pop();
        }
        //此时表明栈2已是空栈，再要出队列的话，那就需要把栈1中的所有元
        //素入栈到栈2中，注意一定要是栈1中的所有元素都入栈到栈2中
        else{
            while (stack1.size() > 0){
                stack2.push(stack1.top());
                stack1.pop();
            }
            stack2.pop();
        }
    }           

有返回值的Pop函数（此返回值为队头元素）：

T&Pop()
    {
        T head;
        //如果两个栈都是空栈，此时说明队列是空的
        if (stack1.empty() && stack2.empty())
            cout << "this queue is empty" << endl;
        //如果栈2中有元素，那出队列就出栈2中的
        if (!stack2.empty()){
            head = stack2.top();
            stack2.pop();
        }
        //此时表明栈2已是空栈，再要出队列的话，那就需要把栈1中的所有元
        //素入栈到栈2中,注意一定要是栈1中的所有元素都入栈到栈2中
        else{
            while (stack1.size() > 0){
                stack2.push(stack1.top());
                stack1.pop();
            }
            head = stack2.top();
            stack2.pop();
        }
        return head;
    }           

三、获取队头元素

队列的队头位于栈2的栈顶

只要栈2不空，那就返回栈2的栈顶元素

如果栈2为空，那就把栈1中的所有元素全部压入栈2中，再取栈顶

T&Front()//获取队头元素，此时队头位于栈2的栈顶
    {
        assert(!stack1.empty() || !stack2.empty());
        if (stack2.empty()){
            while (!stack1.empty()){
                stack2.push(stack1.top());
                stack1.pop();
            }
        }
        return stack2.top();
    }           

源代码

#include<iostream>
#include<stack>
#include<assert.h>
using namespace std;
template<class T>
class Queue
{
public:
    //入队列
    void push(const T&data){
        stack1.push(data);
    }
    //出队列
    void Pop()
    {
        //如果两个栈都是空栈，此时说明队列是空的
        if (stack1.empty() && stack2.empty())
            cout << "this queue is empty" << endl;
        //如果栈2中有元素，那出队列就出栈2中的
        if (!stack2.empty()){
            stack2.pop();
        }
        //此时表明栈2已是空栈，再要出队列的话，那就需要把栈1中的所有元
        //素入栈到栈2中,注意一定要是栈1中的所有元素都入栈到栈2中
        else{
            while (stack1.size() > 0){
                stack2.push(stack1.top());
                stack1.pop();
            }
            stack2.pop();
        }
    }
    T&Front()//获取队头元素，此时队头位于栈2的栈顶
    {
        assert(!stack1.empty() || !stack2.empty());
        if (stack2.empty()){
            while (!stack1.empty()){
                stack2.push(stack1.top());
                stack1.pop();
            }
        }
        return stack2.top();
    }
private:
    stack<T> stack1;
    stack<T> stack2;
};
void TestQueue()
{
    Queue<int> q;
    q.push(1);
    q.push(2);
    q.push(3);
    q.push(4);
    q.push(5);
    cout << "队头为:>   "<<q.Front() << endl;
    q.Pop();
    q.Pop();
    q.Pop();
    cout << "队头为:>   " << q.Front() << endl;
    q.push(6);
    q.push(7);
    q.push(8);
    q.push(9);
    q.Pop();
    q.Pop();
    q.Pop();
    cout << "队头为:>   " << q.Front() << endl;
}
int main()
{
    TestQueue();
    system("pause");
    return 0;
}           

运行结果：

Pop函数中返回队头元素时的源代码

#include<iostream>
#include<stack>
#include<assert.h>
using namespace std;
template<class T>
class Queue
{
public:
    //入队列
    void push(const T&data){
        stack1.push(data);
    }
    //出队列
    T&Pop()
    {
        T head;
        //如果两个栈都是空栈，此时说明队列是空的
        if (stack1.empty() && stack2.empty())
            cout << "this queue is empty" << endl;
        //如果栈2中有元素，那出队列就出栈2中的
        if (!stack2.empty()){
            head = stack2.top();
            stack2.pop();
        }
        //此时表明栈2已是空栈，再要出队列的话，那就需要把栈1中的所有元
        //素入栈到栈2中,注意一定要是栈1中的所有元素都入栈到栈2中
        else{
            while (stack1.size() > 0){
                stack2.push(stack1.top());
                stack1.pop();
            }
            head = stack2.top();
            stack2.pop();
        }
        return head;
    }
    T&Front()//获取队头元素，此时队头位于栈2的栈顶
    {
        assert(!stack1.empty() || !stack2.empty());
        if (stack2.empty()){
            while (!stack1.empty()){
                stack2.push(stack1.top());
                stack1.pop();
            }
        }
        return stack2.top();
    }
private:
    stack<T> stack1;
    stack<T> stack2;
};
void TestQueue()
{
    Queue<int> q;
    q.push(1);
    q.push(2);
    q.push(3);
    q.push(4);
    q.push(5);
    cout <<"队头为:>  "<< q.Pop() << endl;
    cout << "队头为:>  " << q.Pop() << endl;
}
int main()
{
    TestQueue();
    system("pause");
    return 0;
}           

ps:是先返回队头，然后在Pop的，所以第一次输出队头为1，第二次输出队头为2