数据结构(C语言版)-栈和队列

第3章限定性线性表——栈和队列第3章限定性线性表—栈和队列3.1栈3.2栈的应用举例3.3栈与递归的实现3.4队列第3章限定性线性表——栈和队列3.1栈3.1.1栈的定义栈作为一种限定性线性表，是将线性表的插入和删除运算限制为仅在表尾进行，通常将表中允许进行插入、删除操作的一端称为栈顶(Top)，因此栈顶的当前位置是动态变化的，它由一个称为栈顶指针的位置指示器指示。同时表的另一端被称为栈底(Bottom)。当栈中没有元素时称为空栈。栈的插入操作被形象地称为进栈或入栈，删除操作称为出栈或退栈。第3章限定性线性表——栈和队列设S=(a1,a2,…,an)表示栈，则a1为栈底元素，an为栈顶元素。栈是一种后进先出（LastInFirstOut）的线性表（简称LIFO结构）。图3.1栈an…a2a1进栈出栈栈顶栈底进栈出栈(a)栈的示意图(b)铁路调序栈的表示第3章限定性线性表——栈和队列栈只能对栈顶元素进行插入和删除操作。例：若输入A，B，C，D。可能的输出序列为D，A，C，B（错）、B，A，C，D（对）、D，C，A，B（错）、B，C，A，D（对）、A，C，B，D（对）第3章限定性线性表——栈和队列ADTStack{数据元素：可以是任意类型的数据，但必须属于同一个数据对象。数据关系：栈中数据元素之间是线性关系。基本操作：（1）InitStack(&S)初始条件：S为未初始化的栈。操作结果：将S初始化为空栈。（2）ClearStack(&S)初始条件：栈S已经存在。操作结果：将栈S置成空栈。第3章限定性线性表——栈和队列（3）StackEmpty(S)初始条件：栈S已经存在。操作结果：若S为空栈，则函数值为TRUE，否则FALSE（4）Push(&S,e)初始条件：栈S已经存在。操作结果：在S的顶部插入(亦称压入)元素e；第3章限定性线性表——栈和队列（5）Pop(&S,&e)初始条件：栈S已经存在。操作结果：删除(亦称弹出)栈S的顶部元素，并用e带回该值。（6）GetTop(S,&e)初始条件：栈S已经存在。操作结果：取栈S的顶部元素。与Pop(&S,e)不同之处在于GetTop(S,&e)不改变栈顶的位置。第3章限定性线性表——栈和队列3.1.2栈的表示和实现1.顺序栈顺序栈是用顺序存储结构实现的栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时由于栈的操作的特殊性，还必须附设一个位置指针top（栈顶指针）来动态地指示栈顶元素在顺序栈中的位置。通常以top=0表示空栈。顺序栈的存储结构可以用C语言中的一维数组来表示。栈的顺序存储结构定义如下：第3章限定性线性表——栈和队列＃defineTRUE1＃defineFALSE0typedefstruct{SElemType*base;SElemType*top;intstacksize;//栈可使用的最大容量}SqStack;按初始分配量进行第一次存储分配，base为栈底指针，始终指向栈底。top为栈顶指针，初值指向栈底，每插入一个元素，top增1；每删除一个元素，top减1，top始终在栈顶元素的下一个位置上。第3章限定性线性表——栈和队列图3.2顺序栈中的进栈和出栈43210432104321043210第3章限定性线性表——栈和队列顺序栈基本操作的实现如下:(1)初始化。StatusInitStack(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;returnOK;}第3章限定性线性表——栈和队列(2)取栈顶元素StatusGetTop(SqStackS,SElemType&e){if(S.top==S.base)returnERROR;e=*(S.top-1);returnOK;}第3章限定性线性表——栈和队列(3)入栈。StatusPush(SqStack&S,SElemTypee){if(S.top-S.base=S.stacksize){S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));if(!S.base)exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;returnOK;}第3章限定性线性表——栈和队列(4)出栈StatusPop(SqStack&S,SelemType&e){if(S.top==S.base)returnERROR;e=*--S.top;returnOK;}第3章限定性线性表——栈和队列在栈的共享技术中最常用的是两个栈的共享技术：它主要利用了栈“栈底位置不变，而栈顶位置动态变化”的特性。首先为两个栈申请一个共享的一维数组空间S[M]，将两个栈的栈底分别放在一维数组的两端，分别是0、M-1。由于两个栈顶动态变化，这样可以形成互补，使得每个栈可用的最大空间与实际使用的需求有关。由此可见，两栈共享比两个栈分别申请M/2的空间利用率高。第3章限定性线性表——栈和队列图3.3共享栈Stack:0M－1top[0]top[1]第3章限定性线性表——栈和队列2.链栈图3.4链栈示意图链式栈无栈满问题，空间可扩充插入与删除仅在栈顶处执行链式栈的栈顶在链头适合于多栈操作第3章限定性线性表——栈和队列3.2栈的应用举例1.假设要将十进制数N转换为d进制数，一个简单的转换算法是重复下述两步，直到N等于零：X=Nmodd(其中mod为求余运算)N=Ndivd(其中div为整除运算)第3章限定性线性表——栈和队列如(1348)10=(2504)8NN/8N%8134816841682102125202第3章限定性线性表——栈和队列voidconversion(){InitStack(S);scanf(“%d”,&N);while(N){Push(s,N%8);N=N/8;}while(!StackEmpty(s)){Pop(S,e);printf(“%d”,e);}}第3章限定性线性表——栈和队列2.括号匹配问题假设表达式中包含三种括号：圆括号、方括号和花括号，它们可互相嵌套，如([{}]([]))或({([][()])})等均为正确的格式，而{[]})}或{[()]或([]}均为不正确的格式。在检验算法中可设置一个栈，每读入一个括号，若是左括号，则直接入栈，等待相匹配的同类右括号；若读入的是右括号，且与当前栈顶的左括号同类型，则二者匹配，将栈顶的左括号出栈，否则属于不合法的情况。另外，如果输入序列已读尽，而栈中仍有等待匹配的左括号，或者读入了一个右括号，而栈中已无等待匹配的左括号，均属不合法的情况。当输入序列和栈同时变为空时，说明所有括号完全匹配。第3章限定性线性表——栈和队列3.表达式求值表达式求值是高级语言编译中的一个基本问题，是栈的典型应用实例。任何一个表达式都是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。操作数既可以是常数，也可以是被说明为变量或常量的标识符；运算符可以分为算术运算符、关系运算符和逻辑运算符三类；基本界限符有左右括号和表达式结束符等。第3章限定性线性表——栈和队列1）表达式计算程序设计语言中都有计算表达式的问题，这是语言编译中的典型问题。(1)表达式形式：由运算对象、运算符及必要的表达式括号组成；(2)表达式运算：运算时要有一个正确的运算形式顺序。由于某些运算符可能具有比别的运算符更高的优先级，因此表达式不可能严格的从左到右进行运算，见图3.5。第3章限定性线性表——栈和队列图3.5表达式运算及运算符优先级第3章限定性线性表——栈和队列图3.6无括号算术表达式的处理过程置空栈OVS、OPTR读字符WW是操作符OPTR栈空W优先级≤OPTR栈顶优先级取OVS顶、次顶和OPTR顶，形成运算结果T(i),然后退OVS顶、次顶和OPTR顶，将T(i)置入OVS栈顶进OVS进OPTR栈W＝'#'结束NYYYNYNN第3章限定性线性表——栈和队列2）(1)规定优先级表。(2)设置两个栈：OVS(运算数栈)和OPTR(运算符栈)。(3)自左向右扫描，遇操作数进OVS，遇操作符则与OPTR栈顶优先数比较：当前操作符OPTR栈顶,当前操作符进OPTR栈；当前操作符≤OPTR栈顶，OVS栈顶、次顶和OPTR栈顶，退栈形成运算T(i)，T(i)进OVS栈。例：实现A/B↑C+D*E＃的运算过程时栈区变化情况如图3.7所示。第3章限定性线性表——栈和队列图3.7A/B↑C+D*E运算过程的栈区变化情况示意图CBAOVS↑/OPTR'＋'＜OPTR'↑'生成B↑C，运算结果T(1)T(1)AOVS/OPTR'＋'＜OPTR'/'生成A/T(1),运算结果T(2)T(2)↑/OPTR为空，'＋'进栈DT(2)＋右边界'#'＜OPTR'*'生成D*E，运算结果T(3)T(3)T(2)＋生成T(3)＋T(2)，得到T(4)T(4)E*右边界'#'＜OPTR'＋'第3章限定性线性表——栈和队列3）假设操作数是整型常数，运算符只含加、减、乘、除等四种运算符，界限符有左右括号和表达式起始、结束符“＃”，如：＃（7+15）*（23-28/4）＃。引入表达式起始、结束符是为了方便。要对一个简单的算术表达式求值，首先要了解算术四则运算的规则，即：(1)从左算到右；(2)先乘除，后加减；(3)先括号内，后括号外。第3章限定性线性表——栈和队列运算符和界限符可统称为算符，它们构成的集合命名为OPS。根据上述三条运算规则，在运算过程中，任意两个前后相继出现的算符θ1和θ2之间的优先关系必为下面三种关系之一：θ1θ2，θ1的优先权低于θ2。θ1=θ2，θ1的优先权等于θ2。θ1θ2，θ1的优先权高于θ2。第3章限定性线性表——栈和队列表3-1算符之间的优先关系第3章限定性线性表——栈和队列实现算符优先算法时需要使用两个工作栈：一个称作operator，用以存放运算符；另一个称作operand，用以存放操作数或运算的中间结果。首先初始化操作数栈operand和运算符栈operator，并将表达式起始符“＃”压入运算符栈；依次读入表达式中的每个字符，若是操作数则直接进入操作数栈operand，若是运算符，则与运算符栈operator的栈顶运算符进行优先权比较，并做如下处理：第3章限定性线性表——栈和队列(1)若栈顶运算符的优先级低于刚读入的运算符，则让刚读入的运算符进operator栈；(2)若栈顶运算符的优先级高于刚读入的运算符，则将栈顶运算符退栈，送入θ，同时将操作数栈operand退栈两次，得到两个操作数a、b，对a、b进行θ运算后，将运算结果作为中间结果推入operand栈；(3)若栈顶运算符的优先级与刚读入的运算符的优先级相同，说明左右括号相遇，只需将栈顶运算符（左括号）退栈即可。第3章限定性线性表——栈和队列3.3栈与递归的实现栈非常重要的一个应用是在程序设计语言中用来实现递归。递归是指在定义自身的同时又出现了对自身的调用。如果一个函数在其定义体内直接调用自己，则称其为直接递归函数；如果一个函数经过一系列的中间调用语句，通过其它函数间接调用自己，则称其为间接递归函数。第3章限定性线性表——栈和队列1.递归特性问题1)例如，很多数学函数是递归定义的，如二阶Fibonacci数列：第3章限定性线性表——栈和队列第3章限定性线性表——栈和队列递归过程的实现一个函数调用另一个函数时，在运行被调用函数之前，系统做的工作有：(1)保留本层参数与返回地址（将所有的实在参数、返回地址等信息传递给被调用函数保存）；(2)给下层参数赋值（为被调用函数的局部变量分配存储区