概念描述

栈是限定仅在表位进行插入或删除操作的线性表。栈的表尾称为栈顶，表头称为栈底。不含元素的栈称为空栈。

左图为栈的示意图，右图为用铁路调度表示栈。

如下是入栈至栈满再进行出栈的过程示意图。值得注意的是，栈满后，top指针指向的不是顶端元素，而是顶端的下一个位置。

基本操作

构造一个空栈S

在正式开始前，照例需要定义一些如下的常量

#define STACK_INIT_SIZE 100//存储空间初始分配量 #define STACKINCREMENT 10//存储空间分配增量 #define TRUE 1 #define ERROR 0 #define OVERFLOW -2 typedef char SElemType; tyoedef int Status; 

typedef struct{    SElemType *base;//栈底指针.在栈构造之前和销毁之后,base的值为NULL    SElemType *top;//栈顶指针    int stacksize;//当前已分配的存储空间,初始值一般为STACK_INIT_SIZE,不够时再以STACKINCREMENT为单位扩大 }SqStack;

在顺序栈中，base指针始终指向栈底元素，栈不存在的条件为base=NULL。top指针初值指向栈底，栈空的条件为base==top。栈不空时，top指向(栈顶+1)。也就是说，在正常情况下，S.top 是不指向任何元素的。(top-base)的值即为栈中元素的个数，也即栈的长度。当top-base==stacksize时，说明栈满。此时若想进行入栈操作，需要扩充分配存储空间。

判空

Status StackEmpty(SqStack S) {   if(!S.base) return TRUE;   else return FALSE; }

构造一个空栈

Status InitStack(SqStack &S) {   S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));   if(!S.base) exit(OVERFLOW);   S.top=S.base;   S.stacksize=STACK_INIT_SIZE;   return OK; }

若栈不存在，分配空间时发生上溢出错误而退出。

入栈

在入栈、出栈、取栈顶元素的函数中，不存在分配空间的问题，是return ERROR而不是 exit(OVERFLOW)

Status Push(SqStack& S, SEIemType e)//入栈 { 	if (S.top - S.base >= S.stacksize) return ERROR; 	*S.top = e;//注意S.top是指针型变量 	S.top++;//先赋值,再加一 	return OK; }

出栈

Status (SqStack &S) {  if(S.top==S.base) return ERROR;  S.top--;  e=*(S.top); return OK； }

值得注意的是，出栈后，元素e并未从栈中删除。改变的只是top指针的位置。虽然e还在栈中，但栈长已经改变，e的原位置此后可以被其它值覆盖。

取栈顶元素

取栈顶元素就是“top指针位置不变”版的“出栈”。博主初学时没意识到这一点，以为出栈就是删除元素，所以构造了一个很复杂的取栈顶元素函数。为避免误导，就不放在这里了。

Status(SqStack S,SElemType) {  if(S.top==S.base) return ERROR;  e=*(S.top-1);//top指针位置不变  return OK; }

输出栈中所有元素

和取栈顶元素同理，在不移动指针位置的情况下输出元素。若采用for循环，需要先求栈长。一般使用while循环。

Status PrintStack(SqStack S) {  int i=0;  SElemType *s;  s=S.base;//注意！顺序栈从底部开始向上存储，顺序输出是从S.base开始  //并且，如果想做逆序输出，while循环条件应为s!=S.base-1  while(s!=S.top)  {   printf("%c\n",*s);   s++;   i++;  }  printf("已输出栈中%d个元素",i);  return OK； }

Status PrintStack(SqStack S) {  int a=S.top-S.base;  if(S.base==S.top) return ERROR;  int i;  for(i=1;i<=a;i++)     printf("%c\n",*(S.top-a));  printf("已输出栈中%d个元素",a);  return OK; }

括号匹配

题干描述

由键盘输入一系列左括号和右括号，判断这些括号是否成功配对。一旦发现不配对的括号，立刻退出程序并说明原因。如：( { [ ] [ ] } )是匹配成功，而((]是由于括号不匹配而失败，{ ( [ ] )是因为左括号多余而失败，( { } ) ]是因为右括号多余而失败。

题目分析

代码(含分析)

Status March_Brackets(SqStack& S) { 	char ch;//输入一连串字符(括号),以回车结束.起初,括号都存储在ch中,栈S为空栈. 	SElemType* s; 	s = S.top-1;//s指向栈顶元素 	printf("请输入字符:\n"); 	ch = getchar();//输入括号,进入循环 	while (ch != '\n')//循环接收括号字符以回车为结束符,每输入一个括号,就进行一次判断。 	{ 		if (ch =='(' || ch == '[' || ch == '{') //如果ch是左括号,入栈.栈中存放左括号,有匹配的右括号就出栈.若全部匹配成功,栈空。 			Push(S, ch); //入栈 			if (ch == ')')//输入字符为右括号 			{ 				if ((Pop(S, *s) == 0)) { printf("右括号多余,不匹配\n"); return ERROR; } 				/*在Pop函数中, 若返回值为0, 说明是空栈.这有两种情况:1,还未输入左括号,第一个输入的就是右括号; 				2,之前输入的左、右括号都已成功匹配,左括号已全部出栈*/ 				else if (*s != '(') { printf("右括号与左括号不匹配\n"); return ERROR; } 				/*最后输入的左括号不是小括号,与输入的右小括号不匹配*/ 			} 			else if (ch == ']') 			{ 				if ((Pop(S, *s) == 0)) { printf("右括号多余,不匹配\n"); return ERROR; } 				else if (*s != '[') { printf("右括号与左括号不匹配\n"); return ERROR; } 			} 			else if (ch == '}') 			{ 				if ((Pop(S, *s) == 0)) { printf("右括号多余,不匹配\n"); return ERROR; } 				else if (*s != '{') { printf("右括号与左括号不匹配\n"); return ERROR; } 			} 			ch = getchar(); 	}//循环结束,说明输入的右括号都有预支品牌的左括号.但这不意味着匹配成功！！还有左括号多余的可能。 	if (S.top != S.base)//栈不空,说明有左括号未出栈,未匹配 	{ 		printf("左括号多余,不匹配\n"); 		return ERROR; 	} 	else//栈空,说明左括号已全部出栈,匹配成功 	{ 		printf("匹配完整,成功退出\n"); 		return OK; 	} } 

上机实现

完整代码

经高手指点：由于getchar的一些特性，建议只执行一次括号判断函数。不要在主函数中反复执行它。

#include  #include  typedef char SElemType; typedef int Status; constexpr auto ERROR = 0; constexpr auto OK = 1; constexpr auto OVERFLOW = -2; constexpr auto STACK_MAX_SIZE = 100; typedef struct { 	SElemType* base; 	SElemType* top; 	int stacksize; }SqStack; Status InitStack(SqStack& S)//建立空顺序栈 { 	S.stacksize = STACK_MAX_SIZE; 	S.base = (SElemType*)malloc(STACK_MAX_SIZE * sizeof(SElemType)); 	if (!S.base) exit(OVERFLOW); 	S.top = S.base; 	return OK; } Status Push(SqStack& S, SElemType e)//入栈 { 	if (S.top - S.base >= S.stacksize) exit(OVERFLOW); 	*S.top = e;//注意S.top是指针型变量 	S.top++;//先赋值,再加一 	return OK; } Status Pop(SqStack& S, SElemType& e)//出栈 { 	if (S.base == S.top) return ERROR; 	S.top--;//注意S.top是指针型变量 	e = *S.top;//先减一,再赋值 	return OK; } Status GetTop(SqStack S, SElemType &e)//获取栈顶元素 { 	if (S.top == S.base) return ERROR; 	e = *(S.top - 1);//top指针位置不变 	return OK; } Status PrintStack(SqStack S)//输出栈所有元素 { 	if (S.top == S.base) return ERROR; 	int i = 0; 	SElemType* s; 	s = S.base; 	while (s != S.top) 	{ 		printf("%c\n", *s); 		i++; 		s++; 	} 	printf("已输出栈中%d个元素", i); 	return OK;  } Status March_Brackets(SqStack& S) { 	char ch;//输入一连串字符(括号),以回车结束.起初,括号都存储在ch中,栈S为空栈. 	SElemType* s; 	s = S.top-1;//s指向栈顶元素 	printf("请输入字符:\n"); 	ch = getchar();//输入括号,进入循环 	while (ch != '\n')//循环接收括号字符以回车为结束符,每输入一个括号,就进行一次判断。 	{ 		if (ch =='(' || ch == '[' || ch == '{') //如果ch是左括号,入栈.栈中存放左括号,有匹配的右括号就出栈.若全部匹配成功,栈空。 			Push(S, ch); //入栈 			if (ch == ')')//输入字符为右括号 			{ 				if ((Pop(S, *s) == 0)) { printf("右括号多余,不匹配\n"); return ERROR; } 				/*在Pop函数中, 若返回值为0, 说明是空栈.这有两种情况:1,还未输入左括号,第一个输入的就是右括号; 				2,之前输入的左、右括号都已成功匹配,左括号已全部出栈*/ 				else if (*s != '(') { printf("右括号与左括号不匹配\n"); return ERROR; } 				/*最后输入的左括号不是小括号,与输入的右小括号不匹配*/ 			} 			else if (ch == ']') 			{ 				if ((Pop(S, *s) == 0)) { printf("右括号多余,不匹配\n"); return ERROR; } 				else if (*s != '[') { printf("右括号与左括号不匹配\n"); return ERROR; } 			} 			else if (ch == '}') 			{ 				if ((Pop(S, *s) == 0)) { printf("右括号多余,不匹配\n"); return ERROR; } 				else if (*s != '{') { printf("右括号与左括号不匹配\n"); return ERROR; } 			} 			ch = getchar(); 	}//循环结束,说明输入的右括号都有预支品牌的左括号.但这不意味着匹配成功！！还有左括号多余的可能。 	if (S.top != S.base)//栈不空,说明有左括号未出栈,未匹配 	{ 		printf("左括号多余,不匹配\n"); 		return ERROR; 	} 	else//栈空,说明左括号已全部出栈,匹配成功 	{ 		printf("匹配完整,成功退出\n"); 		return OK; 	} }  int main(void) { 	SqStack S; int i; 	char e; char f; char k; 	InitStack(S); 	printf("请向栈中输入字符\n"); 	for (i = 0; i < 7; i++) 	{ 		scanf_s("%c", &e); 		Push(S, e);//入栈 	} 	printf("已初始化栈如下\n"); 	PrintStack(S); 	GetTop(S, f);//获取栈顶元素 	printf("栈顶元素为\n"); 	putchar(f); 	printf("删除栈顶元素\n"); 	Pop(S, k);//出栈 	printf("更新栈如下\n"); 	PrintStack(S);  	printf("下面进入括号匹配\n");      SqStack B; 	InitStack(B); 	March_Brackets(B);  	return 0; }

运行结果