03-数据结构-栈与队列2

《03-数据结构-栈与队列2》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、ThanksWangqiongofZhongbeicollegeattachingtoNanjing Normal University第三节队列一、逻辑结构　　只能在一端(队尾rear)插入，在另一端(队头front)删除的线性表。　　先进先出表FIFO(FirstInFirstOut)基本操作：进/出队列判别队列满/空队列的应用背景：排队模型。排队问题无处不在，各种服务行业、甚至生产管理中都存在排队问题。二、链式存储结构Typedefstructqueuenode//队列中的结点类型{ElemTypedata;structNode

2、*link;}QueueNode;typedefstruct//队列类型{QueueNode*front,*rear;}LinkQueue;LinkQueueQ;初始化空队列：Q.front==NULLQ.rear==NULL1、入队列StatusLinkQueue_Enter(LinkQueue&Q,ElemTypee){QueueNode*p;p=(QueueNode*)malloc(sizeof(QueueNode));if(!p)return(OVERFLOW);p->data=e;p->link=NULL;3-12Thank

3、sWangqiongofZhongbeicollegeattachingtoNanjing Normal Universityif(Q.front==NULL)Q.front=Q.rear=p;else{Q.rear->link=p;Q.rear=p;}return(OK);}2、出队列StatusLinkQueue_Leave(LinkQueue&Q,ElemType&e){QueueNode*p;if(Q.front==NULL)return(UNDERFLOW);p=Q.front;Q.front=p->link;if(Q.re

4、ar==p)Q.rear=NULL;e=p->data;free(p);return(OK);}3、销毁队列voidLinkQueue_Destroy(LinkQueue&Q){QueueNode*p;while(Q.front){p=Q.front;Q.front=p->link;free(p);}Q.rear=NULL;}三、顺序存储结构动态顺序存储结构：3-12ThanksWangqiongofZhongbeicollegeattachingtoNanjing Normal University#defineQUEUE_SIZE

5、100//初始化时分配的空间typedefstruct{ElemType*base;//存储空间的起始地址intfront,rear;}SqQueue;SqQueueQ;//定义一个队列结构rear为下一个进队列元素的位置。front在队列不空时，指向首元素；在队列为空时，等于rear。1、初始化队列StatusSqQueue_Init(SqQueue&Q){Q.base=malloc(QUEUE_SIZE*sizeof(ElemType));if(!Q.base)return(OVERFLOW);Q.front=Q.rear=0;r

6、eturn(OK);}队列空：Q.front==Q.rear进队列：*(Q.base+Q.rear)=e;Q.rear++;出队列：e=*(Q.base+Q.front);Q.front++;队列满：Q.rear==QUEUE_SIZE=》假溢出进队列：Q.rear=(Q.rear+1)%QUEUE_SIZE出队列：Q.front=(Q.front+1)%QUEUE_SIZE队列空：Q.front==Q.rear3-12ThanksWangqiongofZhongbeicollegeattachingtoNanjing Normal 

7、University当队列中有QUEUE_SIZE个元素时：Q.front==Q.rear=》必须浪费一个结点空间队列满：(Q.rear+1)%QUEUE_SIZE==Q.front2、入队列StatusSqQueue_Enter(SqQueue&Q,ElemTypee){if((Q.rear+1)%QUEUE_SIZE==Q.front)return(OVERFLOW);*(Q.base+Q.rear)=e;Q.rear=(Q.rear+1)%QUEUE_SIZE;return(OK);}3、出队列StatusSqQueue_Lea

8、ve(SqQueue&Q,ElemType&e){if(Q.rear==Q.front)return(UNDERFLOW);e=*(Q.base+Q.front);Q.front=(Q.front+1)%QUEUE_SI