为什么循环队列队满的是(rear+1)%max_queue_size=front不可以是rear.next=front
发布网友
发布时间：2022-04-18 18:00
共2个回答
热心网友
时间：2022-04-18 19:29
链队列：
用指针实现队列得到的实际上是一个单链表。由于入队在队尾进行，所以用一个指针来指示队尾可以使入队操作不必从头到尾检查整个表，从而提高运算的效率。另外，指向队头的指针对于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入队。
实现
Procere 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的队头元素删除，简称为出队。
实现
Procere 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成为空队列。
实现
Procere 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
热心网友
时间：2022-04-18 20:47
http://ke.baidu.com/view/203647.htm
去链接里仔细看看图
