题目描述
用两个栈实现队列，支持队列的基本操作。
输入描述
第一行输入一个整数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
数据保证没有不合法的操作
解题思路
使用两个栈实现队列的基本操作，难点在于队列是先进先出，而栈是先进后出。 此时，一个栈模拟入队，一个栈模拟出队。 每次入队的时候，直接添加到入队栈， 每次出队的时候，需要先判断当前出队栈是否为空，为空则需要把入队栈中的元素全部放入出队栈中。然后再进行出栈操作。 每次获取队头元素的时候，也需要判断当前出队栈是否为空，操作与出队类似，只不过不弹出元素，获取元素即可。
实现代码
#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
;
}
}
return 0;
}
