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

题目描述

用两个栈实现队列，支持队列的基本操作。

输入描述

第一行输入一个整数N，表示对队列进行的操作总数。

下面N行每行输入一个字符串S，表示操作的种类。

如果S为"add"，则后面还有一个整数X表示向队列尾部加入整数X。

如果S为"poll"，则表示弹出队列头部操作。

如果S为"peek"，则表示询问当前队列中头部元素是多少。

输出描述

对于每一个为"peek"的操作，输出一行表示当前队列中头部元素是多少。

示例

输入：
6
add 1
add 2
add 3
peek
poll
peek
输出：
1
2

备注

1<=N<=1000000

-1000000<=X<=1000000

数据保证没有不合法的操作

解题思路

使用两个栈实现队列的基本操作，难点在于队列是先进先出，而栈是先进后出。
此时，一个栈模拟入队，一个栈模拟出队。
每次入队的时候，直接添加到入队栈，
每次出队的时候，需要先判断当前出队栈是否为空，为空则需要把入队栈中的元素全部放入出队栈中。然后再进行出栈操作。
每次获取队头元素的时候，也需要判断当前出队栈是否为空，操作与出队类似，只不过不弹出元素，获取元素即可。

实现代码

/*
 * @Description: 
 * @Author: 
 * @Date: 2020-10-20 18:05:08
 * @LastEditTime: 2020-10-20 18:57:20
 * @LastEditors: Please set LastEditors
 */
#include <iostream>
#include <vector>
#include <string>
#include <stack>
using namespace std;

int main()
{

    int N;
    cin >> N;
    getchar();
    vector<string> arr(N);
    for (int i = 0; i < N; i++)
    {
        getline(cin, arr[i]);
    }
    stack<int> in_stack; //入队栈
    stack<int> out_stack; //出队栈
    for (int i = 0; i < arr.size(); i++)
    {
        string str = arr[i].substr(0, 3);
        if (str == "add")
        {
            int num = atoi(arr[i].substr(3).c_str());
            //入队
            in_stack.push(num);
        }
        else if (str == "pol")
        {
            //出队
            if (out_stack.empty())
            { //出队栈为空
                while (!in_stack.empty())
                {
                    int top = in_stack.top();
                    in_stack.pop();
                    out_stack.push(top);
                }
            }
            out_stack.pop();
        }
        else if (str == "pee")
        {
            //获取队头元素
            if(out_stack.empty()){
                //出队栈为空
                while (!in_stack.empty())
                {
                    int top = in_stack.top();
                    in_stack.pop();
                    out_stack.push(top);
                }
            }
            cout << out_stack.top() << endl;
        }
    }
    //system("pause");
    return 0;
}