软件技术基础4_栈队列课件.ppt

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

1、1.2.2栈与队列一.栈ana1a2……...栈底栈顶...出栈进栈栈s=(a1,a2,……,an)1.顺序栈typedefstruct{elemtypestack[MAXNUM];inttop;}stacktype;初始化：voidinitiate_st(stacktype*s){s-->top=-1;}栈顶元素位置top＝-1：空栈top＝0：有一个元素存在stack[0]中插入算法:#definetrue1#definefalse0intpush_st(stacktype*s,elemtypex){if(s-->top>=MAXNUM-1)return(false);els

2、e{s-->top++;s-->stack[s-->top]=x;return(true);}}删除算法：elemtypepop_st(stacktype*s){if(s-->top<0)return(NULL);else{s-->top--;return(s-->stack[s-->top+1]);}}2.链式存储结构的链栈structnode{elemtypedata;structnode*next;}^top栈底栈顶…...aiai-1ai-2a1进栈^…...栈底toptopxpvoidpush_lst(node**ptop,elemtypex){node*p;p=(no

3、de*)malloc(sizeof(node));p-->data=x;p-->next=(*ptop);(*ptop)=p;}出栈top^…...栈底topqelemtypepop_lst(node**ptop){node*p;elemtypex;if((*ptop)==NULL){printf(“stackisunderflow”);return(NULL);}x=(*ptop)-->data;p=(*ptop);(*ptop)=(*ptop)-->next;free(p);return(x);}二.队列先进先出（FIFO）setnull_q（Q）empty_q（Q）ente

4、r_q（Q，x）delete_q（Q）gethead（Q）a1a2a3…………………….an入队出队frontrear队列Q=(a1,a2,……,an)1.队列的顺序存储结构typedefstruct{elemtypequeue[MAXNUM+1];intfront;intrear;}queuetype;queuetypeQ;:尾元素位置:队列首元素的前一个算法[13]入队列操作intenter_q(queuetype*q,elemtypex){if(q-->rear>=MAXNUM)return(false);else{q-->rear++;q-->queue[q-->rear

5、]=x;return(true);}}[算法14]出队列操作elemtypedelete_q(queuetype*q){if(q-->front==q-->rear)return(NULL);else{q-->front++;return(q-->queue[q-->front]);}}循环队列假溢出--循环队列初始状态：q-->front=q-->rear=0循环队列为空的条件：(q-->front)==(q-->rear)循环队列为满的条件：(q-->rear+1)%MAXNUM==q-->front[算法15]循环队列入队操作intenter_cq(queuetype*q

6、,elemtypex){if((q-->rear+1)%MAXNUM==q->front)return(false);else{q-->rear=(q-->rear)%MAXNUM+1;q-->queue[q-->rear]=x;return(true);}}[算法15]循环队列出队操作elemtypedelete_cq(queuetype*q){if((q-->front)==(q-->rear))return(NULL);else{q-->front=(q-->front)%MAXNUM+1;return(q-->queue[q-->front]);}}2.队列的链式存储结构

7、[算法17]进链队列操作算法frontrear空队^frontrearx入队^xfrontreary入队x^yvoidenter_lq(qtype*q,elemtypex){node*p;p=(node*)malloc(sizeof(node));p-->data=x;p-->next=NULL;q-->rear-->next=p;q-->rear=p;}[算法18]出链队列操作算法frontrear空队^frontrearx出队x^yfrontreary出队^elemtyped