程序员代码面试指南 1.2：由两个栈组成的队列

解法一

两个栈倒来倒去的常规解法。

#include <iostream>
#include <string>
#include <stack>

using namespace std;

stack<int> stk1, stk2;

//将一个栈倒入另一个栈中
void stkExchange(stack<int>& stk1, stack<int>& stk2)
{
    while (!stk1.empty())
    {
        stk2.push(stk1.top());
        stk1.pop();
    }
}

void add(int num)
{
    stk1.push(num);
}

void poll()
{
    stkExchange(stk1, stk2);
    stk2.pop();
    stkExchange(stk2, stk1);
}

int peek()
{
    stkExchange(stk1, stk2);
    int res = stk2.top();
    stkExchange(stk2, stk1);

    return res;
}

int main()
{
    int n;
    cin >> n;

    while (n -- )
    {
        string s;
        cin >> s;

        if (s == "add")
        {
            int num;
            cin >> num;

            add(num);
        }
        else if (s == "poll")
        {
            poll();
        }
        else
        {
            cout << peek() << endl;
        }
    }

    return 0;
}

解法二

左程云给出了更精妙的解法，不再需要两个栈倒过来倒过去，建两个栈：

• stkPush：专门用来push元素；
• stkPop：专门用来pop元素。

相当于stkPop用来按顺序存放队首元素，stkPush用来做缓冲，可以模拟一下连续push 1 2 3后再pop的过程。

#include <iostream>
#include <string>
#include <stack>

using namespace std;

stack<int> stkPush, stkPop;

//将push栈倒入pop栈中，条件是pop栈必须为空
void pushToPop()
{
    if (stkPop.empty())
    {
        while (!stkPush.empty())
        {
            stkPop.push(stkPush.top());
            stkPush.pop();
        }
    }
}

void add(int num)
{
    stkPush.push(num);
    pushToPop();
}

void poll()             //poll与peek的操作比上一种解法简洁太多
{
    stkPop.pop();
    pushToPop();
}

int peek()
{
    return stkPop.top();
}

int main()
{
    int n;
    cin >> n;

    while (n -- )
    {
        string s;
        cin >> s;

        if (s == "add")
        {
            int num;
            cin >> num;

            add(num);
        }
        else if (s == "poll")
        {
            poll();
        }
        else
        {
            cout << peek() << endl;
        }
    }

    return 0;
}