Question

循环队列元素个数的计算方法

Answer 1

循环队列元素个数的计算方法指的是队列的实现方式，用一个头尾相接的循环链表，或者逻辑上头尾相接的数组（读取最后一个元素的下一个元素时会跳转到第一个元素）。

顺序队列在使用过程中容易出现虚假的满状态， 为了解决这个问题，就产生了一个较巧妙的方法，将顺序队列臆造为一个环状的空间，称之为循环队列。

循环队列中指针和队列元素之间的关系不变，我们只需要利用模运算就可以很容易实现指针的循环移动。但是循环队列中存在一个问题，在循环队列中只凭头指针front等于尾指针rear无法判别队列空间是“空”还是“满”。

可有两种处理方法：其一是另设一个标志位以区别队列是“空”还是“满”。其二是少用一个元素空间，约定以“队列头指针在队列尾指针的下一位置(指环状的下一位置)上”作为队列呈“满”状态的标志。此处使用方法二来解决这个问题。