Question

带头尾指针的循环队列的基本操作

Answer 1

问：带头尾指针的循环队列的基本操作

答：你好，循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量上界（QueueSize-1）时，其加1操作的结果是指向向量的下界0。这种循环意义下的加1操作可以描述为： ① 方法一： if(i+1==QueueSize) //i表示front或rear i=0; else i++; ② 方法二--利用"模运算" i=(i+1)%QueueSize； （2） 循环队列边界条件处理 　 循环队列中，由于入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针，造成队空和队满时头尾指针均相等。因此，无法通过条件front==rear来判别队列是"空"还是"满"。 【 参见动画演示】 　 解决这个问题的方法至少有三种： ① 另设一布尔变量以区别队列的空和满； ② 少用一个元素的空间。约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满（注意：rear所指的单元始终为空）； ③使用一个计数器记录队列中元素的总数（即队列长度）。