数据结构 第7讲 循环队列

数据结构 第7讲 循环队列

过了一段时间,小张再也受不了这种"起早贪黑"的有车生活。为了解决胡同停车问题,小张跑了无数次居委会,终于将挡在胡同口的建筑清除,这样住在胡同尽头的小张,就可以早早回家停在家门口,每天第一个开车上班去了。

现在胡同打通了,但仍然很窄,只能通过一辆车,但是可以从一端进,另一端出,画图:

小汽车是线性排列,而且只能从一端进,另一端出,这就是"队列",队列也是一种线性表,只不过它是操作受限的线性表,只能在两端操作,先进先出(First In First Out,FIFO)。

进的一端称为队尾(rear),出的一端称为队头(front)。队列可以用顺序存储,也可以用链式存储。

1. 顺序队列

队列的顺序存储形式,可以用一个一维数组存储数据元素,用两个整型变量记录队头和队尾元素的下标。

顺序存储方式:

顺序队列的结构体定义:

2. 完美图解

接下来看看顺序队列的入队和出队情况:

假设现在顺序队列Q分配了6个空间,然后进行入队出队操作,过程如图所示:

(1) 开始时为空队,Q.front=Q.rear,如图所示:

 (2) 元素a1进队,放入尾指针Q.rear(整型下标)的位置,Q.rear后移一位,如图所示:

 (3) 元素a2进队,放入尾指针Q.rear(整型下标)的位置,Q.rear后移一位,如图所示:

(4) 元素a3,a4,a5分别按顺序进队,尾指针Q.rear依次后移,如图所示:

 (5) 元素a1出队,头指针Q.front(整型下标)后移一位,如图所示:

(6) 元素a2出队,头指针Q.front(整型下标)后移一位,如图所示:

 (7) 元素a6进队,放入尾指针rear(整型下标)的位置,rear后移一位,如图所示:

(8) 元素a7进队,此时尾指针Q.rear已经超过了数组的下标,无法再存储进队,但是我们发现前面明明有2个空间,却出现了队满的情况,这种情况称为"假溢出"。

那么如何解决该问题呢?

能否利用前面的空间继续存储入队呢?

试试看…~

上面第(7)步元素a6进队之后,尾指针Q.rear要后移一个位置,此时已经超过了数组的下标,即Q.rear+1=Maxsize(最大空间数6),那么如果前面有空闲,Q.rear可以转向前面0的位置,如图所示:

然后元素a7进队,放入尾指针Q.rear(整型下标)的位置,Q.rear后移一位,如图所示:

元素a8进队,放入尾指针Q.rear(整型下标)的位置,Q.rear后移一位,如图所示:

这时候虽然队列空间存满了,但是出现了一个大问题,队满时Q.front=Q.rear,这和队空的条件一模一样,无法区分队空还是队满,如何解决呢?有两种办法:一是设置一个标志,标记队空和队满;另一种办法是浪费一个空间,当尾指针Q.rear的下一个位置Q.front是时,就认为是队满。如图所示:

3. 循环队列

上述到达尾部又向前存储的队列称为循环队列,为了避免"假溢出",我们通常采用循环队列。

循环队列无论入队还是出队,队尾、队头加1后都要取模运算,例如入队后队尾后移一位:Q.rear =(Q.rear+1)%Maxsize。

为什么要%Maxsize呢?

主要是为了处理临界状态,即Q.rear向后移动一个位置Q.rear+1后,很有可能超出了数组的下标,这时它的下一个位置其实是0,如果将一维数组画成环形图,如图所示:

队空 队满

上图中最大空间Maxsize,当Q.rear=Maxsize-1时,(Q.rear+1)%Maxsize=0,而且Q.front=0,正好满足队满的条件:(Q.rear+1) %Maxsize= Q.front,此时为队满。

因此无论是front还是rear向后移动一个位置时,都要加1与最大空间Maxsize取模运算,处理临界问题。

总结:

队空:Q.front=Q.rear; // Q.rear和Q.front指向同一个位置

队满: (Q.rear+1) %Maxsize=Q.front; // Q.rear向后移一位正好是Q.front

入队

Q.base[Q.rear]=x; //将元素放入Q.rear所指空间,

Q.rear =( Q.rear+1) %Maxsize; // Q.rear向后移一位

出队

e= Q.base[Q.front]; //用变量记录Q.front所指元素,

Q.front=(Q.front+1) %Maxsize // Q. front向后移一位

循环队列中到底存了多少个元素呢?

因为队列是循环的,所以存在两种情况:

(1)Q.rear>= Q.front,如下图所示:

这种情况队列中元素个数为:Q.rear-Q.front=4-1=3。

(2)Q.rear< Q.front,如下图所示:

此时,Q.rear=4,Q.front=Maxsize-2,Q.rear-Q.front=6-Maxsize。但是我们可以看到循环队列中的元素实际上为6个,那怎么办呢?当两者之差为负数时,可以将差值+Maxsize计算元素个数,即:Q.rear-Q.front+Maxsize=6-Maxsize+Maxsize =6,元素个数为6。

那么在计算元素个数时,可以分两种情况判断:

  • Q.rear>= Q.front:元素个数为Q.rear-Q.front;
  • Q.rear<Q.front:元素个数为Q.rear-Q.front+ Maxsize;

也可以采用取模的方法把两种情况统一为一个语句:

队列中元素个数:(Q.rear-Q.front+Maxsize)% Maxsize

当Q.rear-Q.front为负数时,加上Maxsize再取余正好是元素个数,如(-2+6)%6=4;当Q.rear-Q.front为正数时,加上Maxsize超过了最大空间数,取余后正好是元素个数,如(3+6)%6=3。

4. 队列的基本操作

队列的基本操作包括初始化、入队、出队、取队头元素、求队列长度。

(1)初始化

//循环队列的初始化
bool InitQueue(SqQueue &Q)//注意使用引用参数,否则出了函数,其改变无效
{
	Q.base=new int[Maxsize];//分配空间
	if(!Q.base) return false;
	Q.front=Q.rear=0; //头指针和尾指针置为零,队列为空
	return true;
}

(2)入队

bool EnQueue(SqQueue &Q,int e)//将元素e放入Q的队尾

{

    if((Q.rear+1)%Maxsize==Q.front) //尾指针后移一位等于头指针,表明队满

        return false;

    Q.base [Q.rear]=e; //新元素插入队尾

    Q.rear=(Q.rear+1)%Maxsize; //队尾指针后移一位

    return true;

}

(3)出队

bool DeQueue(SqQueue &Q, int &e) //删除Q的队头元素,用e返回其值

{

    if (Q.front==Q.rear)

        return false; //队空

    e=Q.base[Q.front]; //保存队头元素

    Q.front=(Q.front+1)%Maxsize; //队头指针后移一位

    return true;

}

(4)取队头元素

int GetHead(SqQueue Q)//返回Q的队头元素,不修改队头指针

{

    if (Q.front!=Q.rear) //队列非空

        return Q.base[Q.front];

return -1;

}

(5)循环队列的长度

int QueueLength(SqQueue Q)

{

    return (Q.rear-Q.front+Maxsize)%Maxsize;

}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Jimoer

数据结构:数组、链表、栈、队列的理解

解释定义 数据结构: 数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。再简单描述一下:数据结构就是描述对象间逻辑关系的学科。 如果还是不太清楚下面会...

525100
来自专栏维C果糖

编程思想 之「对象漫谈」

在「语言导论」中,我们曾提到过「万物皆对象」,事实上,也确实如此。在面向对象编程的世界中,我们创建对象、操作对象、销毁对象,我们所做的一切动作都离不开对象。在本...

563190
来自专栏xx_Cc的学习总结专栏

iOS底层原理总结 - 探寻Runtime本质(二)

28220
来自专栏猿人谷

Effective c++ 小结

最近又重新看了Effective C+,不过到现在还是有好多地方不懂的,先记下笔记,待用的时候再细细琢磨。 条款1:尽量用const和inline而不用#def...

20350
来自专栏null的专栏

设计模式——类图以及类与类之间的关系

    设计模式在程序设计上有着很重要的作用,使用设计模式可以使得代码更容易被理解,使得代码更规范,真正实现工程化。 一、用UML表示一个类 ? 类图一般是三行...

37540
来自专栏iOS技术杂谈

iOS runtime探究(一): 从runtime开始理解面向对象的类到面向过程的结构体你要知道的runtime都在这里

你要知道的runtime都在这里 转载请注明出处 https://cloud.tencent.com/developer/user/1605429 本文主要讲解...

416120
来自专栏磐创AI技术团队的专栏

Python开发的十个Tips,你知道几个?

下面是十个Python中很有用的贴士和技巧。其中一些是初学这门语言常常会犯的错误。

10220
来自专栏恰童鞋骚年

正则表达式30分钟入门教程--deerchao

原文地址:http://www.cnblogs.com/deerchao/archive/2006/08/24/zhengzhe30fengzhongjiaoc...

30040
来自专栏老司机的简书

老司机出品——源码解析之从Block说开去

近来把《iOS与OS X多线程和内存管理》这本书又掏出来看了一遍,这本书前前后后加起来看了能有三四遍了,每次看都有新的理解。现在就把个人对Block的一些理解记...

11230
来自专栏菩提树下的杨过

Flash/Flex学习笔记(8):ActionScript3.0中的面对对象

首先要习惯AS3.0的几个BT约定: 1.一个.as文件中,只能定义一个类 2.类名称必须与.as的文件名相同 3.类定义中必须要有package包声明 4.一...

18690

扫码关注云+社区

领取腾讯云代金券