第3章栈与队列(已修改).ppt

《第3章栈与队列(已修改).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1第3章栈和队列栈和队列被称为操作受限的线性表。本章介绍栈和队列的逻辑结构和存储结构，以及栈和队列的基本运算以及实现算法。2（a1,a2,...,ai-1,ai,ai+1,…,an）插入删除3.1栈只允许在线性表的一端进行插入和删除操作的线性表允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)特点后进先出(LIFO)3栈的基本操作INITSTACK(s)构造一个空栈s。STACKEMPTY(s)判断s是否为空栈，若s为空栈，返回1,否则返回0。PUSH(s,x)进栈操作。在栈s顶部插入一个新的元素x。PO

2、P(s,x)退栈操作，若s非空，删除s中的栈顶元素，并返回该元素。4GETTOP(s)取栈s的栈顶元素。若s非空，返回栈顶元素，但与POP(s,x)的区别是GETTOP(s)不改变栈的状态。CLEASTACK(s)将栈s清为空栈。STACKLENGTH(s)求栈的长度，返回栈s中的元素个数。5栈的表示和实现由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应。1.顺序栈栈的顺序存储结构—顺序栈，可以将栈底位置设置在数组的低地址端点；栈顶位置是随着进栈和退栈操作而变化的，故需用一个整型变量top，指明当前栈顶的位置，同样将

3、data数组和top封装在一个结构中，顺序栈的类型描述如下：#defineMAXSIZE1024typedefstructSeqStack{datatypedata[MAXSIZE];inttop;}SeqStack6退栈进栈a1anan-1top7bottomtopbottomtopAABCDEAB栈操作图示A进栈BCDE进栈EDC出栈CDEtoptoptop栈的特点后进先出LIFO入栈与出栈topbottomtopbottomtoptoptop8约定栈顶指针指向向栈顶元素的位置当栈用顺序结构存储时，栈的基本操作如建空栈

4、、进栈、出栈等操作如何实现？顺序栈的图示topMAX-1nn-1n-210anan-1a2a1栈空：栈满：Top=-1Top=maxlen-192．顺序栈的基本运算算法（1）初始化栈voidINITSTACK(seqstack*s){/*创建一个空栈由指针S指向*/s->top=-1;}思考：voidINITSTACK(seqstacks){s.top=-1;}哪个是对的？为什么？10MAX-1nn-1n-210建立空栈top11(2)判栈空判定顺序栈S是否空栈,S为空时，返回为1；非空时，返回为0intSTACKEMPTY

5、(seqstack*s){if(s->top>=0)/*s.top>=0*/return0;elsereturn1;}12（3）入栈操作PUSH(seqstacks,datatypex){if(s.top==maxsize-1){error(“overflow”);returnNULL;}//上溢，退出运行；else{s.top++;//栈顶指针+1；s.data[s.top]=x;}//将x入栈；}13（4）出栈操作datatypePOP(seqstacks){ifSTACKEMPTY(s){error(“underflo

6、w”);//下溢；returnNULL;}else{return(s.data[s.top]);s.top--；}}14（5）取栈顶元素操作datatypeGETTOP(seqstacks){if(STACKEMPTY(s)){error(“stackisempty”);returnNULL;}//栈空；elsereturn(s.data[s.top]);//取栈顶元素；}15顺序栈的不足：存在栈满以后就不能再进栈的问题（这是因为用了定长的数组存储栈的元素）解决方法：使用链式存储结构。162.链栈栈的链式存储结构，也称链栈(

7、没有头结点的单链表)。其各结点的结构与单链表中的结点结构完全相同。如图所示：在前面学习了线性链表的插入删除操作算法，不难写出链式栈初始化、进栈、出栈等操作的算法结点结构定义：Typedefstructnode{elemtypedata;structnode*next;}node,*pointer;Datanexts栈顶（单链表的表头）栈底an-1a1an17(1)初始化栈Voidinitstack（pointers）{s=null;}^s18Datanexts栈顶栈底an-1a1anDatanext栈顶栈底an-1a1anx

8、ps进栈前进栈后(2)进栈19进栈算法Voidpush(pointers,datatypex){p=(pointer*)malloc(sizeof(node));p->data=x;p->next=s;s=p;}20出栈前出栈后Datanext栈顶栈底an-1a1ansDatanextp栈