Virtual Judge-4099:队列和栈
题目描述:
队列和栈是两种重要的数据结构,它们具有push k和pop操作。push k是将数字k加入到队列或栈中,pop则是从队列和栈取一个数出来。队列和栈的区别在于取数的位置是不同的。
队列是先进先出的:把队列看成横向的一个通道,则push k是将k放到队列的最右边,而pop则是从队列的最左边取出一个数。
栈是后进先出的:把栈也看成横向的一个通道,则push k是将k放到栈的最右边,而pop也是从栈的最右边取出一个数。
假设队列和栈当前从左至右都含有1和2两个数,则执行push 5和pop操作示例图如下:
push 5 pop
队列 1 2 -------> 1 2 5 ------> 2 5
push 5 pop
栈 1 2 -------> 1 2 5 ------> 1 2
现在,假设队列和栈都是空的。给定一系列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。输出应该共2*m行。
Sample Input
2
4
push 1
push 3
pop
push 5
1
pop
Sample Output
3 5
1 5
error
error
思路:
对数列和栈基础知识的运用,知道两种数据结构的相同和不同。
AC代码:
#include<stdio.h>
#include<stack>
#include<queue>
#include<string.h>
using namespace std;
char ch[10]; //定义一个字符数组存push和pop
int q[1000]; //存栈内元素
int p[1000]; //存队列内元素
int main()
{
int m,n;
int x,flag; //x为入栈数字,flag为标记,用来标记是否为空栈或空队列
scanf("%d",&m);
getchar();
while(m--)
{
flag=0; //标记初始化
int c=0,d=0; //c和d为计数器,分别为队列和栈的计数
queue<int> a; //定义一个队列
stack<int> b; //定义一个栈
scanf("%d",&n);
getchar();
while(n--)
{
scanf("%s",ch);
if(ch[1]=='u') //看是push还是pop,如果第二个字符为‘u‘就入栈
{
scanf("%d",&x);
a.push(x); //入队列
b.push(x); //入栈
}
if(ch[1]=='o')
{
if(a.empty()||b.empty()) //判断是否为空栈(空队列)如果为空栈还pop就输出error
{
flag=1;
}
else //否则就pop
{
a.pop();
b.pop();
}
}
}
if(flag!=1) //如果不是空栈或空队列
{
while(!a.empty()) //非空就那一个数组存起来
{
p[d]=a.front();
a.pop();
d++;
}
for(int i=0;i<d;i++) //输出队列元素
{
if(i!=d-1)
{
printf("%d ",p[i]);
}
else
{
printf("%d\n",p[i]);
}
}
while(!b.empty()) //非空就那一个数组存起来
{
q[c]=b.top();
b.pop();
c++;
}
for(int i=c-1;i>=0;i--) //输出队列元素,因为栈是先进后出,所以倒序输出
{
if(i!=0)
{
printf("%d ",q[i]);
}
else
{
printf("%d\n",q[i]);
}
}
}
else
{
printf("error\n");
printf("error\n");
}
while(!a.empty()||!b.empty()) //清空队列和栈内元素
{
a.pop();
b.pop();
}
}
return 0;
}
(这是一道基础题,但是我在输出元素的时候卡住了,还是对知识掌握的不够好,感谢我身边的大佬对我的帮助)