Question

■数据结构的一道题

利用大小为N的数组顺序存贮一个队列时,该队列的最大长度是?
请说名原因

Answer 1

为N-1, 因为队列需要设置成循环队列，所以必须有一个空格来区分队列的头和尾的分界线。
举个例子：一个长度为4的数组做循环队列，现在插入1，2，3，4四个数字：
作为队列，需要两个指针：队头指针head和队尾指针tail。初始的时候（队空），这两个指针是重合的，假设都指向a[1]位置。如下
a[0] = null
a[1] = null<-- head(tail)
a[2] = null
a[3] = null
每插入一个值，tail指针向后移一个，每删除一个值，队头指针向“前”移动一个。那么插入1，2，3三个数以后，队列的情况如下：
a[0] = null <-- tail
a[1] = 1 <-- head
a[2] = 2
a[3] = 3
如果现在插入4会出现什么情况？
a[0] = 4
a[1] = 1 <--head(tail)
a[2] = 2
a[3] = 3
队头指针和队尾指针再次重合！但是从第一步我们可以知道，队空的标志正是head和tail两个指针重合（事实上这也正是我们判断队列是否为空的标准）。这样的话，队满和队空的标志是一样的，这时不可接受的。
因此一个长度为N的数组来作为循环队列的话，队列的长度最长只能为N-1, 队空标志是head和tail重合，队满标志是tail在head“前”一位。

Answer 2

yesterday2651分析得很有道理,不过如果增加一个标志变量,用来区分head和tail重合时,队列是空还是满的话,结果就是N了.

Answer 3

为N，
每个数组元素存储一个队列元素，当然，这个队列需要设置成循环队列！