(3.3.1)--3.3队列与循环队列.ppt

《(3.3.1)--3.3队列与循环队列.ppt》由会员分享，可在线阅读，更多相关《(3.3.1)--3.3队列与循环队列.ppt（15页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、队列与循环队列队列与循环队列1队列(queue)队列的定义及特点定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表 队尾(rear)允许插入的一端 队头(front)允许删除的一端队列特点：先进先出(FIFO First In First Out)a1 a2 a3.an 入队出队frontrear队列Q=(a1,a2,an)链队列结点定义typedef int ElemType;typedef struct node ElemType data;struct node *next;JD;typedef struct JD front;JD rear;LinkQueue;头结点

2、 .front队头队尾rear设队首指针front，指向头结点设队尾指针rear,指向队尾frontrearx入队xfrontreary入队xyfrontrearx出队xyfront rear空队front reary出队5frontrearx入队xbool EnQueue(LinkQueue&Q,ElemType e)p=(JD*)malloc(sizof(JD);if(p)p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;return true;return false;v入队算法rearv出队算法DeQueue(LinkQueue&Q,ElemTyp

3、e&e)if(Q.front=Q.rear)return ERROR;p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear=p)Q.rear=Q.front;/特殊情况 free(p);return OK;frontrearx出队xy队列的顺序存储结构v实现：用一维数组实现sqMfront=0rear=0123450队空123450frontJ1,J2,J3入队J1J2J3rearrear123450J4,J5,J6入队J4J5J6front设两个指针front,rear,约定：rear指示队尾元素的下一个位置；front指示队头元素；初值

4、front=rear=0空队列条件：front=rear入队列：sqrear+=x;出队列：x=sqfront+;rearrearfrontfrontfrontfrontrearrear123450J1,J2,J3出队J1J2J3队列存在的问题设数组容量为M，则：当front=0,rear=M时，再有元素入队发生溢出真溢出当front0,rear=M时，再有元素入队发生溢出假溢出(不能充分利用空间)解决方案一队首固定，每次出队剩余元素向下移动浪费时间9rear123450J1出队J1front队头front位置不动，平移调整队列中的元素及队尾位置J3J2解决方案二循环队列基本思想：把队列设想成

5、环形，让sq0接在sqM-1之后，若rear+1=M,则令rear=0;u实现：利用“模”运算u入队：sq rear=x;rear=(rear+1)%M;u出队：x=sq front;front=(front+1)%M;0maxsize-11frontrear.循环队列012345rearfrontJ5J6J7012345rearfrontJ4J9J8J4J5J6012345rearfront初始状态J4,J5,J6出队J7,J8,J9入队队空：front=rear解决方案：1.另外设一个标志以区别队空、队满2.队列中留一个空位：队空：front=rear 队满：(rear+1)%M=fron

6、t队满：front=rear入队算法：入队算法：int en_cycque(int sq,int front,int rear,int x)int en_cycque(int sq,int front,int rear,int x)if if(rear+1)%M)=front(rear+1)%M)=front)/)/队满队满 printf(overflow);printf(overflow);return 0;return 0;else else sqrear=x;sqrear=x;rear=(rear+1)%M;/rear=(rear+1)%M;/队尾指针后移队尾指针后移 return 1;return 1;出队算法：出队算法：int dl_cycque(int sq,int front,int rear,int*q)if(front=rear)/队空 return 0;/返回出队失败标志 else *q=sqfront;/存储出队元素 front=(front+1)%M;/头指针后移一位 return 1;/返回出队成功标志 课程作业：1 1、整理并写出判断循环队列空满的条件。、整理并写出判断循环队列空满的条件。15 下下下下 节节节节 课课课课 见见见见！