[数据结构与算法]预备役的那些事--栈与队列

? ? ? ? 对于栈和队列，想必大家都很熟悉吧！

? ? ? ? 今天我来分享一道栈和队列结合在一起的题目。

? ? ? ? 题目如下：

????????

冰冰子最近新学习了队列和栈两种重要的数据结构，他知道它们具有push 和pop操作。

而冰冰子现在想同时研究栈和队列，于是，他开始了一个实验。

现在，假设队列和栈都是空的。给定一系列push k和pop操作之后，冰冰子想知道队列和栈中分别存的数字。若队列或栈已经空了，仍然接收到pop操作，则输出error。

Input

第一行为m，表示有m组测试输入，m<100。
每组第一行为n，表示下列有n行push k或pop操作。（n<150）
接下来n行，每行是push k或者pop，其中k是一个整数。
（输入保证同时在队列或栈中的数不会超过100个）

Output

对每组测试数据输出两行，第一行是队列情况，若在队列空时收到pop操作，则输出error。其余情况将队列按照对头至队尾顺序输出队列中所有元素，中间用空格隔开。第二行是栈的情况，若在栈空时收到pop操作，则输出error。其余情况下按照栈底至栈顶的顺序输出栈中所有元素。

Sample Input

2
4
push 1
push 3
pop
push 5
1
pop

Sample Output

3 5
1 5
error
error

? ? ? ? 说实话呀，刚接触栈和队列的我，看到这个题目时，有点懵逼：应该很麻烦吧。但其实这只是题目的外表难，它的精髓并不难。一起来看看吧。

#include<iostream>

using namespace std;

const int maxn = 101;

int Q[maxn]; //定义一个栈?
int top; ?//栈顶?

void pushq(int x) {
?? ?Q[top++]=x;
}

int popq() {
?? ?return Q[--top];
}

int E[maxn]; //定义一个队列
int front,back; ?//队列头 ?和 ? 尾巴

void pushe(int x) {
?? ?E[back++]=x;
}?

int pope() {
?? ?return E[front++];
}

int main()
{
? ? int a;
? ? int m;
? ? cin >> m;
? ? while (m --) ? ?//多组输入
? ? {
? ? ?? ?int y = 0; ? //这只是起到一个标记的作用
? ? ?? ?int w = 0;
? ? ?? ?Q[101] = {0};
? ? ?? ?E[101] = {0};
? ? ?? ?back = 0;
? ? ?? ?front = 0;
? ? ?? ?top = 0;
? ? ? ? string s;
? ? ? ? int n;
? ? ? ? cin >> n;
? ? ? ? for (int i = 0;i < n;i ++) ? ? ?
? ? ? ? {
? ? ? ? ? ? cin >> s;
? ? ? ? ? ? if(s == "push") ? ? ? ?//开始判断需要执行的命令
? ? ? ? ? ? {
? ? ? ? ? ? ? ? cin >> a; ? ? ? ? ? ?
? ? ? ? ? ? ? ? pushq(a); ? ? ? ? ?//栈和队列都要执行
? ? ? ? ? ? ? ? pushe(a);
? ? ? ? ? ? }
? ? ? ? ? ? else if (s == "pop")
? ? ? ? ? ? {
? ? ? ? ? ? ?? ?if(front >= back) ? //if队列为空
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? w = 1; ? ? ? ?//标记
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? else
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? pope();
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? if(top == 0) ? ? ?//if栈为空
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? w = 1; ? ? ? ? ?//标记
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? else
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? popq();
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ??
? ? ? ? ? ? }
? ? ? ? }
? ? ? ??
? ? ? ? if (w == 1) ? ? ? ?//为空时 ? 栈和队列 都要 输出 ?eroor
? ? ? ? {
?? ??? ??? ?cout << "error" << endl << "error";
?? ??? ?}
? ? ? ??
?? ??? ??? ?
?? ??? ??? ?if (w == 0){
? ? ? ? ? ? while(front < back) ? ? ?//队列非空则输出
? ? ? ? ? ? {
? ? ? ? ? ? ? ? cout << pope() << " ";
? ? ? ? ? ? ? ? y = 1;
? ? ? ? ? ? }
// ? ? ? ? ? ?cout << pope();
?? ??? ??? ?}
? ? ? ? ? ? if (y == 1) ? ? ?//这里需要注意格式
? ? ? ? ? ? {
? ? ? ? ? ? cout << endl;
? ? ? ? ? ? }

?? ??? ??? ?if (w == 0) ? ?//如果栈不为空
?? ??? ??? ?{
?? ??? ??? ?for (int i = 0;i < top - 1;i ++)
?? ??? ??? ?{
?? ??? ??? ??? ?cout << Q[i] << " "; ? ? //输出值
?? ??? ??? ?}
?? ??? ??? ?cout << Q[top - 1];
?? ??? ??? ?}
? ? ? ? ? ? cout << endl; ? ? ? ? //这里注意 ? 格式 ? ?要求 ? 换行
? ? }
? ? return 0;
}

? ? ? ? 看来之后是不是很简单，只是有点长而已。其实可以简单一点，这就需要你来助我一臂之力。