顺序队列

1、顺序队列
(1)顺序队列的定义
   队列的顺序存储结构称为顺序队列,顺序队列实际上是运算受限的顺序表。

(2) 顺序队列的表示

①和顺序表一样,顺序队列用一个向量空间来存放当前队列中的元素。
②由于队列的队头和队尾的位置是变化的,设置两个指针front和rear分别指示队头元素和队尾元素在向量空间中的位置,它们的初值在队列初始化时均应置为0。

d1

(3) 顺序队列的基本操作
①入队时:将新元素插入rear所指的位置,然后将rear加1。
②出队时:删去front所指的元素,然后将front加1并返回被删元素。
注意:
①当头尾指针相等时,队列为空。
②在非空队列里,队头指针始终指向队头元素,尾指针始终指向队尾元素的下一位置。
顺序队列基本操作【参见动画演示

(4)顺序队列中的溢出现象
① “下溢”现象
当队列为空时,做出队运算产生的溢出现象。“下溢”是正常现象,常用作程序控制转移的条件。
② “真上溢”现象
当队列满时,做进栈运算产生空间溢出的现象。“真上溢”是一种出错状态,应设法避免。
③ “假上溢”现象
由于入队和出队操作中,头尾指针只增加不减小,致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时,也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为”假上溢”现象。
【例】假设下述操作序列作用在初始为空的顺序队列上:
EnQueue,DeQueue,EnQueue,DeQueue,…
尽管在任何时刻,队列元素的个数均不超过1,但是只要该序列足够长,事先定义的向量空间无论多大均会产生指针越界错误。

2、循环队列
为充分利用向量空间,克服”假上溢”现象的方法是:将向量空间想象为一个首尾相接的圆环,并称这种向量为循环向量。存储在其中的队列称为循环队列(Circular Queue)。

d2
(1) 循环队列的基本操作
循环队列中进行出队、入队操作时,头尾指针仍要加1,朝前移动。只不过当头尾指针指向向量上界(QueueSize-1)时,其加1操作的结果是指向向量的下界0。这种循环意义下的加1操作可以描述为:
① 方法一:
if(i+1==QueueSize) //i表示front或rear
i=0;
else
i++;

② 方法二–利用”模运算”
i=(i+1)%QueueSize;

(2) 循环队列边界条件处理
循环队列中,由于入队时尾指针向前追赶头指针;出队时头指针向前追赶尾指针,造成队空和队满时头尾指针均相等。因此,无法通过条件front==rear来判别队列是”空”还是”满”。 【参见动画演示
解决这个问题的方法至少有三种:
① 另设一布尔变量以区别队列的空和满;
② 少用一个元素的空间。约定入队前,测试尾指针在循环意义下加1后是否等于头指针,若相等则认为队满(注意:rear所指的单元始终为空);
③使用一个计数器记录队列中元素的总数(即队列长度)。

(3) 循环队列的类型定义

#define Queur Size 100   //应根据具体情况定义该值
typedef char Queue DataType;  //DataType的类型依赖于具体的应用
typedef Sturet{               //头指针,队非空时指向队头元素
int front;              //尾指针,队非空时指向队尾元素的下一位置
int rear;               //计数器,记录队中元素总数
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];
}

Tagged on:

发表评论