原题连接

     首先要了解有关栈的一些基本知识，即：

     什么是栈，栈有什么作用；

       1、什么是栈：

watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" alt="">

     仅同意在表的一端进行插入和删除运算。

( 先进后出的一种数据结构形式 )。

     这一端被称为栈顶( top )。相对地，把还有一端称为栈底( bottom )；

     向一个栈插入新元素又称作进栈( push )、入栈或压栈。它是把新元素放到栈顶元素的上面。使之成为新的栈顶元素；

     从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉( pop )。使其相邻的元素成为新的栈顶元素。

       简单地说，就是在不满足取出条件的时候，新元素压栈。

       一直到满足条件后，退栈。一直到一组数据的最后一个元素；

       2、栈的作用：

     用来在函数调用的时候存储断点。做递归时要用到栈；

题目 :  )

括号配对问题

描写叙述

如今。有一行括号序列，请你检查这行括号是否配对。

输入

第一行输入一个数N（0<N<=100）,表示有N组測试数据。后面的N行输入多组输入数据。每组输入数据都是一个字符串S(S的长度小于10000。且S不是空串）。測试数据组数少于5组。

数据保证S中仅仅含有"[","]","(",")"四种字符

输出

每组输入数据的输出占一行，假设该字符串中所含的括号是配对的。则输出Yes,假设不配对则输出No

例子输入

3

[(])

(])

([[]()])

例子输出

No

No

Yes

       分析：

      1. 进栈条件： 假设 s[ i ] 是 “（” 或者 " [ " 的时候；

      2. 出栈条件： 假设碰到配对的括号；

AC代码：

<span style="font-size:18px;">#include<stdio.h>

#include<stdlib.h>

#include<string.h>

char a[11000],b[11000];//b即stack。

int main()

{

	int n;

	scanf("%d",&n);

	getchar();//屏蔽回车；

	while(n--)

	{

		int len,top=1,i;

		gets(a);

		b[top++]=a[0];

		len=strlen(a);

		if((a[0]!='[')&&(a[0]!='(')||(len%2==1)) printf("No\n");//若第一个元素为")"或"]"输入个数为奇数,No。

		else

		{

			for(i=1;	i<len;	i++)

			{

				if(a[i]=='('||a[i]=='[') b[top++]=a[i];//满足进栈条件，进栈；

				else

				{

					if(a[i]==']'&&b[top-1]=='[') top--;//满足出栈条件。

					else if(a[i]==')'&&b[top-1]=='(') top--;

					else b[top++]=a[i];

				}

			}

			if(top==1) printf("Yes\n");//假设最后top回到原位( 都配对 )。

			else printf("No\n");

		}

	}

	return 0;

}</span>

当然，栈的问题也能够转化为通过数组模拟栈来解决：

AC代码( 数组 )：

<span style="font-size:14px;">#include<stdio.h>

#include<string.h>

char s[11000],c[11000];

int main()

{

    int t;

    int len;

    int i,j,k;

    int top;

    scanf("%d",&t);

    getchar();

    while(t--)

    {

        gets(s);

        len=strlen(s);

        if(len%2==1)

            printf("No\n");

        else

        {

            top=1;

            c[0]=s[0];

            if(c[0]==']'||c[0]==')')

            printf("No\n");

            else

            {

                for(i=1;i<len;i++)

                {

                    c[top]=s[i];

                    if(top==0)

                        top++;

                    else

                    {

                    if(c[top-1]=='['&&c[top]==']')

                        top--;

                    else if(c[top-1]=='('&&c[top]==')')

                        top--;

                    else

                        top++;

                    }

                }

                if(top==0)

                    printf("Yes\n");

                else

                    printf("No\n");

            }

        }

    }

    return 0;

}</span>

这道题仅仅是对栈的简单应用，另外C++头文件stack中包括有栈处理函数。大家有空能够学习一下STL；

这里仅给出C语言中对栈的定义方法 ( 以整形数据处理为例 ) [ 感谢度娘 T T ]：

<span style="font-size:18px;">#include<stdio.h>

#include<malloc.h>

#define DataType int

#define MAXSIZE 1024

typedef struct

{

DataType data[MAXSIZE];

int top;

}SeqStack;

SeqStack*Init_SeqStack()//栈初始化

{

SeqStack*s;

s=(SeqStack*)malloc(sizeof(SeqStack));

if(!s)

{

printf("空间不足\n");

return NULL;

}

else

{

s->top=-1;

return s;

}

}

int Empty_SeqStack(SeqStack *s)//判栈空

{

if(s->top==-1)

return 1;

else

return 0;

}

int Push_SeqStack(SeqStack *s,DataType x)//入栈

{

if(s->top==MAXSIZE-1)

return 0;//栈满不能入栈

else

{

s->top++;

s->data[s->top]=x;

return 1;

}

}

int Pop_SeqStack(SeqStack *s,DataType *x)//出栈

{

if(Empty_SeqStack(s))

return 0;//栈空不能出栈

else

{

*x=s->data[s->top];

s->top--;

return 1;

}//栈顶元素存入*x。返回

}

DataType Top_SeqStack(SeqStack *s)//取栈顶元素

{

if(Empty_SeqStack(s))

return 0;//栈空

else

return s->data[s->top];

}

int Print_SeqStack(SeqStack *s)

{

int i;

printf("当前栈中的元素:\n");

for(i=s->top;i>=0;i--)

printf("%3d",s->data[i]);

printf("\n");

return 0;

}

int main()

{

SeqStack*L;

int n,num,m;

int i;

L=Init_SeqStack();

printf("初始化完毕\n");

printf("栈空：%d\n",Empty_SeqStack(L));

printf("请输入入栈元素个数：\n");

scanf("%d",&n);

printf("请输入要入栈的%d个元素：\n",n);

for(i=0;i<n;i++)

{

scanf("%d",&num);

Push_SeqStack(L,num);

}

Print_SeqStack(L);

printf("栈顶元素：%d\n",Top_SeqStack(L));

printf("请输入要出栈的元素个数（不能超过%d个）：\n",n);

scanf("%d",&n);

printf("依次出栈的%d个元素：\n",n);

for(i=0;i<n;i++)

{

Pop_SeqStack(L,&m);

printf("%3d",m);

}

printf("\n");

Print_SeqStack(L);

printf("栈顶元素：%d\n",Top_SeqStack(L));

return 0;

}</span>

定义stack的简单代码：

stack<int> sta;

入栈：sta.push(x);

出栈：sta.pop();

推断栈的大小： sta.size( );

推断栈是否为空：sta.empty( );