第3章+栈和队列ppt课件.ppt

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

1、第3章限定性线性表—栈和队列3.1栈3.2栈的应用举例3.3栈与递归的实现3.4队列3.1栈3.1.1栈的定义栈作为一种限定性线性表，是将线性表的插入和删除运算限制为仅在表尾进行，通常将表中允许进行插入、删除操作的一端称为栈顶(Top)，因此栈顶的当前位置是动态变化的，它由一个称为栈顶指针的位置指示器指示。同时表的另一端被称为栈底(Bottom)。当栈中没有元素时称为空栈。栈的插入操作被形象地称为进栈或入栈，删除操作称为出栈或退栈。设S=(a1,a2,…,an)表示栈，则a1为栈底元素，an为栈顶元素。栈是一种后进先出（LastInFirstOut）的线性表（简称LIFO结构）。栈只

2、能对栈顶元素进行插入和删除操作。例：若输入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.1栈ADTStack{数据元素：可以是任意类型的数据，但必须属于同一个数据对象。数据关系：栈中数据元素之间是线性关系。基本操作：（1）InitStack(&S)初始条件：S为未初始化的栈。操作结果：将S初始化为空栈。（2）ClearStack(&S)初始条件：栈S已经存在。操作结果：将栈S置成空栈。（3）StackEmpty(S)初始条件：栈S已经存在。操作结果：若S为空栈，则

3、函数值为TRUE，否则FALSE（4）Push(&S,e)初始条件：栈S已经存在。操作结果：在S的顶部插入(亦称压入)元素e；（5）Pop(&S,&e)初始条件：栈S已经存在。操作结果：删除(亦称弹出)栈S的顶部元素，并用e带回该值。（6）GetTop(S,&e)初始条件：栈S已经存在。操作结果：取栈S的顶部元素。与Pop(&S,e)不同之处在于GetTop(S,&e)不改变栈顶的位置。}3.1.2栈的表示和实现1.顺序栈顺序栈是用顺序存储结构实现的栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时由于栈的操作的特殊性，还必须附设一个位置指针top（栈顶

4、指针）来动态地指示栈顶元素在顺序栈中的位置。通常以top=0表示空栈。顺序栈的存储结构可以用C语言中的一维数组来表示。栈的顺序存储结构定义如下：＃defineTRUE1＃defineFALSE0typedefstruct{SElemType*base;SElemType*top;intstacksize;//栈可使用的最大容量}Sqstack;按初始分配量进行第一次存储分配，base为栈底指针，始终指向栈底。top为栈顶指针，初值指向栈底，每插入一个元素，top增1；每删除一个元素，top减1，top始终在栈顶元素的下一个位置上。图3.2顺序栈中的进栈和出栈顺序栈基本操作的实现如下

5、:(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;}(2)取栈顶元素StatusGetTop(SqStackS,SElemType&e){if(S.top==S.base)returnERROR;e=*(S.top-1);returnOK;}(3)入栈。StatusPush(SqStack&

6、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;}(4)出栈StatusPop(SqStack&S,SelemType&e){If(S.top==S.base)returnERROR;e

7、=*--S.top;returnOK;}在栈的共享技术中最常用的是两个栈的共享技术：它主要利用了栈“栈底位置不变，而栈顶位置动态变化”的特性。首先为两个栈申请一个共享的一维数组空间S［M］，将两个栈的栈底分别放在一维数组的两端，分别是0，M-1。由于两个栈顶动态变化，这样可以形成互补，使得每个栈可用的最大空间与实际使用的需求有关。由此可见，两栈共享比两个栈分别申请M/2的空间利用率高。图3.3共享栈2.链栈图3.4链栈示意图3.2栈的应用举例1