《循环队列》由会员分享，可在线阅读，更多相关《循环队列（32页珍藏版）》请在金锄头文库上搜索。
1、3.2 循环队列 队队列的逻辑结逻辑结 构和基本计计算 循环队环队 列的运算 队队列的存储结储结 构 目 录 队列的概念 队列是一种只允许在表的一端（称为队尾）进行插入 ，在另一端（称为对头）进行删除的线性表。 队列的概念 队列是一种只允许在表的一端（称为队尾）进行插入 ，在另一端（称为对头）进行删除的线性表。 删删除结结点 只能删除队头的结点a1 增加结结点 只能在队尾插入结点x 队列的概念 队列是一种只允许在表的一端（称为队尾）进行插入 ，在另一端（称为对头）进行删除的线性表。 与我们生活中的排队非常相似 先排队的先离开 晚排队的晚离开 不允许插队 不允许中途离队 因此，队列也称先进先出(
2、FIFO) 队列有5种基本运算 来使用和管理队列。 队列的5种基本运算 置队空SetNull(Q)1 获取有效结点长度GetLength(Q)2 取头结点GetHead(Q)3 入队InsQueue(Q, x)4 出队DelQueue(Q)5 将队列Q置成空队列 队列的5种基本运算 置队空SetNull(Q)1 获取有效结点长度GetLength(Q)2 取头结点GetHead(Q)3 入队InsQueue(Q, x)4 出队DelQueue(Q)5 返回队列中的结点数 N个结点数 若N为零，则为空队列 队列的5种基本运算 置队空SetNull(Q)1 获取有效结点长度GetLength(Q)
3、2 取头结点GetHead(Q)3 入队InsQueue(Q, x)4 出队DelQueue(Q)5 读取队列Q中头结点的值 队列中的结点保持不变 队列的5种基本运算 置队空SetNull(Q)1 获取有效结点长度GetLength(Q)2 取头结点GetHead(Q)3 入队InsQueue(Q, x)4 出队DelQueue(Q)5 将结点x插入到队列Q的队尾 x 队列的5种基本运算 置队空SetNull(Q)1 获取有效结点长度GetLength(Q)2 取头结点GetHead(Q)3 入队InsQueue(Q, x)4 出队DelQueue(Q)5 删除队列头结点 队队列的逻辑结逻辑结
4、 构和基本计计算 循环队环队 列的运算 队队列的存储结储结 构 目 录 队列的存储结构 循环队列顺序队列链接队列 常用队列的存储结构 本章重点讲解 顺序队列的存储结构 当队列采用顺序存储结构时， 可利用一维数组来存放结点数据 。 一维数组来 存放节点数据 数组下标 0 1 2 n - 1 n msize - 1 顺序队列的存储结构 一维数组来 存放节点数据 数组下标 0 1 2 n - 1 n msize - 1 head tail 队列的操作只能在表头和表尾 进行，且不移动队列的结点。 必须有活动的 表头和表尾的索引 头尾索引即头尾 结点对应的数组下标 顺序队列的结构描述 一维数组来 存放节
5、点数据 数组下标 0 1 2 n - 1 n msize - 1 head tail #define msize 128 typedef struct unsigned char arraumsize; unsigned char head; unsgined char tail; Queue; 顺序队列的存储结构 一维数组来 存放节点数据 数组下标 0 1 2 n - 1 n msize - 1 tail 当要删除一结点时 必须删除索引 head所指向的结点 再将头索引加1， 使其指向下一结点 head 出队运算可描述为： head+; 顺序队列的存储结构 0 1 2 n - 1 n msi
6、ze - 1 当要插入一结点时 必须将结点值插入到 尾索引tail所指向的结点 head 入队运算可描述为： arraytail+; 再将头索引加1， 使其指向下一结点 tail x 顺序队列的存储结构 0 1 2 n - 1 n msize - 1 当队列装满时 当队满时，若再做入队 操作会产生“上溢” head tail 尾索引tail等于 最大结点msize时， 后果 不可预测预测 产生该现象的原因是： 被删除的结点（出队结点 ）的空间永远不能再使用。 采用循环队列 这种意义的队列 称为循环队列。 将将顺序队列的数组设想为一个首尾相接的圆环 ， 即接在arraymsize - 1之后的是
7、array0。 循环队列 0 1 2 n - 1 n msize - 1 head tail 1 n - 1 ntail head 0 msize - 1 在入队和出队操作时须对 头尾索引进行特殊处理 循环队列的入队出队操作 1 n - 1 n head 0 msize - 1 tail tail tail arraytail+ = x; if (tail =msize) tail = 0; arraytail+ = x; tail % = msize; 利用模运算 ， 则可优化为 ： 循环队列的入队出队操作 1 n - 1 n 0 msize - 1 tail head+; head % =
8、 msize; head a b c d 循环队列的队空与队满情况分析 head tail e f g h tail head 如何确定队空 还是队满呢? 循环队列的类型定义 a b cd head e f g h tail head tail count = msizecount = 0 循环队列的类型定义 a b cd head e f g h tail head tail #define msize 128 typedef struct unsigned char arraumsize; unsigned char head; unsgined char tail; Queue; #de
9、fine msize 128 typedef struct unsigned char arraumsize; unsigned char head; unsgined char count; Queue; count = msizecount = 0 有效结点数 去掉尾索引 去掉尾索引 增加结构 描述count 增加结构 描述count 循环队列的类型定义 a b cd head e f g h tail head tail #define msize 128 typedef struct unsigned char arraumsize; unsigned char head; unsgi
10、ned char tail; Queue; #define msize 128 typedef struct unsigned char arraumsize; unsigned char head; unsgined char count; Queue; count = msizecount = 0 有效结点数 u入队时，count加一 u出队时，count减一 u满队时，count等于msize u空队时，count等于0 count初始值为0 tail = head + count 队队列的逻辑结逻辑结 构和基本计计算 循环队环队 列的运算 队队列的存储结储结 构 目 录 循环队列的运算
11、 置队空 void SetNull(lpQueue * lp) lp head = 0; lp count = 0; 只要将队列的有效结点 数置为0即可置队空 习惯上也可顺便 将头索引置为0 获取有效结点长度 unsigned char GetLength(lpQueue * lp) return (lp count); 获取有效结点长度 unsigned char GetHead(lpQueue * lp) return (lp arraylp head); 获取有效结点长度 BOOL InsQueue(lpQueue * lp, unsigned char x) if (lp count msize) lp array(lp head lp count) % msize = x; lp count+; return TRUE; else return FALSE; 获取有效结点长度 出队时，将头结点的值输出 ，同时将头索引指向下一结 点, 且将有效结点数减1 unsigned char DelQueue(lpQueue * lp) unsigned char temp; if (lp count 0) temp = lp arraylp head ; lp head % = msize; lp count; return temp; else return FALSE;
