新浪博客

3.2.2 队列的顺序存储结构及其基本运算的实现

2016-10-10 18:37阅读：

http://blog.sina.cn/dpool/blog/u/3702337543

3.2.2 队列的顺序存储结构及其基本运算的实现
顺序队类型SqQueue定义如下：
1. typedef struct{
2. ElemType data[MaxSize];
3. int front,rear; //队首和队尾指针
4. }SqQueue;
因为队列两端都在变化，所以需要两个指针来表示队列的状态。
顺序队列的示意图
3.2.2 <wbr>队列的顺序存储结构及其基本运算的实现
例如：MaxSize=5
3.2.2 <wbr>
队列的顺序存储结构及其基本运算的实现' />
总结：
①　约定rear总是指向队尾元素
②　元素进队，rear增1
③　约定front指向当前队中对头元素的前一位置
④　元素出队，front增1
⑤　当rear=MaxSize-1时不能再进队
队列的各种状态
3.2.2 <wbr>队列的顺序存储结构及其基本运算的实现
顺序队的4要素（初始时front=rear=-1）：
①　队空条件：front=rear
②　队满条件：rear=MaxSize-1
③　元素e进队：rear++；data[rear]=e；
④　元素e出队：front++；e=data[front];
1 顺序队中实现队列的基本运算
（1）初始化队列InitQueue（&q）
构造一个空队列q。将front和rear指针均设置成初始状态即-1值。
1. void InitQueue(SqQueue *&q){
2. q=(SqQueue *)malloc(sizeof(SqQueue));
3. q->front=q->rear=-1;
4. }

（2）销毁队列DestroyQueue（&q）
释放队列q占用的存储空间。
1. void DestroyQueue(SqQueue *&q){
2. free(q);
3. }

（3）判断队列是否为空QueueEmpty（q）
若队列q满足q->front==q->rear条件，则返回true；否则返回false。
1. void QueueEmpty(SqQueue *q){
2. return (q->front==q->rear);
3. }

（4）enQueue（&q，e）：进队列。将元素e进队作为队尾元素。
若队列不满，将队尾指针rear增1，然后将元素添加到该位置。
1. bool enQueue(SqQueue *&q,ElemType e){
2. if(q->rear==MaxSize) return false; //队满上溢
3. q->rear++;
4. q->data[q->rear]=e;
5. return true;
6. }

（5）出队列deQueue（&q，&e）
若队列不为空，将队首指针rear增1，并将该位置的元素赋给e。
1. bool deQueue(SqQueue *&q,ElemType &e){
2. if(q->front==q->rear) return false;
3. q->front++;
4. e=q->data[q->front];
5. return true;
6. }

2 环形队列（或循环队列）中实现队列的基本运算
思考：
3.2.2 <wbr>队列的顺序存储结构及其基本运算的实现
这是因为采用rear==MaxSize-1作为队满条件的缺陷。当队满条件为真时，队中可能还有若干空位置。这种溢出并不是真的溢出，称为假溢出。
解决方案
把数组的前端和后端连接起来，形成一个环形的顺序表，即把存储队列元素的表从逻辑上看成一个环，称为环形队列或循环队列。
例如：
3.2.2 <wbr>队列的顺序存储结构及其基本运算的实现
实际上内存地址一定是连续的，不可能是环形的，这里是通过逻辑方式实现环形队列，也就是将rear++和front++改为：
①　rear=（rear+1）%MaxSize
②　front=（front+1）%MaxSize




循环队列的各种状态
3.2.2 <wbr>队列的顺序存储结构及其基本运算的实现
现在约定rear=front为队空，一下两种情况都满足该条件：
3.2.2 <wbr>队列的顺序存储结构及其基本运算的实现
让rear=front为队空条件，并约定（rear+1）%MaxSize=front为队满条件。（进队一个元素时到达队头，就认为队满了。这样做会少放一个元素，牺牲一个元素没关系的。）
环形队列的4要素：
③　队空条件：front=rear
④　队满条件：（rear+1）%MaxSize=front
⑤　进队e操作：rear=（rear+1）%MaxSize；将e放在rear处；
⑥　出队操作：front=（front+1）%MaxSize；取出front处元素e；
在环形队列中，实现队列的基本运算算法与非环形队列类似，只是改为上述4要素即可。
【例 3-5】对于环形队列来说，如果知道对头指针和队列中元素个数，则可以计算出队尾指针。也就是说，可以用队列中元素个数代替队尾指针。设计出这种环形队列的初始化、入队、出队和判空算法。
已知front、rear，求队中元素个数count=？
MaxSize=5
3.2.2 <wbr>队列的顺序存储结构及其基本运算的实现
由此可以推断出
①　已知front、rear，求队中元素个数count：
count=（rear-front+MaxSize）%MaxSize
②　已知front、count，求rear：
Rear=（front+count）%MaxSize
③　已知rear、count，求front：
front=（rear-count+MaxSize）%MaxSize
解：依题意设计的环形队列类型如下：
1. typedef struct {
2. ElemType data[MaxSize];
3. int front; //队头指针
4. int count; //队列中元素个数
5. }QuType;
该循环队列的4要素：
①　队空条件：count=0
②　队满条件：count=MaxSize
③　进队e操作：rear=（rear+1）%MaxSize；将e放在rear处；
④　出队操作：front=（front+1）%MaxSize；取出front处的元素e；
注意：这样的循环队列中最多可以放置MaxSize个元素。
对应算法如下：

1. void InitQueue(QuType *&qu) //初始化队运算算法
2. {
3. qu=(QuType *)malloc(sizeof{QuType});
4. qu->font=0;
5. qu->count=0;
6. }
7.
8. bool enQueue(QuType *&qu,ElemType e) //进队算法

我的更多文章

下载客户端阅读体验更佳

APP专享