数据结构第3章栈和队列课件.ppt

《数据结构第3章栈和队列课件.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）的线性表（

2、简称LIFO结构）。图3.1栈栈只能对栈顶元素进行插入和删除操作。例：若输入A，B，C，D，同时在插入的时候也可能进行删除操作。可能的输出序列为：B，A，C，D;C、D、A、B；D，A，C，B；C、A、D、B；D，C，A，B；C、B、D、A；B，C，A，D；A，C，B，D；ADTStack{数据元素：可以是任意类型的数据，但必须属于同一个数据对象。数据关系：栈中数据元素之间是线性关系。基本操作：（1）InitStack(&S)初始条件：S为未初始化的栈。操作结果：将S初始化为空栈。（2）ClearStack(&S)初始条件：栈S已经存在。操作结

3、果：将栈S置成空栈。（3）StackEmpty(S)初始条件：栈S已经存在。操作结果：若S为空栈，则函数值为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.顺序栈顺序栈是用顺序存储结构实现

4、的栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时由于栈的操作的特殊性，还必须附设一个位置指针top（栈顶指针）来动态地指示栈顶元素在顺序栈中的位置。通常以top=0表示空栈。顺序栈的存储结构可以用C语言中的一维数组来表示。栈的顺序存储结构定义如下：＃defineTRUE1＃defineFALSE0typedefstruct{SElemType*base;SElemType*top;intstacksize;//栈可使用的最大容量}SqStack;按初始分配量进行第一次存储分配，base为栈底指针，始终指向栈底。top为栈顶指针，初值指向

5、栈底，每插入一个元素，top增1；每删除一个元素，top减1，top始终在栈顶元素的下一个位置上。图3.2顺序栈中的进栈和出栈43210432104321043210顺序栈基本操作的实现如下:(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)取栈顶元素Status

6、GetTop(SqStackS,SElemType&e){if(S.top==S.base)returnERROR;e=*(S.top-1);returnOK;}(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;

7、S.stacksize+=STACKINCREMENT;}*S.top++=e;returnOK;}(4)出栈StatusPop(SqStack&S,SelemType&e){if(S.top==S.base)returnERROR;e=*--S.top;returnOK;}2.链栈图3.4链栈示意图链式栈无栈满问题，空间可扩充插入与删除仅在栈顶处执行链式栈的栈顶在链头适合于多栈操作2.链栈图3.4链栈示意图栈的链式存储结构实际上就是一个单链表，叫做链栈。插入和删除操作只能在链栈的栈顶进行。栈顶指针Top应该在链表的哪一头？链式栈的栈顶在链头插入与删除仅在栈顶

8、处执行链式栈无栈满问题，