数据结构教程3 栈和队列课件.ppt

《数据结构教程3 栈和队列课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、⒈教学内容：3.1栈3.2栈应用举例3.3队列3.4队列应用举例⒉教学目的：⑴理解栈的定义、特征及在其上所定义的基本运算⑵掌握在两种存储结构上对栈所施加的基本运算的实现⑶理解队列的定义、特征及在其上所定义的基本运算⑷掌握在两种存储结构上对队列所施加的基本运算的实现第三章栈和队列⒊教学重点：⑴栈的定义及逻辑特点，栈的基本运算；⑵栈的顺序存储结构及运算实现；⑶栈的链式存储结构及运算实现；⑷队列的定义及逻辑特点，队列的基本运算；⑸队列的顺序存储结构及其上的运算实现；⑹队列的链式存储结构及运算实现。⒋教学难点

2、：⑴顺序栈的溢出判断条件；⑵循环队列的队空、队满判断条件；⑶循环队列上的插入、删除操作。栈和队列是两种特殊的线性表，是操作受限的线性表，称限定性DS3.1栈栈的定义及基本运算栈的存储实现和运算实现3.1栈（stack）栈的定义和特点定义：限定仅在表尾进行插入或删除操作的线性表，表尾—栈顶，表头—栈底，不含元素的空表称空栈特点：先进后出(FILO)或后进先出(LIFO)ana1a2……...栈底栈顶...出栈进栈栈s=(a1,a2,……,an)栈的基本操作有：⑴栈初始化：Init_Stack(s)操作结

3、果是构造了一个空栈。⑵判栈空：Empty_Stack(s)操作结果是若S为空栈返回为1，否则返回为0。⑶入栈：Push_Stack(s，x)操作结果是在栈S的顶部插入一个新元素X，X成为新的栈顶元素。⑷出栈：Pop_Stack(s)在栈S存在且非空的情况下，操作结果是将栈S的顶部元素从栈中删除。⑸读栈顶元素：Top_Stack(s)在栈S存在且非空情况下，操作结果是读栈顶元素，栈不变化。例行编辑程序whli##ilr#e(s#*s)outcha@putchar(*s=#++)；则实际有效的是下面两行：

4、while(*s)putchar(*s++)；voidLineEdit(){InitStack(S)；ch=getchar()；while(ch!=EOF){while(ch!=EOF&&ch!=''){switch(Ch){case'#'：Pop(S，c)；break；case'@'：ClearStack(S)；break；default：Push(S，ch);break；}ch=getchar()；}将从栈底到栈顶的栈内字符传送至调用过程的数据区；ClearStack(S)；if(ch!=EO

5、F)ch=getchar()；}DestroyStack(S)；}//LlineEdit3.1.2栈的存储实现和运算实现⒈顺序栈栈中的数据元素用一个预设的足够长度的一维数组来实现：datatypedata[MAXSIZE]栈底位置可以设置在数组的任一个端点，而栈顶是随着插入和删除而变化的，用一个inttop来作为栈顶的指针，指明当前栈顶的位置，将data和top封装在一个结构中。顺序栈的类型描述如下：#defineMAXSIZE1024typedefstruct{datatypedata[MAXSIZ

6、E];inttop;}SeqStack；定义一个指向顺序栈的指针：SeqStack*s;//-----栈的顺序存储表示-----#defineSTACK_INIT_SIZE100；//存储空间初始分配量#defineSTACKINCREMENT10；//存储空间分配增量typedefstruct{SElemType*base；//在栈构造之前和销毁之后，base的值为NULLSElemType*top；//栈顶指针intstacksize；//当前已分配的存储空间，以元素为单位}SQStack；top

7、=-1123450栈空栈顶指针top,指向实际栈顶后的空位置，初值为-1top123450进栈Atop出栈栈满BCDEF设数组维数为Mtop=-1,栈空，此时出栈，则下溢（underflow)top=M-1,栈满，此时入栈，则上溢（overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop栈空通常0下标端设为栈底，这样空栈时栈顶指针top=-1;入栈时，栈顶指针加１，即s->top++;出栈时，栈顶指针减１，即s->top--。图(a)是空栈，图(c)

8、是A、B、C、D、E5个元素依次入栈之后，图(d)是在图(c)之后E、D相继出栈，此时栈中还有3个元素，或许最近出栈的元素D、E仍然在原先的单元存储着，但top指针已经指向了新的栈顶，则元素D、E已不在栈中了。⑴置空栈首先建立栈空间，然后初始化栈顶指针。SeqStack*Init_SeqStack(){SeqStack*s;s=malloc(sizeof(SeqStack));s->top=-1;returns;}⑵判空栈intEmpty_SeqStac