1、第第4章章 栈栈 栈是一种操作受限的线性表。栈具有线性表的结构特点，即每栈是一种操作受限的线性表。栈具有线性表的结构特点，即每一个元素只有一个前驱元素和后继元素（除了第一个元素和最后一一个元素只有一个前驱元素和后继元素（除了第一个元素和最后一个元素外），但它只允许在表的一端进行插入和删除操作。个元素外），但它只允许在表的一端进行插入和删除操作。本章重点和难点：本章重点和难点：1、栈的顺序表示与算法实现、栈的顺序表示与算法实现 2、栈的链式表示与算法实现、栈的链式表示与算法实现 3、求算术表达式的值、求算术表达式的值 4、迷宫求解问题、迷宫求解问题 5、递归的消除、递归的消除4.1 栈的定义与抽
2、象数据类型栈的定义与抽象数据类型4.1.1 什么是栈 栈（栈（stack），也称为堆栈，它是限定仅在表尾进行插入和删除），也称为堆栈，它是限定仅在表尾进行插入和删除操作的线性表。对栈来说，表尾（允许操作的一端）称为栈顶操作的线性表。对栈来说，表尾（允许操作的一端）称为栈顶（top），另一端称为栈底（），另一端称为栈底（bottom）。栈顶是动态变化的，它由一）。栈顶是动态变化的，它由一个称为栈顶指针（个称为栈顶指针（top）的变量指示。当表中没有元素时，称为空栈。）的变量指示。当表中没有元素时，称为空栈。栈的插入操作称为入栈或进栈，删除操作称为出栈或退栈。栈的插入操作称为入栈或进栈，删除操作称
3、为出栈或退栈。4.1 栈的定义与抽象数据类型栈的定义与抽象数据类型 在栈在栈S=(a1,a2,an)中，中，a1称为栈底元素，称为栈底元素，an称为栈顶元素，由栈称为栈顶元素，由栈顶指针顶指针top指示。栈中的元素按照指示。栈中的元素按照a1，a2，an的顺序进栈，当前的顺序进栈，当前的栈顶元素为的栈顶元素为an。如图。如图4.1所示。最先进栈的元素一定是栈底元素，所示。最先进栈的元素一定是栈底元素，最后进栈的元素一定是栈顶元素。每次删除的元素是栈顶元素，也就最后进栈的元素一定是栈顶元素。每次删除的元素是栈顶元素，也就是最后进栈的元素。因此，栈是一种后进先出（是最后进栈的元素。因此，栈是一种后
4、进先出（last in first out，简，简称称LIFO）的线性表。）的线性表。4.1 栈的定义与抽象数据类型栈的定义与抽象数据类型 若将元素若将元素a、b、c和和d依次入栈，最后将栈顶元素出栈，依次入栈，最后将栈顶元素出栈，栈顶指针栈顶指针top的变化情况如图的变化情况如图4.2所示。所示。4.1 栈的定义与抽象数据类型栈的定义与抽象数据类型4.1.2 栈的抽象数据类型 1数据对象集合数据对象集合 栈的数据对象集合为栈的数据对象集合为a1，a2，an，每个元素都有，每个元素都有相同的类型相同的类型DataType。栈中数据元素之间是一对一的关系。栈具有线性表的特栈中数据元素之间是一对一
5、的关系。栈具有线性表的特点：除了第一个元素点：除了第一个元素a1外，每一个元素有且只有一个直接外，每一个元素有且只有一个直接前驱元素，除了最后一个元素前驱元素，除了最后一个元素an外，每一个元素有且只有外，每一个元素有且只有一个直接后继元素。一个直接后继元素。4.1 栈的定义与抽象数据类型栈的定义与抽象数据类型 2 2基本操作集合基本操作集合 （1）InitStack(&S)：初始化操作，建立一个空栈：初始化操作，建立一个空栈S。（2）StackEmpty(S)：若栈：若栈S为空，返回为空，返回1，否则返回，否则返回0。（3）GetTop(S,&e)：返回栈：返回栈S的栈顶元素给的栈顶元素给e
6、。（4）PushStack(&S,e)：在栈：在栈S中插入元素中插入元素e，使其成为新的栈顶元，使其成为新的栈顶元素。素。（5）PopStack(&S,&e)：删除栈：删除栈S的栈顶元素，并用的栈顶元素，并用e返回其值。返回其值。（6）StackLength(S)：返回栈：返回栈S的元素个数。的元素个数。（7）ClearStack(S)：清空栈：清空栈S。4.2 栈的顺序表示与实现栈的顺序表示与实现 4.2.1 栈的顺序存储结构 采用顺序存储结构的栈称为顺序栈。顺序栈是利用一组地址连续的采用顺序存储结构的栈称为顺序栈。顺序栈是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，可利用存储
7、单元依次存放自栈底到栈顶的数据元素，可利用C语言中的数组作语言中的数组作为顺序栈的存储结构，同时附设一个栈顶指针为顺序栈的存储结构，同时附设一个栈顶指针top，用于指向顺序栈的，用于指向顺序栈的栈顶元素。当栈顶元素。当top=0时表示空栈。时表示空栈。栈的顺序存储结构类型描述如下：栈的顺序存储结构类型描述如下：#define StackSize 100 typedef struct DataType stackStackSize;int top;SeqStack;中缀表达式6+(7-1)*3+10/2#转换为后缀表达式的处理流程如图4.return 1;如何将中缀表达式转换为后缀表达式呢？vo
8、id ClearStack(SeqStack*S)（2）StackEmpty(S)：若栈S为空，返回1，否则返回0。/*将塔座A上按照从小到大自上而下编号为1到n的那个圆盘按照规则搬到塔座C上，B可以作为辅助塔座*/if(S-top0=S-top1)/*如果共享栈已满*/case 1:/*当flag为1，表示将元素进左端的栈*/两个月后，生下一对小兔子，小兔子数共有2对兔子；递归的调用过程也是系统借助栈的特性实现的。（1）后缀表达式与中缀表达式的操作数出现顺序相同，只是运算符先后顺序改变了；递归问题可以被分解成规模小、性质相同的问题加以解决。p=p-next;/*p指向下一个结点，即下一次要释
9、放的结点*/typedef structLStackNode,*LinkStack;转换后的八进制数为(13056)8。【例4_5】通过键盘输入一个表达式，如6+(7-1)*3+10/2，要求将其转换为后缀表达式，并计算该表达式的值。return 0;/*返回0*/case 2:/*当flag为2，表示将元素要进右端的栈*/4.2 栈的顺序表示与实现栈的顺序表示与实现 当栈中元素已经有当栈中元素已经有StackSize个时，称为栈满。如果继续进栈操作则会产生个时，称为栈满。如果继续进栈操作则会产生溢出，称为上溢。对空栈进行删除操作，称为下溢。溢出，称为上溢。对空栈进行删除操作，称为下溢。顺序栈
10、的结构如图顺序栈的结构如图4.3所示。元素所示。元素a、b、c、d、e、f、g、h依次进栈后，依次进栈后，a为栈底元素，为栈底元素，h为栈顶元素。在实际操作中，栈顶指针指向栈顶元素的下一个为栈顶元素。在实际操作中，栈顶指针指向栈顶元素的下一个位置。位置。顺序栈涉及的一些基本操作如下：顺序栈涉及的一些基本操作如下：（1）在初始化栈时，将栈顶指针置为）在初始化栈时，将栈顶指针置为0，即令，即令S.top=0。（2）判断栈空条件为）判断栈空条件为S.top=0，栈满条件为，栈满条件为S.top=StackSize-1。（3）栈的长度（即栈中元素个数）为）栈的长度（即栈中元素个数）为S.top。（4）
11、进栈操作时，先判断栈是否已满，若未满，将元素压入栈中，即）进栈操作时，先判断栈是否已满，若未满，将元素压入栈中，即S.stackS.top=e，然后使栈顶指针加，然后使栈顶指针加1，即，即S.top+。出栈操作时，先判断。出栈操作时，先判断栈是否为空，若为空，使栈顶指针减栈是否为空，若为空，使栈顶指针减1，即，即S.top-，然后元素出栈，即，然后元素出栈，即e=S.stackS.top。4.2 栈的顺序表示与实现栈的顺序表示与实现4.2.2 顺序栈的基本运算顺序栈的基本运算（1）初始化栈。）初始化栈。void InitStack(SeqStack*S)/*初始化栈初始化栈*/S-top=0;
12、/*把栈顶指针置为把栈顶指针置为0*/（2）判断栈是否为空。）判断栈是否为空。int StackEmpty(SeqStack S)/*判断栈是否为空，栈为空返回判断栈是否为空，栈为空返回1，否则返回，否则返回0*/if(S.top=0)/*如果栈顶指针如果栈顶指针top为为0*/return 1;/*返回返回1*/else/*否则否则*/return 0;/*返回返回0*/4.2 栈的顺序表示与实现栈的顺序表示与实现（3）取栈顶元素。）取栈顶元素。int GetTop(SeqStack S,DataType*e)if(S.toptop=StackSize)/*如果栈已满如果栈已满*/print
13、f(“栈已满，不能将元素进栈！栈已满，不能将元素进栈！n”);return 0;else/*否则否则*/S-stackS-top=e;/*元素元素e进栈进栈*/S-top+;/*修改栈顶指针修改栈顶指针*/return 1;4.2 栈的顺序表示与实现栈的顺序表示与实现（5）将栈顶元素出栈。）将栈顶元素出栈。int PopStack(SeqStack*S,DataType*e)if(S-top=0)/*如果栈为空如果栈为空*/printf(“栈中已经没有元素，不能进行出栈操作栈中已经没有元素，不能进行出栈操作!n”);return 0;else/*否则否则*/S-top-;/*先修改栈顶指针，即
14、出栈先修改栈顶指针，即出栈*/*e=S-stackS-top;/*将出栈元素赋给将出栈元素赋给e*/return 1;4.2 栈的顺序表示与实现栈的顺序表示与实现（6）求栈的长度。）求栈的长度。int StackLength(SeqStack S)/*求栈的长度求栈的长度*/return S.top;（7）清空栈。）清空栈。void ClearStack(SeqStack*S)/*清空栈清空栈*/S-top=0;/*将栈顶指针置为将栈顶指针置为0*/4.2 栈的顺序表示与实现栈的顺序表示与实现4.2.3 顺序栈应用举例 【例【例4_1】利用顺序栈的基本操作，将元素】利用顺序栈的基本操作，将元素
15、A、B、C、D、E、F依次进栈，然后将依次进栈，然后将F和和E出栈，再将出栈，再将G和和H进栈，最后将元素全部出进栈，最后将元素全部出栈，并依次输出出栈元素。栈，并依次输出出栈元素。4.2 栈的顺序表示与实现栈的顺序表示与实现 【例【例4_2】有两个栈】有两个栈S1和和S2都采用顺序结构存储，并且共享一个存都采用顺序结构存储，并且共享一个存储区。为了尽可能利用存储空间，减少溢出的可能，采用栈顶相向，储区。为了尽可能利用存储空间，减少溢出的可能，采用栈顶相向，迎面增长的方式，试设计迎面增长的方式，试设计S1和和S2有关入栈和出栈算法。有关入栈和出栈算法。【分析】该题是哈尔滨工业大学的考研试题，主
16、要考察共享栈的算【分析】该题是哈尔滨工业大学的考研试题，主要考察共享栈的算法设计。法设计。1 1什么是栈的共享什么是栈的共享 在使用顺序栈时，因为栈空间的大小难以准确估计，可能会出现有的栈还有空闲空间。为了能充分利用栈的空间，可以让多个栈共享一个足够大的连续存储空间，通过利用栈顶指针能灵活移动的特性，使多个栈存储空间互相补充，存储空间得到有效利用，这就是栈的共享栈的共享。4.2 栈的顺序表示与实现栈的顺序表示与实现 共享栈的数据结构类型描述如下。共享栈的数据结构类型描述如下。typedef struct DataType stackStackSize;int top2;SSeqStack;其中
17、，其中，top0和和top1分别是两个栈的栈顶指针。分别是两个栈的栈顶指针。用一维数组表示的共享栈如图用一维数组表示的共享栈如图4.5所示。所示。4.2 栈的顺序表示与实现栈的顺序表示与实现2 2共享栈的基本运算共享栈的基本运算（1）初始化栈。）初始化栈。void InitStack(SSeqStack*S)/*共享栈的初始化共享栈的初始化*/S-top0=0;S-top1=StackSize-1;4.2 栈的顺序表示与实现栈的顺序表示与实现（2）取栈顶元素。）取栈顶元素。int GetTop(SSeqStack S,DataType*e,int flag)/*取栈顶元素。将栈顶元素值返回给取
18、栈顶元素。将栈顶元素值返回给e，并返回，并返回1表示成功；否则返回表示成功；否则返回0表示失败。表示失败。*/switch(flag)case 1:/*为为1，表示要取左端栈的栈顶元素，表示要取左端栈的栈顶元素*/if(S.top0=0)return 0;*e=S.stackS.top0-1;break;case 2:/*为为2，表示要取右端栈的栈顶元素，表示要取右端栈的栈顶元素*/if(S.top1=StackSize-1)return 0;*e=S.stackS.top1+1;break;default:return 0;return 1;4.2 栈的顺序表示与实现栈的顺序表示与实现（3）
19、将元素）将元素e入栈。入栈。int PushStack(SSeqStack*S,DataType e,int flag)/*将元素将元素e入共享栈。进栈成功返回入共享栈。进栈成功返回1，否则返回，否则返回0*/if(S-top0=S-top1)/*如果共享栈已满如果共享栈已满*/return 0;/*返回返回0，进栈失败，进栈失败*/switch(flag)case 1:/*当当flag为为1，表示将元素进左端的栈，表示将元素进左端的栈*/S-stackS-top0=e;/*元素进栈元素进栈*/S-top0+;/*修改栈顶指针修改栈顶指针*/break;case 2:/*当当flag为为2，表
20、示将元素要进右端的栈，表示将元素要进右端的栈*/S-stackS-top1=e;/*元素进栈元素进栈*/S-top1-;/*修改栈顶指针修改栈顶指针*/break;default:return 0;return 1;/*返回返回1，进栈成功，进栈成功*/4.2 栈的顺序表示与实现栈的顺序表示与实现（4）将栈顶元素出栈。）将栈顶元素出栈。int PopStack(SSeqStack*S,DataType*e,int flag)switch(flag)/*在出栈操作之前，判断哪个栈要进行出栈操作在出栈操作之前，判断哪个栈要进行出栈操作*/case 1:/*为为1，表示左端的栈需要出栈操作，表示左端
21、的栈需要出栈操作*/if(S-top0=0)/*左端的栈为空左端的栈为空*/return 0;/*返回返回0，出栈操作失败，出栈操作失败*/S-top0-;/*修改栈顶指针，元素出栈操作修改栈顶指针，元素出栈操作*/*e=S-stackS-top0;/*将出栈的元素赋给将出栈的元素赋给e*/break;case 2:/*为为2，表示右端的栈需要出栈操作，表示右端的栈需要出栈操作*/if(S-top1=StackSize-1)/*右端的栈为空右端的栈为空*/return 0;/*返回返回0，出栈操作失败，出栈操作失败*/S-top1+;/*修改栈顶指针，元素出栈操作修改栈顶指针，元素出栈操作*/
22、*e=S-stackS-top1;/*将出栈的元素赋给将出栈的元素赋给e*/break;default:return 0;return 1;/*返回返回1，出栈操作成功，出栈操作成功*/4.2 栈的顺序表示与实现栈的顺序表示与实现（5）判断栈是否为空。）判断栈是否为空。int StackEmpty(SSeqStack S,int flag)switch(flag)case 1:/*为为1，表示判断左端的栈是否为空，表示判断左端的栈是否为空*/if(S.top0=0)return 1;break;case 2:/*为为2，表示判断右端的栈是否为空，表示判断右端的栈是否为空*/if(S.top1=
23、StackSize-1)return 1;break;default:printf(“输入的输入的flag参数错误参数错误!”);return-1;return 0;else/*否则*/else if(n=1)转换后的八进制数为(13056)8。/*判断栈是否为空，栈为空返回1，否则返回0*/if(S-top0=S-top1)/*如果共享栈已满*/printf(“栈已空”);（2）StackEmpty(S)：若栈S为空，返回1，否则返回0。当n=1时，递归调用开始逐层返回，参数开始出栈，如图4.递归问题可以被分解成规模小、性质相同的问题加以解决。S-top0=0;和、和、(和)分别是匹配的括号
24、，括号的嵌套顺序是任意的，即()和()等为正确的格式，、()和()等为不正确的格式。case 2:/*当flag为2，表示将元素要进右端的栈*/switch(flag)（2）后缀表达式不出现括号。return Ack(m-1,1);else if(n=1)当top=0时表示空栈。（3）将控制转到被调用函数的入口。完整的求解迷宫程序如下。top-next=p。由于链栈的操作都是在链表的表头位置进行，因而链栈的基本操作的时间复杂度均为O(1)。if(*top=(LinkStack)malloc(sizeof(LStackNode)=NULL)4.3 栈的链式表示与实现栈的链式表示与实现 在顺序栈中
25、，由于顺序存储结构需要事先静态分配，而存储规模往往在顺序栈中，由于顺序存储结构需要事先静态分配，而存储规模往往又难以确定，如果栈空间分配过小，可能会造成溢出；如果栈空间分配又难以确定，如果栈空间分配过小，可能会造成溢出；如果栈空间分配过大，又造成存储空间浪费。过大，又造成存储空间浪费。4.3.1 栈的存储结构 栈的链式存储结构是用一组不一定连续的存储单元来存放栈中的数栈的链式存储结构是用一组不一定连续的存储单元来存放栈中的数据元素的。一般来说，当栈中数据元素的数目变化较大或不确定时，使据元素的。一般来说，当栈中数据元素的数目变化较大或不确定时，使用链式存储结构作为栈的存储结构是比较合适的。人们
26、将用链式存储结用链式存储结构作为栈的存储结构是比较合适的。人们将用链式存储结构表示的栈称为链栈或链式栈。构表示的栈称为链栈或链式栈。4.3 栈的链式表示与实现栈的链式表示与实现 链栈通常用单链表表示。插入和删除操作都在栈顶指针的位置进行，链栈通常用单链表表示。插入和删除操作都在栈顶指针的位置进行，这一端称为栈顶，通常由栈顶指针这一端称为栈顶，通常由栈顶指针top指示。为了操作上的方便，通常指示。为了操作上的方便，通常在链栈中设置一个头结点，用栈顶指针在链栈中设置一个头结点，用栈顶指针top指向头结点，头结点的指针指向头结点，头结点的指针指向链栈的第一个结点。例如，元素指向链栈的第一个结点。例如
27、，元素a、b、c、d依次入栈的链栈如图依次入栈的链栈如图4.7所示。所示。4.3 栈的链式表示与实现栈的链式表示与实现 栈顶指针栈顶指针top始终指向头结点，最先入栈的元素在链栈的栈底，最始终指向头结点，最先入栈的元素在链栈的栈底，最后入栈的元素成为栈顶元素。由于链栈的操作都是在链表的表头位后入栈的元素成为栈顶元素。由于链栈的操作都是在链表的表头位置进行，因而链栈的基本操作的时间复杂度均为置进行，因而链栈的基本操作的时间复杂度均为O(1)。链栈的结点类型描述如下：链栈的结点类型描述如下：typedef struct node DataType data;struct node*next;LSt
28、ackNode,*LinkStack;4.3 栈的链式表示与实现栈的链式表示与实现 4.3.2 链栈的基本运算（1）初始化链栈。）初始化链栈。void InitStack(LinkStack*top)/*链栈的初始化链栈的初始化*/if(*top=(LinkStack)malloc(sizeof(LStackNode)=NULL)exit(-1);(*top)-next=NULL;/*将链栈的头结点指针域置为空将链栈的头结点指针域置为空*/4.3 栈的链式表示与实现栈的链式表示与实现（2）判断链栈是否为空。）判断链栈是否为空。int StackEmpty(LinkStack top)/*判断链
29、栈是否为空判断链栈是否为空*/if(top-next=NULL)/*如果头结点的指针域为空如果头结点的指针域为空*/return 1;/*返回返回1*/else/*否则否则*/return 0;/*返回返回0*/4.3 栈的链式表示与实现栈的链式表示与实现 （3）将元素）将元素e入栈。先动态生成一个结点，用入栈。先动态生成一个结点，用p指向该结点，将元指向该结点，将元素素e值赋给值赋给*p结点的数据域，然后将新结点插入到链表的第一个结点之结点的数据域，然后将新结点插入到链表的第一个结点之前。把新结点插入到链表中分为两个步骤：前。把新结点插入到链表中分为两个步骤：p-next=top-next；
30、top-next=p。进栈操作如图。进栈操作如图4.8所示。所示。4.3 栈的链式表示与实现栈的链式表示与实现将元素将元素e入栈的算法实现如下。入栈的算法实现如下。int PushStack(LinkStack top,DataType e)LStackNode*p;/*定义指针定义指针p，指向新生成的结点，指向新生成的结点*/if(p=(LStackNode*)malloc(sizeof(LStackNode)=NULL)printf(“内存分配失败内存分配失败!”);exit(-1);p-data=e;/*将将e赋给赋给p指向的结点数据域指向的结点数据域*/p-next=top-next;
31、/*指针指针p指向头结点指向头结点*/top-next=p;/*栈顶结点的指针域指向新插入的结点栈顶结点的指针域指向新插入的结点*/return 1;4.3 栈的链式表示与实现栈的链式表示与实现（4）将栈顶元素出栈。先判断栈是否为空，如果栈为空，返回）将栈顶元素出栈。先判断栈是否为空，如果栈为空，返回0表示出表示出栈操作失败；否则，将栈顶元素出栈，并将栈顶元素值赋给栈操作失败；否则，将栈顶元素出栈，并将栈顶元素值赋给e，最后释，最后释放结点空间，返回放结点空间，返回1表示出栈操作成功。出栈操作如图表示出栈操作成功。出栈操作如图4.9所示。所示。4.3 栈的链式表示与实现栈的链式表示与实现将栈顶
32、元素出栈的算法实现如下。将栈顶元素出栈的算法实现如下。int PopStack(LinkStack top,DataType*e)LStackNode*p;p=top-next;if(!p)/*判断链栈是否为空判断链栈是否为空*/printf(“栈已空栈已空”);return 0;top-next=p-next;/*将栈顶结点与链表断开，即出栈将栈顶结点与链表断开，即出栈*/*e=p-data;/*将出栈元素赋值给将出栈元素赋值给e*/free(p);/*释放释放p指向的结点指向的结点*/return 1;（5）取栈顶元素。）取栈顶元素。int GetTop(LinkStack top,Dat
33、aType*e)/*取栈顶元素。取栈顶元素成功返回取栈顶元素。取栈顶元素成功返回1，否则返回，否则返回0*/LStackNode*p;p=top-next;/*指针指针p指向栈顶结点指向栈顶结点*/if(!p)/*如果栈为空如果栈为空*/printf(“栈已空栈已空”);return 0;*e=p-data;/*将将p指向的结点元素赋值给指向的结点元素赋值给e*/return 1;4.3 栈的链式表示与实现栈的链式表示与实现4.3 栈的链式表示与实现栈的链式表示与实现6）求栈的长度。）求栈的长度。int StackLength(LinkStack top)LStackNode*p;int co
34、unt=0;/*定义一个计数器，并初始化为定义一个计数器，并初始化为0*/p=top;/*p指向栈顶指针指向栈顶指针*/while(p-next!=NULL)/*如果栈中还有结点如果栈中还有结点*/p=p-next;/*依次访问栈中的结点依次访问栈中的结点*/count+;/*每次找到一个结点，计数器累加每次找到一个结点，计数器累加1*/return count;/*返回栈的长度返回栈的长度*/4.3 栈的链式表示与实现栈的链式表示与实现（7）销毁链栈。）销毁链栈。void DestroyStack(LinkStack top)LStackNode*p,*q;p=top;while(!p)/*
35、如果栈还有结点如果栈还有结点*/q=p;/*q就是要释放的结点就是要释放的结点*/p=p-next;/*p指向下一个结点，即下一次要释放的结点指向下一个结点，即下一次要释放的结点*/free(q);/*释放释放q指向的结点空间指向的结点空间*/（2）依据后缀表达式计算表达式的值。栈具有线性表的特点：除了第一个元素a1外，每一个元素有且只有一个直接前驱元素，除了最后一个元素an外，每一个元素有且只有一个直接后继元素。完整的求解迷宫程序如下。else/*否则*/（1）InitStack(&S)：初始化操作，建立一个空栈S。栈具有线性表的特点：除了第一个元素a1外，每一个元素有且只有一个直接前驱元素
36、，除了最后一个元素an外，每一个元素有且只有一个直接后继元素。return 0;if(S-top1=StackSize-1)/*右端的栈为空*/通常采用穷举法即从入口出发，顺某一个方向向前探索，若能走通，则继续往前走；（2）依据后缀表达式计算表达式的值。在使用顺序栈时，因为栈空间的大小难以准确估计，可能会出现有的栈还有空闲空间。S-top=0;/*将栈顶指针置为0*/return Ack(m-1,1);定义一个二维数组，数组的第一维用于存放本层参数n，第二维用于存放本层要返回的结果。（6）StackLength(S)：返回栈S的元素个数。break;利用上述规则，后缀表达式的6 7 1 3*+
37、10/+的值的运算过程如图4.S-top1+;/*修改栈顶指针，元素出栈操作*/LStackNode,*LinkStack;/*将元素e入共享栈。break;依据此原理，得到十进制数N转换为八进制的算法如下：4.3.3 链栈应用举例 【例【例4_3】利用链表模拟栈实现将十进制数】利用链表模拟栈实现将十进制数5678转换为对应的八转换为对应的八进制数。进制数。【分析】进制转换是计算机实现计算的基本问题。根据我们掌握的【分析】进制转换是计算机实现计算的基本问题。根据我们掌握的C语言知识，我们可以采用辗转相除法实现将十进制数转换为八进制语言知识，我们可以采用辗转相除法实现将十进制数转换为八进制数。将
38、数。将5678转换为八进制数的过程如图转换为八进制数的过程如图4.10所示。所示。4.3 栈的链式表示与实现栈的链式表示与实现 转换后的八进制数为转换后的八进制数为(13056)8。通过观察图。通过观察图4.10的转换过程的转换过程不难看出，每次不断利用被除数除以不难看出，每次不断利用被除数除以8得到商数后，记下余数，又得到商数后，记下余数，又将商数作为新的被除数继续除以将商数作为新的被除数继续除以8，直到商数为，直到商数为0为止，把得到的余为止，把得到的余数排列起来就是转换后的八进制数。依据此原理，得到十进制数数排列起来就是转换后的八进制数。依据此原理，得到十进制数N转换为八进制的算法如下：
39、转换为八进制的算法如下：（1）将）将N除以除以8，记下其余数；，记下其余数；（2）判断商是否为零，如果为零，结束程序；否则，将商送）判断商是否为零，如果为零，结束程序；否则，将商送N，转到（转到（1）继续执行。）继续执行。得到的位序正好与八进制数的位序相反，这恰好可利用栈的得到的位序正好与八进制数的位序相反，这恰好可利用栈的“后进先出后进先出”特性，先把得到的余数序列放入栈保存，最后依次出特性，先把得到的余数序列放入栈保存，最后依次出栈得到八进制数。栈得到八进制数。4.3 栈的链式表示与实现栈的链式表示与实现4.4.1 括号匹配 在计算机中，常见的括号有在计算机中，常见的括号有3种：花括号、方
40、括号和圆括号。种：花括号、方括号和圆括号。和和、和和、(和和)分别是匹配的括号，括号的嵌套顺序是任分别是匹配的括号，括号的嵌套顺序是任意的，即意的，即()和和()等为正确的格式，等为正确的格式，、()和和()等为等为不正确的格式。例如，有括号序列如图不正确的格式。例如，有括号序列如图4.12所示。所示。不难看出，括号匹配的处理过程符合栈的后进先出的特点。因此，不难看出，括号匹配的处理过程符合栈的后进先出的特点。因此，解决括号匹配问题可以利用栈来实现，设置一个栈，依次读入括号序列。解决括号匹配问题可以利用栈来实现，设置一个栈，依次读入括号序列。如果读入的是左括号，则进栈；若是右括号，则与栈顶的括
41、号进行比较，如果读入的是左括号，则进栈；若是右括号，则与栈顶的括号进行比较，是否匹配，如果匹配，则栈顶的括号出栈。如果栈不空，并且此时的括是否匹配，如果匹配，则栈顶的括号出栈。如果栈不空，并且此时的括号不匹配，则说明整个括号序列不匹配。当括号序列读入完毕，且栈为号不匹配，则说明整个括号序列不匹配。当括号序列读入完毕，且栈为空时，说明整个括号序列是匹配的。空时，说明整个括号序列是匹配的。4.4 栈的典型应用栈的典型应用 【例【例4_4】任意给定一个数学表达式如】任意给定一个数学表达式如5*(9-2)-15-(8-3)/2+3*(6-4)，试设计一个算法判断表达式的括号是否匹配。，试设计一个算法判
42、断表达式的括号是否匹配。【分析】检验括号是否匹配可以设置一个栈，每读入一个括号，如果【分析】检验括号是否匹配可以设置一个栈，每读入一个括号，如果是左括号，则直接进栈。是左括号，则直接进栈。（1）如果读入的是右括号且与当前栈顶的左括号是同类型的，说明）如果读入的是右括号且与当前栈顶的左括号是同类型的，说明这一对括号是匹配的，则将栈顶的左括号出栈，否则是不匹配。这一对括号是匹配的，则将栈顶的左括号出栈，否则是不匹配。且栈已经为空，说明缺少左括号，该括号序列不匹配。且栈已经为空，说明缺少左括号，该括号序列不匹配。（2）如果输入序列已经读完，而栈中仍然有等待匹配的左括号，说）如果输入序列已经读完，而栈
43、中仍然有等待匹配的左括号，说明缺少右括号，该括号序列不匹配。明缺少右括号，该括号序列不匹配。（3）如果读入是数字字符，则不进行处理，直接读入下一个字符。）如果读入是数字字符，则不进行处理，直接读入下一个字符。4.4 栈的典型应用栈的典型应用 4.4.2 求算术表达式的值 表达式求值是程序设计编译中的基本问题，它的实现是栈应用表达式求值是程序设计编译中的基本问题，它的实现是栈应用的一个典型例子。本节给大家介绍一种简单并广为使用的算法，被的一个典型例子。本节给大家介绍一种简单并广为使用的算法，被称之为算符优先法。计算机编译系统利用栈的称之为算符优先法。计算机编译系统利用栈的“后进先出后进先出”特性
44、把特性把人们便于理解的表达式翻译成计算机能够正确理解的表示序列。人们便于理解的表达式翻译成计算机能够正确理解的表示序列。一个算术表达式是由操作数、运算符和分界符组成。为了简化一个算术表达式是由操作数、运算符和分界符组成。为了简化问题，我们假设算术运算符仅由加、减、乘、除四种运算符和左、问题，我们假设算术运算符仅由加、减、乘、除四种运算符和左、右圆括号组成。右圆括号组成。4.4 栈的典型应用栈的典型应用 例如，一个算术表达式为例如，一个算术表达式为 6+(7-1)*3+10/2 这种算术表达式中的运算符总是出现在两个操作数之间，这种这种算术表达式中的运算符总是出现在两个操作数之间，这种算术表达式
45、被称为中缀表达式。计算机编译系统在计算一个算算术表达式被称为中缀表达式。计算机编译系统在计算一个算术表达式之前，要将中缀表达式转换为后缀表达式，然后对后术表达式之前，要将中缀表达式转换为后缀表达式，然后对后缀表达式进行计算。后缀表达式就是算术运算符出现在操作数缀表达式进行计算。后缀表达式就是算术运算符出现在操作数之后，并且不含括号。之后，并且不含括号。计算机在求算术表达式的值时分为两个步骤：计算机在求算术表达式的值时分为两个步骤：（1）将中缀表达式转换为后缀表达式；）将中缀表达式转换为后缀表达式；（2）依据后缀表达式计算表达式的值。）依据后缀表达式计算表达式的值。4.4 栈的典型应用栈的典型应
46、用 1将中缀表达式转换为后缀表达式将中缀表达式转换为后缀表达式 要将一个算术表达式的中缀形式转化为相应的后缀形式，首先了解下要将一个算术表达式的中缀形式转化为相应的后缀形式，首先了解下算术四则运算的规则。算术四则运算的规则是：算术四则运算的规则。算术四则运算的规则是：（1）先乘除，后加减；）先乘除，后加减；（3）同级别的运算从左到右进行计算；）同级别的运算从左到右进行计算；（2）先括号内，后括号外。）先括号内，后括号外。上面的算术表达式转换为后缀表达式为：上面的算术表达式转换为后缀表达式为：6 7 1 3*+10 2/+4.4 栈的典型应用栈的典型应用elseint PushStack(SSe
47、qStack*S,DataType e,int flag)int count=0;/*定义一个计数器，并初始化为0*/void DestroyStack(LinkStack top)（3）将控制转到调用函数的返回地址处。栈具有线性表的特点：除了第一个元素a1外，每一个元素有且只有一个直接前驱元素，除了最后一个元素an外，每一个元素有且只有一个直接后继元素。S-stackS-top1=e;/*元素进栈*/return 0;/*返回0*/栈是一种只允许在线性表的一端进行插入和删除操作的线性表。依据此原理，得到十进制数N转换为八进制的算法如下：取栈顶元素成功返回1，否则返回0*/如果兔子在出生两个月
48、后，就有繁殖能力，一对兔子每个月能生出一对兔子，假设所有兔子都不死，那么一年以后可以繁殖多少对兔子呢？（2）判断链栈是否为空。（1）将所有参数和返回地址传递给被调用函数保存；/*将塔座A上按照从小到大自上而下编号为1到n的那个圆盘按照规则搬到塔座C上，B可以作为辅助塔座*/if(S-top0=S-top1)/*如果共享栈已满*/case 2:/*当flag为2，表示将元素要进右端的栈*/S-top=0;/*将栈顶指针置为0*/（5）判断栈是否为空。例如，当n=4时，代码执行过程如图4.当表中没有元素时，称为空栈。return 1;/*返回1，进栈成功*/转换后的后缀表达式具有以下两个特点：转换
49、后的后缀表达式具有以下两个特点：（1）后缀表达式与中缀表达式的操作数出现顺序相同，只是运）后缀表达式与中缀表达式的操作数出现顺序相同，只是运算符先后顺序改变了；算符先后顺序改变了；（2）后缀表达式不出现括号。）后缀表达式不出现括号。正因为后缀表达式的以上特点，所以编译系统不必考虑运算符正因为后缀表达式的以上特点，所以编译系统不必考虑运算符的优先关系。仅需要从左到右依次扫描后缀表达式的各个字符，的优先关系。仅需要从左到右依次扫描后缀表达式的各个字符，遇到运算符时，直接对运算符前面的两个操作数进行运算即可。遇到运算符时，直接对运算符前面的两个操作数进行运算即可。4.4 栈的典型应用栈的典型应用 如
50、何将中缀表达式转换为后缀表达式呢？如何将中缀表达式转换为后缀表达式呢？我们约定我们约定#作为后缀表达式的结束标志，假设作为后缀表达式的结束标志，假设1为栈顶运算符，为栈顶运算符，2为当前扫为当前扫描的运算符。则中缀表达式转换为后缀表达式的算法描述如下：描的运算符。则中缀表达式转换为后缀表达式的算法描述如下：（1）初始化栈，并将）初始化栈，并将#入栈；入栈；（2）若当前读入的字符是操作数，则将该操作数输出，并读入下一字符；）若当前读入的字符是操作数，则将该操作数输出，并读入下一字符；（3）若当前字符是运算符，记作）若当前字符是运算符，记作2，则将，则将2与栈顶的运算符与栈顶的运算符1比较。若比较
