数据结构 | 您所在的位置:网站首页 › 循环队列元素个数怎么确定 › 数据结构 |
队列定义是这样的 #define MAXSIZE 10 typedef struct{ ElemType data[MAXSIZE]; int front,rear; } SeqQueue;一个队列 = 一个存放元素的数组 + 一个队头指针 + 一个队尾指针 front:控制出队 rear:控制入队 我们先做个规定: front指向队头元素 rear指向队尾元素的下一个元素(当然也可以让它直接指向队尾元素,只是在某些代码上需要相应的改动,但思想不变) 初始我们让rear = front = data[0] 元素出队:front++ 元素入队:rear++ 一直rear++便到达索引最大的位置,这个时候队列就满了不能再入队元素了吗? 并不,如果同时也一直有元素出队,那么还是有空闲位置可以继续入队的,那要怎么表示呢? 于是就出现了循环队列,这个类比时钟就很好理解 时钟的指针到达12之后就会归0,周而复始再次循环 所以出入队指针的变化就可以表示成 元素出队:(front+1)% maxSize 元素入队:(rear+1)% maxSize 那此时的队列的长度怎么获取呢? 那就不是单纯的rear - front了,看图 +maxSize:目的是防止rear - front < 0 %maxSize:目的是防止当rear - front > 0时,又+ maxSize导致队列长度>maxSize 回答一下评论中的问题 为什么会rear - front < 0? 一个队列的初始状态如下图 |
CopyRight 2018-2019 实验室设备网 版权所有 |