[C++知识库]今日总结：栈

习题：

F - F

冰冰子最近新学习了队列和栈两种重要的数据结构，他知道它们具有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

思路:开始我以为是遇到一个pop就输出，但实际是要输完指点n个数才能出结果。

首先可以弄一个队列的数组Q 队尾top 队首front，在搞个栈的数组top1 栈顶top1 栈底 front1.

输入一个push，就将值分别给进队列数组 栈数组，输入pop，先判断是否为空，在进行操作。

注意：本题要输完指点n个数才能出结果，而不是数一个pop就出一个结果

代码实现：

#include<stdio.h>
#include<string.h>
int x;
int Q[100000];//队列 
int Q1[100000];//栈 
int top;//队列 
int top1;//栈 
int front;//队列 
int front1; //栈 

void push(int x)//输入 
{
	Q[top]=x;
	Q1[top1]=x;
	top++;
	top1++;
} 
char a[1000];
int main()
{
	int m;
	scanf("%d",&m);
	for(int i=0;i<m;i++)
	{
		front=0;
		top1=0;
		top=0;
		front1=0;//归零 
	 int flag=0;//队列 
     int flag1=0;//栈
		int n;
		scanf("%d",&n);
		for(int j=0;j<n;j++)
		{
		    scanf("%s",a);
		    if(strcmp(a,"push")==0)
		    {
		    	scanf("%d",&x);
		    	push(x);
			}
			if(strcmp(a,"pop")==0)
			{
				if(front==top)//判断 
				{
					flag=1;
				 }
				 if(front1==top1)//判断 
				 {
				 	flag1=1;
				  } 
				while(front<top)
				{
				  Q[front]=Q[front+1];
				   front++;	
				}
				front=0;
				top-=1;
				if(front1<top1)
				{
					top1--;
				}
			}
		}
		if(flag==1)
		printf("error\n");
		else
		{
		while(front<top)
		{
			printf("%d",Q[front]);
			front++;
			if(front!=top)
			printf(" ");
			else
			printf("\n");
		}
	}   
	    if(flag1==1)
	    printf("error\n");
	    else
	    {
		while(front1<top1)
		{   
			printf("%d",Q1[front1]);
		     front1++;
		     if(front1!=top1)
			printf(" ");
				else
			printf("\n");
		}
	}
	}
}

?C-C:

?您将获得一个由括号??（ ）??和??[ ]??组成的字符串。这种类型的字符串被认为是正确的：?

• ?如果是空字符串?
• ?如果??A??和??B??是正确的??，AB??是正确的，?
• ?如果??A??是正确的，（??A??） 和 [??A??] 是正确的。?

?编写一个程序，该程序采用此类型的字符串序列并检查其正确性。您的程序可以假定最大字符串长度为??128??。?

?输入?

?第一行包含测试用例??n 的数量??。接下来的??n??行中的每一行都包含括号??（ ）??和??[ ]??的字符串。?

?输出?

?对于每个测试用例，如果表达式??正确，则??在单独的行中打印"是"，否则打印"??否??"。?

Example 1

Input example #1?content_copy

3
([])
(([()])))
([()[]()])()

Output example #1?content_copy

Yes
No
Yes

Example 2

Input example #10?content_copy

22
((()

())))
([)]

((([[[]]])])
([])
(([()])))
([()[]()])()
[(])
(((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((())))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))
(])
[)]
[)))]
[[)]
([])
(([()])))
([()[]()])()
([)]
(
()(
[()

Output example #10?content_copy

No
Yes
No
No
Yes
No
Yes
No
Yes
No
Yes
No
No
No
No
Yes
No
Yes
No
No
No
No

思路：循环遍历，遇到'('或'['，将它们存进栈数组，遇到')'或']'，再判断是否和栈顶对应。

如(([()])) ，最里层'('与')'对应，然后我们把这个栈顶删去，下一个继续匹配。

代码：

#include<stdio.h>
#include<string.h>
char Q[10000];
int main()
{
	int n;
     scanf("%d",&n);
	getchar();
	for(int i=0;i<n;i++)
	{
		int top=0; 
		int t=0;//判断 
		char a[10000];
		gets(a);
		int lent=strlen(a);//字符串长度 
		if(lent==0)//不输入的情况 
		{
		printf("Yes\n");
		continue;
     }
	    for(int j=0;j<lent;j++)
	    {
	    	if(a[j]=='('||a[j]=='[')
	    	{
			Q[++top]=a[j];
}
	    	else
			if(a[j]==')'||a[j]==']')
	    	{
	       	   	if(a[j]==')'&&Q[top]=='('||a[j]==']'&&Q[top]=='[')
	       	   	{
	       	   		top--;	
		}
		  else
		  t=1;
		}
	}
        if(top==0&&t==0) //一一对应后top应该等于0
        printf("Yes\n");
        if(top!=0||t==1)
        printf("No\n");
	}
}

总结:做题容易忘记一些小细节，然后写代码有些复杂，没有考虑简化。?