循环队列
为充分利用向量空间,克服"假溢出"现象的方法是:将向量空间想象为一个首尾相接的圆环,并称这种向量为循环向量。存储在其中的队列称为循环队列(Circular Queue)。
(1) 循环队列的基本操作
插入新元素;
PASCAL语言:
procedure Add2(var q:equeue;x:qtype;var r:integer);
begin
r=t mod m+1;
if t=f then writeln('full')
else begin
r=t;q[r]=x;
end;
end;
过程DEL2(Q,Y,F)从循环队列q中取出队首元素
procedure del2(var q:equeue; var y:qtype; var f:integer);
begin
if f=r then writeln('empty')
else begin
f=f mod m+1;y=q[f];
end;
end;
(2) 循环队列边界条件处理
循环队列中,由于入队时尾指针向前追赶头指针;出队时头指针向前追赶尾指针,造成队空和队满时头尾指针均相等。因此,无法通过条件front==rear来判别队列是"空"还是"满"。 【参见动画演示】
解决这个问题的方法至少有三种:
① 另设一布尔变量以区别队列的空和满;
② 少用一个元素的空间。约定入队前,测试尾指针在循环意义下加1后是否等于头指针,若相等则认为队满(注意:rear所指的单元始终为空);
③使用一个计数器记录队列中元素的总数(即队列长度)。
(3) 循环队列的类型定义
#define Queur Size 100 //应根据具体情况定义该值
typedef char Queue DataType; //DataType的类型依赖于具体的应用
typedef Sturet{
int front; //头指针,队非空时指向队头元素
int rear; //尾指针,队非空时指向队尾元素的下一位置
int count//计数器,记录队中元素总数
DataType data[QueueSize]
}CirQueue;
(4) 循环队列的基本运算
用第三种方法,循环队列的六种基本运算:
① 置队空
void InitQueue(CirQueue *Q)
{
Q->front=Q->rear=0;
Q->count=0; //计数器置0
}
② 判队空
int QueueEmpty(CirQueue *Q)
{
return Q->count==0; //队列无元素为空
}
③ 判队满
int QueueFull(CirQueue *Q)
{
return Q->count==QueueSize; //队中元素个数等于QueueSize时队满
}
④ 入队
void EnQueue(CirQueuq *Q,DataType x)
{
if(QueueFull((Q))
Error("Queue overflow"); //队满上溢
Q->count ++; //队列元素个数加1
Q->data[Q->rear]=x; //新元素插入队尾
Q->rear=(Q->rear+1)%QueueSize; //循环意义下将尾指针加1
⑤ 出队
DataType DeQueue(CirQueue *Q)
{
DataType temp;
if(QueueEmpty((Q))
Error("Queue underflow"); //队空下溢
temp=Q->data[Q->front];
Q->count--; //队列元素个数减1
Q->front=(Q->front+1)&QueueSize; //循环意义下的头指针加1
return temp;
}
⑥取队头元素
DataType QueueFront(CirQueue *Q)
{
if(QueueEmpty(Q))
Error("Queue if empty.");
return Q->data[Q->front];
}
````````````````````````````````````````````````````````````````````````````````````
队列的操作特点是“先进先出”。队列的存储结构包括链队列和顺序队列。前者主要是头指针、尾指针的使用,后者主要是理解循环队列提出的原因及其特点。两者都要掌握队列空与满的判定条件以及出队列、入队列操作的实现。