- 零基础学算法（第4版）
- 张昆 戴艳
- 7349字
- 2025-02-25 05:17:53
2.2 后进先出结构：栈
在程序设计中，栈是一种很常用的数据结构，也是一种重要的线性结构，它是线性表的特殊表现形式。栈必须通过顺序表或链表来实现。本节将介绍栈的特点和操作栈的C语言代码。
2.2.1 栈的概念
栈是一个后进先出的线性表，它要求只在表尾进行删除和插入等操作。所以，栈其实就是一个线性表（顺序表、链表），不过，它在操作上有一些特殊的要求和限制。第一，栈的元素必须先进后出，这与一般的顺序表不同；第二，栈的操作只能限定在这个顺序表的表尾进行。
日常生活中有很多栈的表现形式，例如，当仓库中堆码货物时，先来的货物放在下面，后来的货物码放在上面，而要取出货物时，总是先取上面的（即后放入的先取出），最后才能取到放在下面的货物。
注意 栈按照“后进先出”（Last In First Out，LIFO）的原则处理数据。
栈结构如图2-12所示，在栈中只能在一端进行操作（即保存和取出数据都只能从线性表的一端进行），该操作端称为栈顶，另一端称为栈底。
图2-12 栈示意图
提示 在很多教材中都将“栈”称为“堆栈”，其实，“栈”和“堆”是两个不同的概念，你可以简单理解为：栈是有序的，而堆是无序的。
在栈中，只有栈顶元素是可以访问的。栈的基本操作只有两个：
·入栈（Push）：即将数据保存到栈顶。进行该操作前，先修改栈顶指针，使其向上移一个元素位置，然后将数据保存到栈顶指针所指的位置。
·出栈（Pop）：即将栈顶的数据弹出，然后修改栈顶指针，使其指向栈中的下一个元素。
·栈是一种特殊的线性表，因此，栈也可以使用两种存储表示方法。
·顺序栈：即使用一组地址连续的内存单元依次保存栈中的数据。一般是定义一个指定大小的数组来作为栈，序号为0的元素就是栈底，再定义一个变量top保存栈顶的序号即可。
·链式栈：使用链表形式保存栈中各元素的值，链表尾部（指向地址为NULL）为栈底，链表首部（head指针所指向元素）为栈顶。
下面介绍顺序栈的实现方式，链式栈的实现代码与此类似，读者可自行编写相关代码。
2.2.2 操作栈
对于顺序栈，在程序中一般是使用数组来保存栈中各元素，同时还需设置一个变量top，在该变量中保存一个数组元素的序号，用来表示栈顶位置。
下面介绍C语言操作栈的代码。
1．定义顺序栈的结构
【程序2-8】操作栈的头文件“2-8 SeqStack.h”
1 typedef struct stack //定义顺序栈结构体
2 {
3 DATA data[SIZE+1]; //数据元素
4 int top; //栈顶
5 }SeqStack;
【程序说明】
以上代码定义栈的结构，其中类型DATA表示栈中元素的数据类型，需在主调程序定义（可定义为简单数据类型，也可定义为结构体），在定义数组data时，使用了符号常量SIZE表示栈的最大容量，该符号常量需在主调程序中设置（也可以在当前文件中设置，在主调程序中设置的好处是不用再修改该头文件的内容，以适应各种不同的情况）。
注意 因为C语言的数组下标是从0开始的，为了与日常习惯相同，栈的数据从下标1开始保存（当top为0时表示栈为空），因此，定义数组data的大小为SIZE+1。
整型变量top用来保存栈顶的序号，当top=0时表示栈为空，当top=SIZE时表示栈满。
2．初始化栈
顺序栈的初始化操作需要做两件事：首先按符号常量SIZE指定的大小申请一片内存空间，用来保存栈中的数据；然后设置栈顶指针的值为0，表示是一个空栈。具体代码如下；
6 SeqStack *SeqStackInit() //初始化栈
7 {
8 SeqStack *p;
9 if(p=(SeqStack *)malloc(sizeof(SeqStack))) //申请栈内存
10 {
11 p->top=0; //设置栈顶为0
12 return p; //返回指向栈的指针
13 }
14 return NULL; //申请内存失败, 返回空值
15 }
【程序说明】
第9行申请内存，第11行设置栈顶为0，然后返回申请内存的首地址。如果申请内存失败，将返回NULL。因此，在主调程序中应判断初始化是否成功，然后再进行后续操作。
因为栈使用的内存空间是通过malloc函数分配的，因此，在不使用栈时应调用free函数释放所分配的内存。该函数代码如下：
16 void SeqStackFree(SeqStack *s) //释放栈所占用空间
17 {
18 if(s)
19 free(s);
20 }
编程经验 在不使用栈时，应显式调用free函数释放内存，这是一种好的编程习惯。当程序终止运行时，系统会将所有内存释放，但如果程序一直在运行，且在不断申请内存，则最终可能会导致内存不足的错误。
3．判断栈的状态
在对栈进行操作之前通常需要先判断栈的状态，再决定是否进行操作，例如，入栈前应先判断栈是否已满，然后再决定是否进行入栈操作。而在出栈时应先判断栈是否已经为空，若已经为空，则没有可出栈的数据。下面的这些函数用来进行栈状态的判断。
21 int SeqStackIsEmpty(SeqStack *s) //判断栈是否为空
22 {
23 return(s->top==0);
24 }
25 void SeqStackClear(SeqStack *s) //清空栈
26 {
27 s->top=0;
28 }
29 int SeqStackIsFull(SeqStack *s) //判断栈是否已满
30 {
31 return(s->top==SIZE);
32 }
【程序说明】
·第21~24行是判断栈是否为空的函数，根据栈顶指针top是否为0，判断栈是否为空。
·第25~28行是清空栈的函数，设置栈顶指针top为0，清空栈。
·第29~32行是判断栈是否已满的函数，判断栈顶指针top是否已等于符号常量SIZE，从而判断栈是否已满。
4．入栈操作
入栈和出栈操作是栈的基本操作，入栈（Push）操作是将数据元素保存到栈中，具体的算法如下：
（1）首先判断top是否大于等于SIZE，若是，则给出溢出信息，做出错处理（不能再入栈）。
（2）设置top=top+1（栈顶指针加1，指向入栈地址）。
（3）将入栈元素保存到top指向的位置。
根据该算法编写代码如下：
33 int SeqStackPush(SeqStack *s,DATA data) //入栈操作
34 {
35 if((s->top+1)>SIZE) //栈顶上一个位置超过最大位置
36 {
37 printf("栈溢出!\n"); //显示出错
38 return 0;
39 }
40 s->data[++s->top]=data; //将元素入栈
41 return 1;
42 }
【程序说明】
该函数有两个参数，参数s是一个指向操作的栈的指针，参数data是需要入栈的数据元素。第35行表示栈若溢出，则不进行入栈操作，否则执行第40行修改栈顶指针的值，再将元素入栈。
5．出栈操作
出栈（Pop）操作与入栈相反，是从栈顶弹出一个数据元素，具体的算法如下。
（1）首先判断top是否小于等于0，若是，则给出栈为空信息，做出错处理（没有数据出栈）。
（2）将栈顶指针top所指位置的元素返回。
（3）设置top=top-1（使栈顶指针减1，指向栈的下一个元素，原来栈顶元素被弹出）。
根据该算法编写代码如下：
43 DATA SeqStackPop(SeqStack *s) //出栈操作
44 {
45 if(s->top==0) //判断栈是否为空
46 {
47 printf("栈为空!");
48 exit(0);
49 }
50 return (s->data[s->top--]); //弹出栈顶元素
51 }
【程序说明】
·该函数只有一个参数，s是一个指向操作的栈的指针。函数返回值为一个DATA类型的数据，返回值是栈顶的数据元素。在主调程序中需定义一个DATA类型的变量来接收该返回值。
·第50行首先返回top所指位置的元素，然后修改top的值，使其指向栈中下一个元素，达到抛弃原来栈顶元素的效果（即弹出）。
提示 出栈时必须判断栈是否为空，若不判断而直接弹出栈顶元素，并修改栈顶指针，将得到一个错误的数据，并使栈顶指针指向不明内存区域，可能会让系统出错。
6．获取栈顶元素
使用出栈函数操作后，原来栈顶的元素就被抛弃（弹出）了，也就是说，出栈后原来栈顶的元素就不存在了。在有的情况下，可能需要获取栈顶元素，但又还需要继续保留该元素在栈顶，这时就需要使用获取栈顶元素的函数，具体代码如下：
52 DATA SeqStackPeek(SeqStack *s) //读栈顶元素
53 {
54 if(s->top==0) //判断栈是否为空
55 {
56 printf("栈为空!");
57 exit(0);
58 }
59 return (s->data[s->top]); //返回栈顶元素
60 }
该函数与SeqStackPop函数的代码很相似，只是第59行不同，在该行中只返回栈顶元素，并不执行修改栈顶指针的操作，所以返回栈顶元素后，原来的栈顶元素仍然存在。
7．测试栈的操作
编写好栈的操作函数后，接下来编写一个简单的测试程序，测试栈的操作过程。具体代码如下。
【程序2-9】测试栈的操作文件“2-9 SeqStackTest.c”
1 #include <stdio.h>
2 #include <stdlib.h> //引入分配内存的头文件
3 #define SIZE 50 //栈的大小(保存元素的数量)
4 typedef struct
5 {
6 char name[15];
7 int age;
8 }DATA; //定义入栈元素
9 #include "2-11 SeqStack.h" //引入自定义的作函数文件
【程序说明】
以上代码中，第3行定义栈中能保存的元素数量，第4~8行定义DATA类型，表示栈中每次保存的元素，本例中定义为一个结构体，保存两个字段（姓名和年龄），第9行包含对栈操作的头文件（本节前面编写的代码）。
接下来编写主函数，具体代码如下：
10 int main()
11 {
12 SeqStack *stack;
13 DATA data,data1; //定义栈操作的元素
14 stack=SeqStackInit(); //初始化栈
15 printf("入栈操作:\n");
16 printf("输入姓名 年龄进行入栈操作:");
17 scanf("%s%d",data.name,&data.age);
18 SeqStackPush(stack,data); //入栈
19 printf("输入姓名 年龄进行入栈操作:");
20 scanf("%s%d",data.name,&data.age);
21 SeqStackPush(stack,data); //入栈
22 printf("\n出栈操作:\n按任意键进行出栈操作:");
23 getch(); //把程序暂停下来，等待用户的输入
24
25 data1=SeqStackPop(stack); //出栈
26 printf("出栈的数据是(%s,%d)\n" ,data1.name,data1.age); //显示出栈数据
27 printf("再按任意键进行出栈操作:");
28 getch();
29
30 data1=SeqStackPop(stack); //出栈
31 printf("出栈的数据是(%s,%d)\n" ,data1.name,data1.age); //显示出栈数据
32 SeqStackFree(stack); //释放栈所占用的空间
33 getch();
34 return 0;
35 }
以上代码比较简单，不再逐句讲解。这些代码主要完成了两次入栈和两次出栈的操作。编译执行代码，按提示输入相关信息，如图2-13所示。
图2-13 【程序2-9】执行结果
执行【程序2-9】的过程如图2-14所示，具体过程如下：
第14行初始化栈时，从内存中申请一片空间，设置top的值为0，指向栈底，此时栈为空，如a图所示。
执行第18行将输入的数据入栈，此时栈顶变量top的值为1，如图b所示。
执行第21行将输入的数据入栈，此时栈顶变量top的值为2，如图c所示。
执行第25行进行出栈操作，此时将栈顶数据返回，并修改top的值，使其由原来的2变为1。这样就将栈顶元素丢弃（其实，该数据可能仍然保存在内存中，再次执行入栈操作时，就会将其覆盖），如图d所示。
执行第30行进行出栈操作，此时将栈顶数据返回，并修改top的值，使其由原来的1变为0。此时，top指向了栈底，表示栈为空，如图e所示。
注意 由图2-14可看到出栈后数据仍然在内存中，只是栈顶top指向下面，使其数据不可访问，当有数据再次入栈时才会覆盖原来的数据。
图2-14 入栈、出栈操作
2.2.3 实例：算术表达式求值
计算机程序设计中，很多地方都需要使用栈。例如，在调用函数时，就需要将函数的返回地址、主调函数各变量的值等数据入栈。当调用函数执行结束时，再从栈中弹出变量的值以及返回地址，以恢复主调程序的继续执行。
另外，在所有编译系统中都必须提供的算术表达式求值功能，也是通过栈来实现的。下面以表达式求值为例介绍栈的实际应用。
对于算术表达式的求值，主要就是解决算术运算符的优先级问题，有以下规则：
·先进行乘除运算，再进行加减运算（乘除优先级大于加减）；
·对于相同优先级的运算符，从左向右计算；
·若要改变优先级，可使用括号。对有括号的表达式，先计算括号内，再计算括号外。
任何算术表达式都是由操作数和运算符组成的，为了简化程序，在本例中只考虑加减乘除这4种算术运算，允许添加括号。这样，4种运算符和2个括号（左括号、右括号）就构成了6种运算符。在一个表达式中，需要根据两个运算符的优先级来决定先计算哪一部分。例如，有以下表达式：
（2+3）*5
很容易就知道先算括号中的“2+3”，再将其和乘以5。但是，计算机怎么知道该这样计算呢？从计算机角度出发，只能逐个扫描表达式字符串中的字符，例如，对于上面的算式，有下面的扫描过程：
首先扫描到的字符是左括号“（”，这时还不知道右括号在哪里，因此，需要将左括号保存起来（入栈）。
接着继续扫描下一个字符“2”，也不知道该字符需要和后面的数据进行什么操作（加、减、乘、除或和下一个数字组成一个更大的数）。
继续扫描下一个字符“+”，这时就知道是用数字2加上某一个数，但具体加什么数还不知道，因此，需要将加号“+”保存起来（入栈）。
继续扫描下一个字符“3”，这时就知道是2+3，是否就直接将其相加了呢？还不行，因为如果后面出现乘或除，应该要先计算，因此，需要将数字3保存起来（入栈）。
继续扫描下一个字符“）”，这时，就应该将前面保存的2+3取出来（出栈）计算，得出结果。
在上面的过程中，遇到右括号“）”，则计算前面加号“+”的内容，表示右括号的优先级低于加号。
如何让计算机知道这些预定义的优先级呢，这就需要预先将定义的规则编写成相应的代码进行判断。假设有以下两个操作符构成的算式：
data1 O1 data2 O2 data3
其中，data1、data2、data3表示3个操作数，O1、O2表示两个操作符，如果O1的优先级大于等于O2，则直接从左向右计算，若O1的优先级小于O2，则需要先对右侧data2和data3进行计算。
各算术运算符之间的优先级如表2-1所示。
表2-1 运算符的优先级
在表2-1中，数字“1”表示O1优先级大于等于O2，“-1”表示O1的优先级小于O2，“0”表示左括号遇到了与其配对的右括号，这时不需要计算。
按照表2-1所列规则，就可直接编写代码判断两个运算符的优先级了。
提示 从前面的分析可知，在表达式的计算过程中，既要保存操作数，又要保存运算符。这时，可定义两个栈，一个用来保存操作数，一个用来保存运算符。算法实现过程如图2-15所示。
根据图2-15所示算法编写代码。
图2-15 表达式求值流程图
【程序2-10】表达式求值程序文件“2-10 CalcExp.c”
1 #include<stdio.h> 2 #include<stdlib.h> 3 #define SIZE 50 4 typedef int DATA; //定义栈元素类型 5 #include "2-8 SeqStack.h"
【程序说明】
在计算表达式时，假设每个操作数都是一个整数，因此，在第4行将DATA定义为一个int类型，如果是其他数据类型，则需要修改该行的定义。第5行包含操作栈的头文件。
从图2-15可看到，程序中每次读取的字符都需要判断是否为运算符，因此，单独编写一个函数用来判断，具体代码如下：
6 int IsOperator(char c) //检查字符是否为运算符
7 {
8 switch(c)
9 {
10 case'+':
11 case'-':
12 case'*':
13 case'/':
14 case'(':
15 case')':
16 case'=':
17 return 1;
18 break;
19 default:
20 return 0;
21 break;
22 }
23 }
【程序说明】
该函数比较简单，如果字符c是运算符则返回1，否则返回0。从程序中第10~16行可看到，程序中只将+、-、*、/、（、）、=判断为运算符。
提示 在计算表达式时，为了方便判断，增设了一个等号“=”作为表达式的定界符，即表达式以“=”开始，以“=”结束（当然，也可选择其他字符来定界）。
在计算表达式的值时，需要比较前后两个运算符的优先级，按照表2-1所示的规则编写以下函数，用来判断两个运算符的优先级。
24 int PRI(char oper1,char oper2) //判断两个运算符的优先级
25 //oper1>oper2返回1
26 //oper1<oper2返回-1
27 //oper1、oper2分别为左、右括号返回0
28 {
29 int pri;
30 switch(oper2) //判断运算符优先级
31 {
32 case '+':
33 case '-':
34 if(oper1=='(' | |oper1=='=') //为左括号或表达式开始符号
35 pri=-1; // oper1<oper2
36 else
37 pri=1; //oper1>oper2
38 break;
39 case '*':
40 case '/':
41 if(oper1=='*'||oper1=='/'||oper1==')')
42 pri=1; //oper1>oper2
43 else
44 pri=-1; //oper1<oper2
45 break;
46 case '(':
47 if(oper1==')') //右括号右侧不能马上出现左括号
48 {
49 printf("语法错误!\n");
50 exit(0);
51 }else
52 pri=-1; //oper1<oper2
53 break;
54 case')':
55 if(oper1=='(')
56 pri=0; //都有号配对, 返回0
57 else if (oper1=='=')
58 {
59 printf("括号不匹配!\n");
60 exit(0);
61 }else
62 pri=1; //oper1>oper2
63 break;
64 case '=' :
65 if(oper1=='(')
66 {
67 printf("括号不匹配!\n");
68 exit(0);
69 }else if(oper1=='=')
70 pri=0; //等号配对, 返回0
71 else
72 pri=1; // oper1>oper2
73 break;
74 }
75 return pri;
76 }
该函数中，根据传入的两个运算符进行判断，得到不同的优先级。在主调函数中再根据优先级决定是入栈还是计算。
对于优先级高的运算符，需将运算符两侧的数据进行计算，因此，编写以下函数用来根据运算符和两个操作数进行计算。
77 int Calc(int a,int oper,int b) //计算两个操作数的结果
78 {
79 switch(oper) //根据运算符计算
80 {
81 case'+':return a+b;
82 case'-': return a-b;
83 case'*': return a*b;
84 case'/' //对除法要考虑除以0错误
85 if(b!=0) //除数不能为0
86 return a/b;
87 else
88 {
89 printf("除以0溢出!\n");
90 exit(0);
91 }
92 }
93 }
编程经验 该函数代码简单，对于除法需要考虑除以0错误的问题，这是所有算术运算都需要考虑的。
编写好这些辅助函数，就可以编写计算表达式值的函数了，具体代码如下：
94 int CalcExp(char exp[]) //表达式计算函数
95 {
96 SeqStack *StackOper,*StackData; //指向两个栈的指针变量
97 int i=0,flag=0; //flag作标志, 用来处理多位数
98 DATA a,b,c,q,x,t,oper;
99
100 StackOper=SeqStackInit(); //初始化两个栈
101 StackData=SeqStackInit();
102
103 q=0;
104 x='=';
105 SeqStackPush(StackOper,x); //首先将等号(=)进入操作符栈
106 //x=SeqStackPeek(StackOper); //获取操作符栈的首元素
107 c=exp[i++];
108 while(c!='=' || x!='=') //循环处理表达式中的每个字符
109 {
110 if(IsOperator(c)) //若输入的是运算符
111 {
112 if(flag){ //操作数未入栈
113 SeqStackPush(StackData,q); //将操作数入栈
114 q=0; //操作数清0
115 flag=0; //标志清0, 表示操作数已入栈
116 }
117 switch(PRI(x,c)) //判断运算符的优先级
118 {
119 case -1 //当前运算符大于前一运算符
120 SeqStackPush(StackOper,c); //运算符进栈
121 c=exp[i++];
122 break;
123 case 0 //括号配对
124 c=SeqStackPop(StackOper); //运算符(括号、等号)出栈(抛弃)
125 c=exp[i++]; //取表达式下一字符
126 break;
127 case 1:
128 oper =SeqStackPop(StackOper); //运算符出栈
129 b=SeqStackPop(StackData); //两个操作数出栈
130 a=SeqStackPop(StackData);
131 t=Calc(a, oper,b); //计算结果
132 SeqStackPush(StackData,t); //将运算结果入栈
133 break;
134 }
135 }else if(c>='0'&&c<='9') //若输入字符在0~9之间
136 {
137 c-='0'; //将字符转换为对应的数值
138 q=q*10+c; //多位数的进位处理
139 flag=1; //设置标志, 表示操作数未入栈
140 c=exp[i++]; //取表达式下一字符
141 }
142 else
143 {
144 printf("输入错误!\n");
145 getch();
146 exit(0);
147 }
148 x=SeqStackPeek(StackOper); //获取栈顶的运算符
149 }
150 q=SeqStackPop(StackData);
151 SeqStackFree(StackOper); //释放栈所占用的空间
152 SeqStackFree(StackData);
153 return q; //出栈, 返回结果
154 }
【程序说明】
该函数代码较多，下面逐个介绍各部分的作用。
·第94行定义函数头，该函数需要一个字符串作为参数，返回值是一个整型数（表达式的计算结果）。
·第97行定义了一个标志变量flag，该标志变量用来处理多位数的情况。因为下面的代码一次只从表达式字符串中获取1个字符，如果操作数为多位数，则需要将该数的每一位获取后再入栈，因此使用标志变量flag，当其值为0时，表示没有操作数要入栈，当其值非0时，表示有操作数需要入栈。具体用法看下面的代码。
·第100、101行初始化两个栈，分别用来保存运算符和操作数。
·第103行初始化变量q为0，变量q用来保存多位的操作数。
·第104、105行初始化变量x为等号“=”，并将该符号作为表达式的第一个运算符入栈。
·第107行从表达式字符串中获取第1个字符，开始扫描表达式的操作。
·第108~149行为一个循环，在该循环中将逐个处理表达式字符串中的每个字符，直到遇到表达式结束字符“=”为止。
·第110~134行处理获取的字符为运算符的情况。
·首先执行第112~116行，如果flag为非0，表示有操作数未入栈，先将操作数入栈，再设置标志flag为0。
·第117~134行处理不同优先级运算符的情况，若当前运算符（保存在变量c中）比前一个运算符（保存在变量x中）优先级大（PRI函数返回的值为-1），则在第120行将运算符入栈，再获取表达式的下一个字符进行处理。若PRI函数返回的值为0，表示括号配对，这时只需将运算符栈中的左括号弹出（第124行）即可，然后再获取表达式的下一个字符进行处理。若PRI函数返回值为1（前一运算符优先级大），则需要将前一运算符弹出（第128行），再将前两个操作数弹出（第129、130行），再调用Calc函数进行计算（第131行），然后将计算结果入栈（第132行）。这时需要注意，变量c中还保存着一个运算符未处理，因此，不能再去处理表达式中的下一字符，而是继续判断变量c中保存的运算符和栈中前一个运算符的优先级（即到第148行获取运算符栈的栈顶元素，然后又回到循环的初始位置）。
·如果读入的字符不是运算符，第135~141行判断是不是数字（即字符0~9），若为数字，则执行第137~140行的操作，第137行将字符（这里是ASCII码）转换为对应的数值，第138行累加多位数（将以前数值乘10，当前位累加到个位），第139行设置标志flag为非0值，表示有数据还没压入操作数栈，第140行获取表达式的下一字符继续进行处理。
·如果读入的字符既不是运算符，也不是0~9的数字，则执行第142~147行提示错误。
·第148行从运算符栈的栈顶获取上一个运算符，方便第117行比较两个运算符的优先级，以进行不同运算。
·当处理完表达式中所有字符串后，最终结果保存在操作数栈中，第150行将其弹出保存到变量q中，第153行返回该变量的值。
·第151、152行释放两个栈所占用的内存空间。
提示 表达式求值函数的计算过程有点复杂，因此解释得比较详细，读者可结合图2-15理解这部分代码。
编写好CalcExp函数，主函数就很简单了。在主函数中只需提示用户输入一个表达式字符串，然后调用CalcExp函数即可。主函数可编写为以下样式：
155 int main()
156 {
157 int c;
158 char exp[80];
159 printf("请输入要计算的表达式(以=结束):");
160 scanf("%s",exp);
161 printf("%s%d\n",exp,CalcExp(exp));
162 getch();
163 return 0;
164 }
这部分代码简单，就不再逐句介绍了。
编译执行以上代码，输入一个表达式，可得到该表达式的值，如图2-16所示。
图2-16 【程序2-10】执行结果