队列的顺序存储及循环队列
1.队列的顺序存储
队列的顺序实现是指分配一块连续的存储单元存放队列中的元素,并附设两个指针front 和rear分别指示队头元素和队尾元素的位置。设队头指针指向队头元素,队尾指针指向队尾 元素的下一个位置(也可以让rear指向队尾元素,front指向队头元素的前一个位置,对于 这种设置方法,请读者以图3-6为例思考出队和入队后这两个指针的变化)。图3-6 队列的操作
队列的顺序存储类型可描述为:
#define MaxSize 50 //定义队列中元素的最大个数 typedef struct{ ElemType data[MaxSize]; //存放队歹I]元素 int front, rear; //队头指针和队尾指针 }SqQueue;
初始状态(队空条件):Q.front==Q.rear==0。
进队操作:队不满时,先送值到队尾元素,再将队尾指针加1。
出队操作:队不空时,先取队头元素值,再将队头指针加1。
如图3-6 (a)所示为队列的初始状态,有Q.front==Q.rear==0成立,该条件可以作为队 列判空的条件。但能否用Q.rear==MaxSize作为队列满的条件呢?显然不能,图3-6(d)中, 队列中仅有1个元素,但仍满足该条件。这时入队出现“上溢出”,但这种溢出并不是真正 的溢出,在data数组中依然存在可以存放元素的空位置,所以是一种“假溢出”。
2.循环队列
前面已指出了顺序队列的缺点,这里我们引出循环队列的概念。将顺序队列臆造为一个 环状的空间,即把存储队列元素的表从逻辑上看成一个环,称为循环队列。当队首指针Q.ftont =MaxSiZe-1后,再前进一个位置就自动到0,这可以利用除法取余运算(%)来实现。初始时:Q.front=Q.rear=0
队首指针进 1:Q.front=(Q.front+1)%MaxSize
队尾指针进 1:Q.rear=(Q.rear+1)%MaxSize
队列长度:(Q.rear+MaxSize-Q.front)%MaxSize
出队入队时:指针都按顺时针方向进1 (如图3-7所示)。
那么,循环队列队空和队满的判断条件是什么呢?显然,队空的条件是Q.front==Q.rear。 如果入队元素的速度快于出队元素的速度,队尾指针很快就赶上了队首指针,如图3-7(d1),此时可以看出队满时也有Q.front==Q.rear。循环队列出入队示意图如图3-7所示。
图3-7 循环队列出入队示意图
为了区分队空还是队满的情况,有三种处理方式:
1) 牺牲一个单元来区分队空和队满,入队时少用一个队列单元,这是一种较为普遍的 做法,约定以“队头指针在队尾指针的下一位置作为队满的标志”,如图3-7(d2)所示。
队满条件为:(Q.rearfl)%MaxSize==Q.front。
队空条件仍为:Q.front==Q.rear。
队列中元素的个数:(Q.rear-Q.front+MaxSize)%MaxSize
2) 类型中增设表示元素个数的数据成员。这样,则队空的条件为Q.Size==0,队满的条 件为 Q.size==MaxSize。这两种情况都有 Q.front=Q.rear。
3) 类型中增设tag数据成员,以区分是队满还是队空。tag等于0的情况下,若因删除导 致Q.front==Q.rear则为队空;tag等于1的情况下,若因插入导致Q.ftont==Q.rear则为队满。
3.循环队列的操作
1) 初始化void InitQueue(&Q){ Q.rear=Q.front=0; //初始化队首、队尾指针 }
2) 判队空
bool isEmpty(Q) { if(Q.rear == Q.front) return true; //队空条件 else return false; }
3) 入队
bool EnQueue(SqQueue &Q, ElemType x){ if((Q.rear+1)%MaxSize == Q.front) return false; //队满 Q.data[Q.rear]=x; Q.rear= (Q.rear+1)%MaxSize; //队尾指针加 1 取模 return true; }
4) 出队
bool DeQueue(SqQueue &Q, ElemType &x){ if(Q.rear == Q.front) return false; //队空,报错 x=Q.data[Q.front]; Q.front= (Q.front+1)%MaxSize; //队头指针加 1 取模 return true; }