本文共 644 字,大约阅读时间需要 2 分钟。
入队,出队操作原理:
由于队列的队头和队尾的位置是变化的,因而要设两个指针和分别指示队头和队尾元素在队列中的位置,它们的初始值地队列初始化时均应置为0。入队时将新元素插入所指的位置,然后将加1。出队时,删去所指的元素,然后将加1并返回被删元素。
杜绝“假上溢”:
和栈类似,队列中亦有上溢和下溢现象。此外,顺序队列中还存在“假上溢”现象。因为在入队和出队的操作中,头尾指针只增加不减小,致使被删除元素的 空间永远无法重新利用。因此,尽管队列中实际的元素个数远远小于向量空间的规模,但也可能由于尾指针巳超出向量空间的上界而不能做入队操作。
为充分利用向量空间。克服上述假上溢现象的方法是将向量空间想象为一个首尾相接的圆环,并称这种向量为循环向量,存储在其中的队列称为循环队列(Circular Queue)。在循环队列中进行出队、入队操作时,头尾指针仍要加1,朝前移动。只不过当头尾指针指向向量上界(QueueSize-1)时,其加1操作的结果是指向向量的下界0。
判断循环队列是否为空(rear=front)
判断循环队列是否为满(解决这个问题有两个办法:一是增加一个参数,用来记录数组中当前元素的个数;第二个办法是,少用一个存储空间,也就是数组的最后一个存数空间不用,当(rear+1)%maxsiz=front时,队列满;)。
转载地址:http://yutmi.baihongyu.com/