《数据结构(C语言)》课件—03栈和队列.ppt

第第3章章 栈和队列栈和队列 栈是一种操作受限的线性表栈具有线性表的结构特点，即每栈是一种操作受限的线性表栈具有线性表的结构特点，即每一个元素只有一个前驱元素和后继元素（除了第一个元素和最后一一个元素只有一个前驱元素和后继元素（除了第一个元素和最后一个元素外），但它只允许在表的一端进行插入和删除操作队列也个元素外），但它只允许在表的一端进行插入和删除操作队列也是一种操作受限的线性表队列在操作系统和事务管理等软件设计是一种操作受限的线性表队列在操作系统和事务管理等软件设计中应用广泛，如键盘输入缓冲区问题就是利用队列的思想实现的中应用广泛，如键盘输入缓冲区问题就是利用队列的思想实现的本章重点和难点：本章重点和难点：1、栈的顺序表示与算法实现、栈的顺序表示与算法实现 2、栈的链式表示与算法实现、栈的链式表示与算法实现 3、求算术表达式的值、求算术表达式的值 4、递归的消除、递归的消除3.1 栈的表示与实现栈的表示与实现3.1.1 栈的表示与实现 栈（栈（stack），也称为堆栈，它是限定仅在表尾进行插入和删除操），也称为堆栈，它是限定仅在表尾进行插入和删除操作的线性表对栈来说，表尾（允许操作的一端）称为栈顶（作的线性表。

对栈来说，表尾（允许操作的一端）称为栈顶（top），），另一端称为栈底（另一端称为栈底（bottom）栈顶是动态变化的，它由一个称为栈）栈顶是动态变化的，它由一个称为栈顶指针（顶指针（top）的变量指示当表中没有元素时，称为空栈的变量指示当表中没有元素时，称为空栈栈的插入操作称为入栈或进栈，删除操作称为出栈或退栈栈的插入操作称为入栈或进栈，删除操作称为出栈或退栈3.1 栈的表示与实现栈的表示与实现 在在栈栈S=(a1,a2,an)中中，a1称称为为栈栈底底元元素素，an称称为为栈栈顶顶元元素素，由由栈栈顶顶指指针针top指指示示栈栈中中的的元元素素按按照照a1，a2，an的的顺顺序序进进栈栈，当当前前的的栈栈顶顶元元素素为为an如如图图所所示示最最先先进进栈栈的的元元素素一一定定是是栈栈底底元元素素，最最后后进进栈栈的的元元素素一一定定是是栈栈顶顶元元素素每每次次删删除除的的元元素素是是栈栈顶顶元元素素，也也就就是是最最后后进进栈栈的的元元素素因因此此，栈栈是是一一种种后后进进先先出出（last in first out，简简称称LIFO）的线性表的线性表3.1 栈的表示与实现栈的表示与实现 若若将将元元素素a、b、c和和d依依次次入入栈栈，最最后后将将栈栈顶顶元元素素出出栈栈，栈顶指针栈顶指针top的变化情况如图所示。

的变化情况如图所示3.1 栈的表示与实现栈的表示与实现3.1.2 栈的抽象数据类型 1数据对象集合数据对象集合 栈的数据对象集合为栈的数据对象集合为a1，a2，an，每个元素都有，每个元素都有相同的类型相同的类型DataType栈中数据元素之间是一对一的关系栈具有线性表的特栈中数据元素之间是一对一的关系栈具有线性表的特点：除了第一个元素点：除了第一个元素a1外，每一个元素有且只有一个直接前外，每一个元素有且只有一个直接前驱元素，除了最后一个元素驱元素，除了最后一个元素an外，每一个元素有且只有一个外，每一个元素有且只有一个直接后继元素直接后继元素3.1 栈的表示与实现栈的表示与实现 2 2基本操作集合基本操作集合 （1）InitStack(&S)：初始化操作，建立一个空栈：初始化操作，建立一个空栈S2）StackEmpty(S)：若栈：若栈S为空，返回为空，返回1，否则返回，否则返回03）GetTop(S,&e)：返回栈：返回栈S的栈顶元素给的栈顶元素给e4）PushStack(&S,e)：在栈：在栈S中插入元素中插入元素e，使其成为新的栈顶元，使其成为新的栈顶元素5）PopStack(&S,&e)：删除栈：删除栈S的栈顶元素，并用的栈顶元素，并用e返回其值。

返回其值6）StackLength(S)：返回栈：返回栈S的元素个数的元素个数7）ClearStack(S)：清空栈：清空栈S3.1 栈的表示与实现栈的表示与实现3.1.3 顺序栈 1.栈的顺序存储结构栈的顺序存储结构 采用顺序存储结构的栈称为顺序栈顺序栈是利用一组地址连续采用顺序存储结构的栈称为顺序栈顺序栈是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，可利用的存储单元依次存放自栈底到栈顶的数据元素，可利用C语言中的数组语言中的数组作为顺序栈的存储结构，同时附设一个栈顶指针作为顺序栈的存储结构，同时附设一个栈顶指针top，用于指向顺序栈，用于指向顺序栈的栈顶元素当的栈顶元素当top=0时表示空栈时表示空栈栈的顺序存储结构类型描述如下：栈的顺序存储结构类型描述如下：#define StackSize 100 typedef struct DataType stackStackSize;int top;SeqStack;3.1 栈的表示与实现栈的表示与实现 当栈中元素已经有当栈中元素已经有StackSize个时，称为栈满如果继续进栈操作则会产生个时，称为栈满如果继续进栈操作则会产生溢出，称为上溢。

对空栈进行删除操作，称为下溢溢出，称为上溢对空栈进行删除操作，称为下溢顺序栈的结构如图所示元素顺序栈的结构如图所示元素a、b、c、d、e、f、g、h依次进栈后，依次进栈后，a为为栈底元素，栈底元素，h为栈顶元素在实际操作中，栈顶指针指向栈顶元素的下一个位置为栈顶元素在实际操作中，栈顶指针指向栈顶元素的下一个位置顺序栈涉及的一些基本操作如下：顺序栈涉及的一些基本操作如下：（1）在初始化栈时，将栈顶指针置为）在初始化栈时，将栈顶指针置为0，即令，即令S.top=02）判断栈空条件为）判断栈空条件为S.top=0，栈满条件为，栈满条件为S.top=StackSize-13）栈的长度（即栈中元素个数）为）栈的长度（即栈中元素个数）为S.top4）进栈操作时，先判断栈是否已满，若未满，将元素压入栈中，即）进栈操作时，先判断栈是否已满，若未满，将元素压入栈中，即S.stackS.top=e，然后使栈顶指针加，然后使栈顶指针加1，即，即S.top+出栈操作时，先判断出栈操作时，先判断栈是否为空，若为空，使栈顶指针减栈是否为空，若为空，使栈顶指针减1，即，即S.top-，然后元素出栈，即，然后元素出栈，即e=S.stackS.top。

3.1 栈的表示与实现栈的表示与实现2 顺序栈的基本运算顺序栈的基本运算（1）初始化栈初始化栈void InitStack(SeqStack*S)/*初始化栈初始化栈*/S-top=0;/*把栈顶指针置为把栈顶指针置为0*/（2）判断栈是否为空判断栈是否为空int StackEmpty(SeqStack S)/*判断栈是否为空，栈为空返回判断栈是否为空，栈为空返回1，否则返回，否则返回0*/if(S.top=0)/*如果栈顶指针如果栈顶指针top为为0*/return 1;/*返回返回1*/else/*否则否则*/return 0;/*返回返回0*/3.1 栈的表示与实现栈的表示与实现（3）取栈顶元素取栈顶元素int GetTop(SeqStack S,DataType*e)if(S.toptop=StackSize)/*如果栈已满如果栈已满*/printf(“栈已满，不能将元素进栈！栈已满，不能将元素进栈！n”);return 0;else/*否则否则*/S-stackS-top=e;/*元素元素e进栈进栈*/S-top+;/*修改栈顶指针修改栈顶指针*/return 1;3.1 栈的表示与实现栈的表示与实现（5）将栈顶元素出栈。

将栈顶元素出栈int PopStack(SeqStack*S,DataType*e)if(S-top=0)/*如果栈为空如果栈为空*/printf(“栈中已经没有元素，不能进行出栈操作栈中已经没有元素，不能进行出栈操作!n”);return 0;else/*否则否则*/S-top-;/*先修改栈顶指针，即出栈先修改栈顶指针，即出栈*/*e=S-stackS-top;/*将出栈元素赋给将出栈元素赋给e*/return 1;3.1 栈的表示与实现栈的表示与实现（6）求栈的长度求栈的长度int StackLength(SeqStack S)/*求栈的长度求栈的长度*/return S.top;（7）清空栈void ClearStack(SeqStack*S)/*清空栈清空栈*/S-top=0;/*将栈顶指针置为将栈顶指针置为0*/3.1 栈的表示与实现栈的表示与实现3 3栈的共享栈的共享 在使用顺序栈时，因为栈空间的大小难以准确估计，可能会出现有的栈还有空闲空间为了能充分利用栈的空间，可以让多个栈共享一个足够大的连续存储空间，通过利用栈顶指针能灵活移动的特性，使多个栈存储空间互相补充，存储空间得到有效利用，这就是栈的共享栈的共享。

3.1 栈的表示与实现栈的表示与实现 共享栈的数据结构类型描述如下共享栈的数据结构类型描述如下typedef struct DataType stackStackSize;int top2;SSeqStack;其中，其中，top0和和top1分别是两个栈的栈顶指针分别是两个栈的栈顶指针用一维数组表示的共享栈如图所示用一维数组表示的共享栈如图所示3.1 栈的表示与实现栈的表示与实现（1）初始化栈初始化栈void InitStack(SSeqStack*S)/*共享栈的初始化共享栈的初始化*/S-top0=0;S-top1=StackSize-1;3.1 栈的表示与实现栈的表示与实现（2）取栈顶元素取栈顶元素int GetTop(SSeqStack S,DataType*e,int flag)/*取栈顶元素将栈顶元素值返回给取栈顶元素将栈顶元素值返回给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;3.1 栈的表示与实现栈的表示与实现（3）将元素）将元素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，表示将元素要进右端的栈，表示将元素要进右端的栈*/S-stackS-top1=e;/*元素进栈元素进栈*/S-top1-;/*修改栈顶指针修改栈顶指针*/break;default:return 0;return 1;/*返回返回1，进栈成功，进栈成功*/3.1 栈的表示与实现栈的表示与实现（4）将栈顶元素出栈将栈顶元素出栈int PopStack(SSeqStack*S,DataType*e,int flag)switch(flag)/*在出栈操作之前，判断哪个栈。