西电软件技术基础课件5,6 栈和队列.ppt

《西电软件技术基础课件5,6 栈和队列.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、栈和队列软件技术基础（三）西安电子科技大学电子工程学院林杰本部分的内容1.基本要求（1）了解栈和队列是操作受限的线性表的概念；掌握顺序栈、链栈、顺序队列、链队列的类型定义和基本运算的实现算法；掌握循环队列的概念和满队、空队的条件。（2）掌握利用基本运算编写实现栈和循环队列应用的算法。2.重点、难点重点：栈和队列的逻辑结构、存储结构、基本运算的实现，栈和队列的应用算法。难点：栈和循环队列应用的算法。2生活中的栈举例1：家里吃饭的碗，通常在洗干净后一个一个地落在一起存放，在使用时，若一个一个地拿，一定最先拿走最上面的那只碗，而最后拿出最下面的那只碗。举例2：在建筑工地上，使用的砖块

2、从底往上一层一层地码放，在使用时，将从最上面一层一层地拿取。3栈的基本概念栈(Stack)：是限制在表的一端进行插入和删除操作的线性表。又称为后进先出LIFO(LastInFirstOut)或先进后出FILO(FirstInLastOut)线性表。栈顶(Top)：允许进行插入、删除操作的一端，又称为表尾。用栈顶指针(Top)来指示栈顶元素。栈底(Bottom)：是固定端，又称为表头。空栈：当表中没有元素时称为空栈。4栈的基本概念设栈S=(a1，a2，…an)，则a1称为栈底元素，an为栈顶元素，如右图所示。元素是以a1,a2,…,an的顺序进栈，出栈的次序却是an,an-1,…

3、,a1。栈的修改原则：“后进先出”。顺序栈示意图a1a2aian⋯⋯⋯⋯栈底Bottom栈顶Top进(入)栈（push）出(退)栈(pop)5栈的基本概念栈“上溢”：在栈满时还进行进栈运算，必定会产生空间的溢出栈“下溢”：当栈空时仍进行出栈运算，必定会产生空间的溢出。上溢是一种出错状态，应该设法避免之；下溢则可能是正常现象，因为栈在程序中使用时，其初态或终态都是空栈，所以下溢常常用来作为程序控制转移的条件。6栈的常用基本运算(1) InitStack(&S)——栈初始化，构造一个空栈S。(2) SetNull(S)——置空栈，将栈S清为空栈。(3) Empty(S)——判断栈空

4、，若栈S为空，则返回“真”值；否则返回“假”值。(4) Push(S，e)——进栈，若栈S不满，则将数据元素e插入栈顶。(5) Pop(S,&e)——出栈，若栈S非空，则删除栈顶数据元素，并返回该数据元素。(6) GetTop(S)——取栈顶元素，若栈S非空，则返回栈顶数据元素。该操作完成后，栈的内容不变。7栈的表示和实现栈作为特殊的线性表，有两种基本的存储结构：顺序存储结构：顺序栈链式存储结构：链栈顺序栈即栈的顺序存储结构，是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针Top指示栈顶元素在顺序栈中的存储位置。空栈Top=08栈的顺序存储结构#defi

5、nemaxsize50typedefstruct{datatypedata[maxsize];//用来存放栈中元素的一维数组intTop;//用来存放栈顶元素的下标}SeqStack;①顺序栈中元素用向量存放②栈底位置是固定不变的，可设置在向量两端的任意一个端点③栈顶位置是随着进栈和退栈操作而变化的，用一个整型量Top（通常称Top为栈顶指针）来指示当前栈顶位置9栈的顺序存储结构定义：SeqStack*S；并规定下标为0的向量元素不用。S->data[1]是栈底元素，S->data[S->Top]是栈顶元素；当S->Top≤0表示空栈；当S->Top=maxsize-1表示栈满

6、；入栈要先判断栈满（上溢）；出栈要先判断栈空（下溢）；10顺序表和顺序栈的操作有何区别？以线性表S=(a0,a1,….,an-2,an-1)为例a0a1……an-1顺序栈Sai……表头表尾last低地址高地址写入：S->data[i]=ai读出：e=S->data[i]低地址高地址a0a1aian-1……顺序表S……an栈底Bottom栈顶Top前提：一定要预设栈顶指针Top进栈(Push):S->data[S->Top++]=an出栈(Pop):e=S->[--S->Top]11顺序栈中的进出栈（图释）6543210(a)空栈Top6543210A(b)A进栈Top65432

7、10DCBA(c)BCD进栈Top6543210BA(d)DC出栈Top12顺序栈的基本操作（1）栈的初始化，即建立空顺序栈voidInitStack(SeqStack*&S)//构造一个空栈S{S=(SeqStack*)malloc(sizeof(SeqStack));S->Top=0;//定义初始栈顶下标值}13顺序栈的基本操作（2）顺序栈置空voidSetNull(SeqStack*S)//将顺序堆栈S置为空栈{S->Top=0;}14顺序栈的基本操作（3）判栈空intEmpty(Se