首页 > 知识点讲解
       队列
知识路径: > 计算机科学基础 > 常用数据结构 > 队列、栈 > 
被考次数:10次     被考频率:高频率     总体答错率:45%     知识难度系数:     
相关知识点:16个      
               队列的定义
               队列(queue)是一种只允许在一端进行插入,而在另一端进行删除的线性表,是一种操作受限的线性表。在表中只允许进行插入的一端称为队尾(rear),只允许进行删除的一端称为队头(front)。队列的插入操作通常称为入队列或进队列,而队列的删除操作则称为出队列或退队列。当队列中无数据元素时,称为空队列。
               由队列的定义可知,队头元素总是最先进队列的,也总是最先出队列;队尾元素总是最后进队列,因而也是最后出队列。这种表是按照先进先出(First In First Out, FIFO)的原则组织数据的,因此,队列也被称为"先进先出"表。
               下图是一个队列的进出示意图,通常用指针front指示队头的位置,用指针rear指向队尾的位置。
               
               队列的进出示意图
               队列的基本操作
               队列的基本操作主要有以下6种。
               .InitQueue(&Q):初始化操作,构造一个队列Q。
               .QueueEmpty(Q):若栈Q为空队列,返回1,否则返回0。
               .EQueue(&Q, e):插入元素e到队列Q的尾部。
               .OQueue(&Q,&e):删除Q的队首元素,并用e返回其值。
               .GetQhead(Q,&e):用e返回Q的队首元素。
               .ClearQueue(&Q):将Q清空为空队。
               队列的顺序存储结构
               顺序存储结构采用一维数组(向量)实现,设队列头指针front和队列尾指针rear,并且假设front指向队头元素的前一位置,rear指向队尾元素。若不考虑队满,则入队操作语句为Q[rear++]=x;若不考虑队空,则出队操作语句为x=Q[++front]。当然,出队时,并不一定需要队头元素(与退栈类似)。
               按上述的做法,有可能出现假溢出,即队尾已到达一维数组的高端,不能再入队,但因为连续出队,队列中元素个数并未达到最大值。解决这种问题,可用循环队列。在循环队列中,需要区分队空和队满:仍用front=rear表示队列空,在牺牲一个单元的前提下,用front==(rear+1)% MAX表示队列满。在这种约定下,入队操作的语句为:rear=(rear+1)%MAX, MAX, Q[rear]=x;出队操作语句为:front=(front+1)% MAX。
               顺序队列的类型定义如下:
               
               顺序队列定义为一个结构类型,该类型变量有3个数据域:data、front、rear。其中data为存储队中元素的一维数组。队头指针front和队尾指针rear定义为整型变量,取值范围是0~QueueSize-1。约定队尾指针指示队尾元素在一维数组中的当前位置,队头指针指示队头元素在一维数组中的当前位置的前一个位置,这种顺序队列说明如下。
               .初始化时,设置SQ.front=SQ.rear=0。
               .队头指针的引用为SQ.front,队尾指针的引用为SQ.rear。
               .队空的条件为SQ.front==SQ.rear;队满的条件为SQ.front=(SQ.rear+1)% QueueSize。
               .入队操作:在队列未满时,队尾指针先加1(要取模),再送值到队尾指针指向的空闲元素。出队操作:在队列非空时,队头指针先加1(要取模),再从队头指针指向的队头元素处取值。
               .队列长度为(SQ.rear+QueueSize-SQ.front)% QueueSize。
               特别应注意的是:在循环队列的操作中队头指针、队尾指针加1时,都要取模,以保持其值不出界。
               在循环队列上队列的实现基本操作的函数如下。
               1)初始化initqueue(SQueue *SQ)
               
               2)判空QueueEmpty(SQueue SQ)
               
               3)入队EQueue(SQueue *SQ, ElemType e)
               
               4)出队OQueue(SQueue *SQ, ElemType *e)
               
               5)取队首元素GetQhead(SQueue *SQ, ElemType *e)
               
               6)清队列ClearQueue(SQueue *SQ)
               
               队列的链式存储结构
               队列的链接实现称为链队,链队实际上是一个同时带有头指针和尾指针的单链表。头指针指向队头节点,尾指针指向队尾节点即单链表的最后一个节点。为了简便,链队设计成一个带头节点的单链表。
               链队的类型定义如下:
               
               链队列的说明如下。
               .队列以链表形式出现,链首节点为队头,链尾节点为队尾。
               .队头指针为LQ→front,队尾指针为LQ→rear,队头元素的引用为Q→front→data,队尾元素的引用为LQ→rear→data。
               .初始化时,设置LQ→front=LQ→rear=NULL。
               .进队操作与链表中链尾插入操作一样;出队操作与链表中链首删除操作一样。
               .队空的条件为LQ→front==NULL。理论上,只要系统内存足够大,链队是不会满的。
               在链队上实现队列基本操作的函数如下。
               1)队列初始化InitQueue(LQueue *LQ)
               
               2)入队EQueue(LQueue *LQ, ElemType e)
               
               3)出队OQueue(LQueue *LQ, ElemType *e)
               
               4)判空QueueEmpty(LQueue *LQ)
               
               5)取队首元素GetQhead(LQueue *LQ, ElemType *e)
               
               6)清队列ClearQueue(LQueue *LQ)
               
               循环队列中的边界条件判别准则
               判别循环队列的"空"或"满"不能以头尾指针是否相等来确定,一般是通过以下几种方法:一是另设一个布尔变量来区别队列的空和满;二是少用一个元素的空间,每次入队前测试入队后头尾指针是否会重合,如果会重合就认为队列已满;三是设置一个计数器记录队列中元素总数,不仅可判别空或满,还可以得到队列中元素的个数。
               双端队列的作用
               双端队列是限定插入和删除操作在线性表的两端进行,可将其看成是栈底连在一起的两个栈,但其与两个栈共享存储空间是不同的。共享存储空间中的两个栈的栈顶指针是向两端扩展的,因而每个栈只需一个指针;而双端队列允许两端进行插入和删除元素,因而每个端点必须设立两个指针,如下图所示。
               
               双端队列的示意图
               在实际应用中,可对双端队列的输出进行限制(即一个端点允许插入和删除,另一个端点只允许插入),也可对双端队列的输入进行限制(即一个端点允许插入和删除,另一个端点只允许删除)。可见,采用双端队列可增加应用中的灵活性。
 
本知识点历年真题:
隶属试卷 题号/题型 题干 难度系数/错误率
   2019年上半年
   程序员
   上午试卷 综合知识
第35题
选择题
某循环队列Q的定义中用front和rear两个整型域变量表示队列状态,其中front 指示队头元素的位置、rear指示队尾元素之后的位置(如下图所示,front的值为5、rear的值为1)。若队列容量为M(下图中M=6),则计算队列长度的通式为( )。

52%
   2016年上半年
   程序员
   上午试卷 综合知识
第36题
选择题
队列采用如下图所示的循环单链表表示,图(a)表示队列为空,图(b)为e1、e2、e3依次入队列后的状态,其中,rear指针指向队尾元素所在结点,size为队列长度。以下叙述中,正确的是(36)。

57%
>>  更多  本知识点历年真题
 
 相关知识点:
 
软考在线指南
优惠劵及余额
在线支付
修改密码
下载及使用
购买流程
取消订单
联系我们
关于我们
联系我们
商务合作
旗下网站群
高级资格科目
信息系统项目管理师 系统分析师
系统架构设计师 网络规划设计师
系统规划与管理师
初级资格科目
程序员 网络管理员
信息处理技术员 信息系统运行管理员
中级资格科目
系统集成项目管理工程师 网络工程师
软件设计师 信息系统监理师
信息系统管理工程师 数据库系统工程师
多媒体应用设计师 软件评测师
嵌入式系统设计师 电子商务设计师
信息安全工程师
 

本网站所有产品设计(包括造型,颜色,图案,观感,文字,产品,内容),功能及其展示形式,均已受版权或产权保护。
任何公司及个人不得以任何方式复制部分或全部,违者将依法追究责任,特此声明。
本站部分内容来自互联网或由会员上传,版权归原作者所有。如有问题,请及时联系我们。


工作时间:9:00-20:00

客服

点击这里给我发消息 点击这里给我发消息 点击这里给我发消息

商务合作

点击这里给我发消息

客服邮箱service@rkpass.cn


京B2-20210865 | 京ICP备2020040059号-5 |京公网安备 11010502032051号 | 营业执照 | Copyright ©2000-2023 All Rights Reserved 软考在线版权所有