《数据结构与算法——C语言和Java语言描述 ppt及答案和其他资源5顺序队列和循环队列》由会员分享，可在线阅读，更多相关《数据结构与算法——C语言和Java语言描述 ppt及答案和其他资源5顺序队列和循环队列（13页珍藏版）》请在金锄头文库上搜索。
1、第三章 栈和队列,顺序队列和循环队列,生活中的栈与队列 栈和队列是特殊的线性表 栈与队列的特征 LIFO(Last In First Out) FIFO(First In First Out),第3节/队列,1.队列（Queue）的定义,FIFO,队列简称为队，是限定只能在表的一端作插入运算、在另一端作删除运算的线性表； 在表中，允许插入的一端称作“队尾”，允许删除的另一端称作“队首”（或“队头”）； 通常将元素插入队尾的操作称作为入队列（或入队），称删除队首元素的操作为出队列（或出队）。,2.队列的存储结构,两种结构： (1) 顺序队列采用顺序结构存储 (2) 链式队列采用链式结构存储,第4
2、节/顺序队列,3.4.1.队列的顺序存储结构-1,#define MaxSize n 队列可能达到的最大长度n typedef struct ElementType elemMaxSize; int front, rear; /*队首、队尾指示器*/ Queue;,3.4.1.队列的顺序存储结构-2,图3.12 队列操作,队满和队空的条件是什么？,队空：front=rear 队满：rear=Maxsize-1,?,3.4.1.队列的顺序存储结构-3,当rear=MaxSize-1时,队列为满，如果再加入新元素，就会产生“溢出“。 但是这种“溢出“并不是真正的溢出，在数组的前端还可能有空位置，所
3、以这是一种假溢出。,b,c,e,rear=4,d,front=0,front=rear=4,解决方法：循环队列,3.4.1.队列的顺序存储结构-4,为了能够充分的使用数组中的存储空间，把数组的前端和后端连接起来，形成一个环形的表，即把存储队列元素的表从逻辑上看成一个环，成为循环队列（Circular Queue）。,front,front,rear,front,rear,a,front,rear,b,c,d,front,rear,a,b,c,d,front,rear,a,b,c,rear,(a) 空队列,(b) a入队列,(c) b,c入队列,(d) d入队列（队满）,(e) 出队1次,(f)
4、 出队3次（队空）,队头指针进1：front=(front+1)%MaxSize； 队尾指针进1：rear=(rear+1)%MaxSize；,以下是队空的几种情况：,初始化时：front=rear=0 循环队列为空的条件是：front=rear,front,rear,(a) 空队列,front,rear,(f) 出队3次（队空）,front=0 Rear=0,front=4 Rear=4,循环队列为满的条件是：front=(rear+1) % MaxSize,front,rear,a,b,c,d,以下是队满的几种情况：,front=0 Rear=4,front,rear,a,b,c,d,front=3 Rear=2,front,rear,b,c,d,a,front=1 Rear=0,
