Question

为什么循环队列队满的是(rear+1)%max_queue_size=front不可以是rear.next=front

Answer 1

队列是一种特殊的表，因此凡是可以用来实现表的数据结构都可以用来实现队列。不过，队列的中的元素的个数通常不固定，因此常用循环数组和链表两种方法实现队列。

链队列：

用指针实现队列得到的实际上是一个单链表。由于入队在队尾进行，所以用一个指针来指示队尾可以使入队操作不必从头到尾检查整个表，从而提高运算的效率。另外，指向队头的指针对于Gethead和Dequeue运算也是必要的。为了便于表示空队列，我们仍使用一个表头单元，将队头指针指向表头单元。当队头和队尾指针都指向表头单元时，表示队列为一个空队列。

用指针实现队列时，单元类型及队列类型可说明如下:

type

queueptr=^queuenode;

queuenode=record

data:elemtp;

next:queueptr;

end;

linkedquetp=record

front,rear:queueptr;

end;

其中front为队头指针，rear为队尾指针。图2是用指针表示队列的示意图。

图2

面我们来讨论队列的5种基本运算。

函数 Gethead(Q)

功能

这是一个函数，函数值返回队列Q的队头元素。

实现

Function Gethead(var Q:linkedquetp):elemtp;

begin

if Empty(Q) then error('The queue is empty!')

else return(Q.front^.next^.data);

end;

函数 Enqueue(Q,x)

功能

将元素x插入队列Q的队尾。此运算也常简称为将元素x入队。

实现

Procedure Enqueue(x:elemtp;var Q:linkedquetp);

begin

new(Q.rear^.next);

Q.rear:=Q.rear^.next;

Q.rear^.data:=x;

Q.rear^.next:=nil;

end;

函数 Empty(Q)

功能

这是一个函数，若Q是一个空队列，则函数值为true，否则为false。

实现

Function Empty(var Q:QueueType):Boolean;

begin

return(Q.front=Q.rear);

end;

函数 Dequeue(Q)

功能

将Q的队头元素删除，简称为出队。

实现

Procedure Dequeue(var Q:linkedquetp);

var

p:queueptr;

begin

if Empty(Q) then Error('The queue is empty!')

else begin

p:=Q.front;

Q.front:=Q.front^.next;

dispose(p);

end;

end;

函数 Clear(Q)

功能

使队列Q成为空队列。

实现

Procedure clear(var Q:linkedquetp);

begin

Q.rear:=Q.front;

while Q.front<>nil do

begin

Q.front:=Q.front^.next;

dispose(Q.rear);

Q.rear:=Q.front;

end;

new(Q.front);

Q.front^.next:=nil;

Q.rear:=Q.front;

end;

循环队列：

我们可以将队列当作一般的表用数组实现，但这样做的效果并不好。尽管我们可以用一个游标last来指示队尾，使得Enqueue运算可在O(1)时间内完成，但是在执行Dequeue时，为了删除队头元素，必须将数组中其他所有元素都向前移动一个位置。这样，当队列中有n个元素时，执行Dequeue就需要O(n)时间。为了提高运算的效率，我们用另一种方法来表达数组中各单元的位置关系。设想数组中的单元不是排成一行，而是围成一个圆环 ，我们将队列中从队头到队尾的元素按顺时针方向存放在循环数组中一段连续的单元中。当需要将新元素入队时，可将队尾游标Q.rear按顺时针方向移一位，并在新的队尾游标指示的单元中存入新元素。出队操作也很简单，只要将队头游标Q.front依顺时针方向移一位即可。容易看出，用循环数组来实现队列可以在O(1)时间内完成Enqueue和Dequeue运算。执行一系列的入队与出队运算，将使整个队列在循环数组中按顺时针方向移动。通常，用队尾游标Q.rear指向队尾元素所在的单元，用队头游标Q.front指向队头元素所在单元的前一个单元，并且约定只能存放maxsize-1个元素如图3所示。

图3

此时队列的定义如下：

const m=maxsize-1

type cyclicquetp=record

elem:array[0..m] of elemtp;

rear,front:0..m;

end;

var sq:cyclicquetp;

这时 当 sq.rear=sq.front 时队空 当 (sq.rear+1) mod maxsize=sq.front 时队满

先 sq.rear=( sq.rear+1) mod maxsize 后进队

先 sq.front=（sq.front+1）mod maxsize 后出队

队列中元素的个数（sq.rear-sq.front+maxsize) mod maxsize

Answer 2

另一种方式就是数据结构常用的： 队满时：(rear+1)%n==front，n为队列长度（所用数组大小），由于rear，front均为所用空间的指针，循环只是逻辑上的循环，所以需要求余运算。如图情况，队已满，但是rear（5）+1=6！=front（0），对空间长度求余，作用就在此6%6=0=front（0）。

http://baike.baidu.com/view/203647.htm
去链接里仔细看看图

追问

那为什么不可以是rear.next=front,还有rear（5）+1为什么等于6！为什么等于front（0），循环只是逻辑上的循环是什么意思

追答

....看图没呀...
循环队列说白了就是个数组,只不过当到达队尾时,让它回到队头.
还有这是定义
　typedef struct{
　　int front; //头指针，队非空时指向队头元素
　　int rear; //尾指针，队非空时指向队尾元素的下一位置
　　int count;//计数器，记录队中元素总数
　　DataType data[QueueSize];
　　}CirQueue;
根本没有rear.next这个好不....
如图数组是 0 1 2 3 4 5
rear此时为5,那rear+1不就是6了....然后长度为6,所以求余为0呀,就是队头

追问

rear此时为5为什么是5，　int rear; //尾指针，队非空时指向队尾元素的下一位置，那怎么不是6，
还有数组是1 2 3 4 5 6，rear此时为多少呢

追答

数组的下标从0开始，如果一个数组0 1 2 3 4 5，数组长度n=6
这时rear不能是6，因为就没有开辟空间到六，所以当rear要指向6时，就让他返回到0,这次才是循环麻。
所以每次入队时，都要判断下rear+1是否为n，如果相等就入队，然后令rear=0.不相等就令rear+1
但这个缺点就是即使rear==front，也不能说明队是空还是满
所以用了2种办法来解决，其中一个办法就是设一个空位，就比入说这个数组A 0 1 2 3 4 5
A[5]就不能存储数据，所以rear可以等于5,因为下标是从0开始的，所以当(rear+1)%n==front时，队为满。若rear=front时为空

追问

int rear; //尾指针，队非空时指向队尾元素的下一位置
问下那为什么元素x入队列，rear指向x，而不是x得下一个位置

追答

就是指向x的下一个呀，比如说数组有5个就是
0 1 2 3 4
a b c
f r
0,1,2有a,b,c。front指向0,rear指向3
0 1 2 3 4
a b c x
f r
x入队就变成这样了,这就是队满了，因为设定的就是最后一位不能放

追问

你有QQ吗？可以给我吗？我发图片给你看，这个发不了图片

追答

453508335