1、4.1 4.1 栈的表示与实现栈的表示与实现栈是作为一种限定性线性表，只允许在表的一端进行栈是作为一种限定性线性表，只允许在表的一端进行插入和删除操作。本节主要介绍栈的定义和栈的抽象数据类插入和删除操作。本节主要介绍栈的定义和栈的抽象数据类型。型。4.1.1 4.1.1 栈的定义栈的定义栈，也称为堆栈，它是一种特殊的线性表，只允许在栈，也称为堆栈，它是一种特殊的线性表，只允许在表的一端进行插入和删除操作。栈顶是动态变化的，它由一表的一端进行插入和删除操作。栈顶是动态变化的，它由一个称为栈顶指针（个称为栈顶指针（top）的变量指示。当表中没有元素时，）的变量指示。当表中没有元素时，称为空栈。称为
2、空栈。栈的插入操作称为入栈或进栈，删除操作称为出栈或栈的插入操作称为入栈或进栈，删除操作称为出栈或退栈。退栈。4.1.1 4.1.1 栈的定义栈的定义4.1.2 4.1.2 栈的抽象数据类型栈的抽象数据类型1数据对象集合数据对象集合2基本操作集合基本操作集合4.2 4.2 栈的顺序表示与实现栈的顺序表示与实现与线性表一样，栈也有两种存储表示：顺序存储和链与线性表一样，栈也有两种存储表示：顺序存储和链式存储。本节的主要学习内容包括栈的顺序存储结构及顺序式存储。本节的主要学习内容包括栈的顺序存储结构及顺序存储结构下的操作实现。存储结构下的操作实现。4.2.1 4.2.1 栈的顺序存储结构栈的顺序存
3、储结构采用顺序存储结构的栈称为顺序栈。顺序栈利用一组采用顺序存储结构的栈称为顺序栈。顺序栈利用一组连续的存储单元存放栈中的元素，存放顺序依次从栈底到栈连续的存储单元存放栈中的元素，存放顺序依次从栈底到栈顶。由于栈中元素之间的存放地址的连续性，在顶。由于栈中元素之间的存放地址的连续性，在C语言中，语言中，同样采用数组实现栈的顺序存储。同样采用数组实现栈的顺序存储。#define StackSize 100typedef struct DataType stackStackSize;int top;SeqStack;4.2.2 4.2.2 顺序栈的基本运算顺序栈的基本运算在顺序存储结构中，栈的基本
4、运算如下。以下算法的在顺序存储结构中，栈的基本运算如下。以下算法的实现保存在文件实现保存在文件“SeqStack.h”中。中。（1）栈的初始化操作。）栈的初始化操作。void InitStack(SeqStack*S)/*将栈初始化为空栈只需要把栈顶指针将栈初始化为空栈只需要把栈顶指针top置为置为0*/S-top=0;/*把栈顶指针置为把栈顶指针置为0*/4.2.2 4.2.2 顺序栈的基本运算顺序栈的基本运算（2）判断栈是否为空。）判断栈是否为空。int StackEmpty(SeqStack S)/*判断栈是否为空，栈为空返回判断栈是否为空，栈为空返回1，否则返回，否则返回0*/if(S
5、.top=0)/*判断栈顶指针判断栈顶指针top是否为是否为0*/return 1;/*当栈为空时，返回当栈为空时，返回1；否则返回；否则返回0*/else return 0;4.2.2 4.2.2 顺序栈的基本运算顺序栈的基本运算（3）取栈顶元素操作。）取栈顶元素操作。int GetTop(SeqStack S,DataType*e)if(S.toptop=StackSize)printf(“栈已满，不能进栈！栈已满，不能进栈！n”);return 0;else S-stackS-top=e;S-top+;return 1;4.2.2 4.2.2 顺序栈的基本运算顺序栈的基本运算（5）出栈操
6、作。）出栈操作。int PopStack(SeqStack*S,DataType*e)if(S-top=0)printf(“栈已经没有元素，不能出栈栈已经没有元素，不能出栈!n”);return 0;else S-top-;*e=S-stackS-top;return 1;4.2.2 4.2.2 顺序栈的基本运算顺序栈的基本运算（6）返回栈的长度操作。）返回栈的长度操作。int StackLength(SeqStack S)return S.top;4.2.2 4.2.2 顺序栈的基本运算顺序栈的基本运算（7）清空栈的操作。）清空栈的操作。void ClearStack(SeqStack*S)
7、S-top=0;4.2.3 4.2.3 共享栈的问题共享栈的问题栈的应用非常广泛，经常会出现一个程序需要同时使栈的应用非常广泛，经常会出现一个程序需要同时使用多个栈的情况。使用顺序栈会因为栈空间的大小难以准确用多个栈的情况。使用顺序栈会因为栈空间的大小难以准确估计，从而造成有的栈溢出，有的栈空间还有空闲。为了解估计，从而造成有的栈溢出，有的栈空间还有空闲。为了解决这个问题，可以让多个栈共享一个足够大的连续存储空间决这个问题，可以让多个栈共享一个足够大的连续存储空间，通过利用栈的动态特性使多个栈存储空间能够互相补充，通过利用栈的动态特性使多个栈存储空间能够互相补充，存储空间得到有效利用，这就是栈
8、的共享存储空间得到有效利用，这就是栈的共享.4.2.3 4.2.3 共享栈的问题共享栈的问题两个共享栈的数据结构类型定义两个共享栈的数据结构类型定义 typedef struct DataType stackStackSize;int top2;SSeqStack;4.2.3 4.2.3 共享栈的问题共享栈的问题（1）初始化操作。）初始化操作。void InitStack(SSeqStack*S)S-top0=0;S-top1=StackSize-1;4.2.3 4.2.3 共享栈的问题共享栈的问题（2）进栈操作。）进栈操作。int PushStack(SSeqStack*S,DataType
9、 e,int flag)if(S-top0=S-top1)return 0;switch(flag)case 0:S-stackS-top0=e;S-top0+;break;case 1:S-stackS-top1=e;S-top1-;break;default:return 0;return 1;4.2.3 4.2.3 共享栈的问题共享栈的问题（3）出栈操作。）出栈操作。int PopStack(SSeqStack*S,DataType*e,int flag)switch(flag)case 0:if(S-top0=0)return 0;S-top0-;*e=S-stackS-top0;br
10、eak;case 1:if(S-top1=StackSize-1)return 0;S-top1+;*e=S-stackS-top1;break;default:return 0;return 1;4.3 4.3 栈的应用举例栈的应用举例上一节已经学习了栈的顺序存储结构及栈的实现。本上一节已经学习了栈的顺序存储结构及栈的实现。本节通过实例来学习栈的基本操作的用法。节通过实例来学习栈的基本操作的用法。例例4_1 将元素将元素a、b、c、d、e依次进栈，然后将依次进栈，然后将d和和e出栈，再将出栈，再将f和和g进栈，最后将元素全部出栈，并将元素按照进栈，最后将元素全部出栈，并将元素按照出栈次序输出
11、。出栈次序输出。4.3 4.3 栈的应用举例栈的应用举例例例4_2 设有两个栈设有两个栈S1和和S2都采用顺序栈的方式存储，都采用顺序栈的方式存储，并且共享一个存储区。为了尽可能利用存储空间，减少溢出并且共享一个存储区。为了尽可能利用存储空间，减少溢出的可能，采用栈顶相向，迎面增长的方式，试设计的可能，采用栈顶相向，迎面增长的方式，试设计S1和和S2有关入栈和出栈算法。有关入栈和出栈算法。4.4 4.4 栈的链式表示与实现栈的链式表示与实现在顺序栈中，由于顺序存储结构需要事先静态分配，在顺序栈中，由于顺序存储结构需要事先静态分配，而存储规模往往又难以确定，如果栈空间分配过小，可能会而存储规模往
12、往又难以确定，如果栈空间分配过小，可能会造成溢出；如果栈空间分配过大，又造成存储空间浪费。因造成溢出；如果栈空间分配过大，又造成存储空间浪费。因此，为了克服顺序存储的缺点，采用链式存储结构表示栈。此，为了克服顺序存储的缺点，采用链式存储结构表示栈。本节主要学习内容包括栈的存储结构及链栈的基本运算。本节主要学习内容包括栈的存储结构及链栈的基本运算。4.4.1 4.4.1 栈的存储结构栈的存储结构采用链式存储方式的栈称为链栈或链式栈。链栈由一个个结点采用链式存储方式的栈称为链栈或链式栈。链栈由一个个结点构成，结点包含数据域和指针域两部分。在链栈中，利用每一个结构成，结点包含数据域和指针域两部分。在
13、链栈中，利用每一个结点的数据域存储栈中的每一个元素，利用指针域表示元素之间的关点的数据域存储栈中的每一个元素，利用指针域表示元素之间的关系。插入和删除元素的一端称为栈顶，栈顶由栈顶指针系。插入和删除元素的一端称为栈顶，栈顶由栈顶指针top指示。指示。链栈结点的类型定义如下：链栈结点的类型定义如下：typedef struct node DataType data;struct node*next;LStackNode,*LinkStack;4.4.2 4.4.2 栈的基本运算栈的基本运算链栈的基本运算包括链栈的初始化、进栈、出栈、取链栈的基本运算包括链栈的初始化、进栈、出栈、取栈顶元素等。带头
14、结点的链栈的基本运算具体实现如下。栈顶元素等。带头结点的链栈的基本运算具体实现如下。4.4.2 4.4.2 栈的基本运算栈的基本运算（1）链栈的初始化操作。）链栈的初始化操作。void InitStack(LinkStack*top)if(*top=(LinkStack)malloc(sizeof(LStackNode)=NULL)exit(-1);(*top)-next=NULL;4.4.2 4.4.2 栈的基本运算栈的基本运算（2）判断链栈是否为空。）判断链栈是否为空。int StackEmpty(LinkStack top)if(top-next=NULL)return 1;else r
15、eturn 0;4.4.2 4.4.2 栈的基本运算栈的基本运算（3）进栈操作。）进栈操作。int PushStack(LinkStack top,DataType e)LStackNode*p;p=(LStackNode*)malloc(sizeof(LStackNode)p-data=e;p-next=top-next;top-next=p;return 1;4.4.2 4.4.2 栈的基本运算栈的基本运算（4）出栈操作。）出栈操作。int PopStack(LinkStack top,DataType*e)LStackNode*p;p=top-next;if(!p)printf(“栈已空
16、栈已空”);return 0;top-next=p-next;*e=p-data;free(p);return 1;4.4.2 4.4.2 栈的基本运算栈的基本运算（5）取栈顶元素操作。）取栈顶元素操作。void GetTop(LinkStack top,DataType*e)LStackNode*p;p=top-next;if(!p)printf(“栈已空栈已空”);return 0;*e=p-data;return 1;4.4.2 4.4.2 栈的基本运算栈的基本运算（6）求表长操作。）求表长操作。int StackLength(LinkStack top)LStackNode*p;int
17、 count=0;p=top;while(p-next!=NULL)p=p-next;count+;return count;4.4.2 4.4.2 栈的基本运算栈的基本运算（7）销毁链栈操作。）销毁链栈操作。void DestroyStack(LinkStack top)LStackNode*p,*q;p=top;while(!p)q=p;p=p-next;free(q);4.4.3 4.4.3 链栈的应用链栈的应用下面通过一个实例说明链栈基本算法的应用。下面通过一个实例说明链栈基本算法的应用。例例4_3 利用链栈的基本运算，通过输入将字符进栈，利用链栈的基本运算，通过输入将字符进栈，然后输
18、出其出栈序列。然后输出其出栈序列。4.5 4.5 栈的应用举例栈的应用举例由于栈结构后进先出的特性，使它成为一种重要的数由于栈结构后进先出的特性，使它成为一种重要的数据结构，它在计算机中的应用也非常广泛。在程序的编译和据结构，它在计算机中的应用也非常广泛。在程序的编译和运行过程中，需要利用栈对程序的语法进行检查，如括号的运行过程中，需要利用栈对程序的语法进行检查，如括号的配对、表达式求值和函数的递归调用。本节通过几个例子来配对、表达式求值和函数的递归调用。本节通过几个例子来学习栈的具体应用。学习栈的具体应用。4.5.1 4.5.1 数制转换数制转换如果将十进制数如果将十进制数N转换为转换为x进
19、制数，需要用辗转相除法进制数，需要用辗转相除法执行以下步骤：执行以下步骤：（1）将）将N除以除以x，取其余数；，取其余数；（2）判断商是否为零，如果为零，结束程序；否则，）判断商是否为零，如果为零，结束程序；否则，将商送将商送N，转（，转（1）继续执行。）继续执行。4.5.2 4.5.2 括号配对括号配对假设表达式中允许包含三种类型的括号：花括号假设表达式中允许包含三种类型的括号：花括号、方括号、方括号和圆括号和圆括号()。其嵌套的顺序任意，即。其嵌套的顺序任意，即()和和()均为正确的格式，均为正确的格式，()、()和和()均为不正确的格式均为不正确的格式。4.5.3 4.5.3 行编辑程序
20、行编辑程序一个简单的行编辑程序的功能是：将用户输入的字符一个简单的行编辑程序的功能是：将用户输入的字符序列存入数据区，由于用户进行输入时，有可能会出现错误序列存入数据区，由于用户进行输入时，有可能会出现错误。因此，如果在编辑程序中，每接受一个字符，即存入数据。因此，如果在编辑程序中，每接受一个字符，即存入数据区的做法显然是不合适的。一个比较好的做法是，设立一个区的做法显然是不合适的。一个比较好的做法是，设立一个输入缓冲区，用来接受用户输入的一行字符，然后输入缓冲区，用来接受用户输入的一行字符，然后逐行存入逐行存入数据区。如果用户输入出现错误，在发现输入有误时及时更数据区。如果用户输入出现错误，
21、在发现输入有误时及时更正。正。4.6 4.6 栈与递归的实现栈与递归的实现栈的后进先出的思想还应用在函数的递归调用中。本栈的后进先出的思想还应用在函数的递归调用中。本节主要说明栈与递归调用的关系、递归利用栈的实现过程、节主要说明栈与递归调用的关系、递归利用栈的实现过程、递归与非递归的转换。递归与非递归的转换。4.6.1 4.6.1 递归递归1递归函数递归函数2递归调用过程递归调用过程4.6.1 4.6.1 递归递归int fact(int n)if(n=0)return 1;else return n*fact(n-1);4.6.1 4.6.1 递归递归int Ack(int m,int n)
22、if(m=0)return n+1;else if(n=0)return Ack(m-1,1);else return Ack(m-1,Ack(m,n-1);4.6.1 4.6.1 递归递归4.6.1 4.6.1 递归递归4.6.1 4.6.1 递归递归4.6.1 4.6.1 递归递归void Hanoi(int n,char x,char y,char z)/*将塔座将塔座X上按照从小到大自上而下编号为上按照从小到大自上而下编号为1到到n的那个圆盘的那个圆盘按照规则搬到塔座按照规则搬到塔座Z上，上，Y可以作为辅助塔座可以作为辅助塔座*/if(n=1)Move(x,1,z);/*将编号为将编号
23、为1的圆盘从的圆盘从X移动到移动到Z*/else Hanoi(n-1,x,z,y);/*将编号为将编号为1到到n-1的圆盘从的圆盘从X移动移动到到Y，Z作为辅助塔座作为辅助塔座*/Move(x,n,z);/*将编号为将编号为n的圆盘从的圆盘从X移动到移动到Z*/Hanoi(n-1,y,x,z);/*将编号为将编号为1到到n-1的圆盘从的圆盘从Y移动移动到到Z，X作为辅助塔座作为辅助塔座*/4.6.2 4.6.2 消除递归消除递归用递归编制的算法结构清晰、易读，容易实现并且递用递归编制的算法结构清晰、易读，容易实现并且递归算法的正确性很容易得到证明。但是，递归算法的执行效归算法的正确性很容易得到
24、证明。但是，递归算法的执行效率比较低，因为递归需要反复入栈，时间和空间开销比较大率比较低，因为递归需要反复入栈，时间和空间开销比较大。递归的算法也完全可以转换为非递归实现，这就是递递归的算法也完全可以转换为非递归实现，这就是递归的消除。消除递归方法有两种，一种是对于简单的递归可归的消除。消除递归方法有两种，一种是对于简单的递归可以直接用迭代，通过循环结构就可以消除；另一种方法是利以直接用迭代，通过循环结构就可以消除；另一种方法是利用栈的方式实现。用栈的方式实现。4.6.2 4.6.2 消除递归消除递归例例4_6 编写编写n的阶乘的递归算法与利用栈结构的非递归的阶乘的递归算法与利用栈结构的非递归
25、实现算法。实现算法。int fact(int n)int f,i;f=1;for(i=1;i=n;i+)f=f*i;return f;4.6.2 4.6.2 消除递归消除递归4.7 4.7 栈的综合应用举例栈的综合应用举例表达式计算是编译系统中的基本问题，是栈的一个典表达式计算是编译系统中的基本问题，是栈的一个典型应用。在编译系统中，需要把人们便于理解的表达式翻译型应用。在编译系统中，需要把人们便于理解的表达式翻译成计算机能够正确理解的表示序列。这就需要利用栈实现表成计算机能够正确理解的表示序列。这就需要利用栈实现表达式的转换，本节的主要学习内容是表达式的转换及计算。达式的转换，本节的主要学习
26、内容是表达式的转换及计算。4.7.1 4.7.1 表达式的转换与计算表达式的转换与计算1将中缀表达式转换为后缀表达式将中缀表达式转换为后缀表达式2后缀表达式的计算后缀表达式的计算4.7.2 4.7.2 表达式的运算举例表达式的运算举例下面以一个例子来说明算术表达式中缀形式转化为后下面以一个例子来说明算术表达式中缀形式转化为后缀形式的过程，并对后缀表达式进行运算。缀形式的过程，并对后缀表达式进行运算。例例4_8 利用栈将中缀表达式（利用栈将中缀表达式（5*（12-3）+4）/2转换转换为后缀表达式，并将得到的后缀表达式求值。为后缀表达式，并将得到的后缀表达式求值。4.7.2 4.7.2 表达式的
27、运算举例表达式的运算举例4.7.2 4.7.2 表达式的运算举例表达式的运算举例精品课件精品课件！精品课件精品课件！4.8 4.8 小结小结本章主要介绍了一种特殊的线性表本章主要介绍了一种特殊的线性表栈。栈。栈是一种只允许在线性表的一端进行插入和删除操作栈是一种只允许在线性表的一端进行插入和删除操作的线性表。的线性表。栈也有两种存储方式：顺序存储和链式存储。栈也有两种存储方式：顺序存储和链式存储。栈的特点是后进先出，使栈在程序设计、编译处理的栈的特点是后进先出，使栈在程序设计、编译处理的过程中得到有效的利用。过程中得到有效的利用。在程序设计中，递归的实现也是系统借助栈的特性实在程序设计中，递归的实现也是系统借助栈的特性实现递归调用过程。现递归调用过程。表达式求值是编译过程中的一个基本问题，是栈的一表达式求值是编译过程中的一个基本问题，是栈的一个典型应用。在表达式的转换和表达式求值的过程中，都需个典型应用。在表达式的转换和表达式求值的过程中，都需要借助栈实现。要借助栈实现。
