读书频道 > 网站 > 网页设计 > 新编数据结构习题与解析
4.1.1 要点归纳
13-06-04    奋斗的小年轻
收藏    我要投稿   

本文所属图书 > 新编数据结构习题与解析

作者长期从事程序设计语言和数据结构课程的基础教学工作,本书是在总结这些教学经验的基础上编写而成,全书分为12章,包括绪论、线性表、栈和队列、串、数组和稀疏矩阵、递归、树形结构、广义表、查找、内排序、...立即去当当网订购
4.1  知识点1:队列的基本概念
4.1.1  要点归纳
1. 队列的定义
队列简称队,如图4.1所示,它也是一种运算受限的线性表,其限制仅允许在表的一端进行插入,而在表的另一端进行删除。通常把进行插入的一端称做队尾(rear),进行删除的一端称做队首或队头(front)。向队列中插入新元素称为进队或入队,新元素进队后就成为新的队尾元素;从队列中删除元素称为出队或离队,元素出队后,其后继元素就成为队首元素。

图4.1  队列示意图
2. 队列的特点
队列的主要特点是“先进先出”,即先进队的元素先出队。队列也称为先进先出表。
3. 队列的基本运算
队列的基本运算如下。
InitQueue(&q):初始化队列。构造一个空队列q。
QueueEmpty(q):判断队列是否为空。若队列q为空,则返回真;否则返回假。
EnQueue(&q,x):入队运算。将元素x入队作为队尾元素。
DeQueue(&q,&x):出队运算。从队列q中出队一个元素,并将其值赋给x。
 
4. 队列的存储结构
队列有两种主要的存储结构,即顺序队和链队。前者采用顺序存储结构实现队列,后者采用链式存储结构实现队列,它们之间的区别与第2章介绍的顺序表和链表类似。
5. 双端队列
所谓双端队列是指两端都可以进行进队和出队操作的队列,如图4.2所示,将队列的两端分别称为前端和后端,两端都可以入队和出队。其元素的逻辑结构仍是线性结构。
在双端队列进队时,前端进的元素排列在队列中后端进的元素的前面,后端进的元素排列在队列中前端进的元素的后面。在双端队列出队时,无论前端出还是后端出,先出的元素排列在后出的元素的前面。

图4.2  一个双端队列
例如,有a、b、c、d元素进队,能否通过双端队列产生dacb的出队序列呢?答案是肯定的。其操作方式为:a后端进,b后端进,c后端进,d前端进,此时队中元素为dabc,d前端出,a前端出,c后端出,b前端出,便可以得到这样的出队序列。
实际上,从图4.2的双端队列可以看出,从后端进前端出或者从前端进后端出体现先进先出的特点,从前端进前端出或后端进后端出体现出后进先出的特点。
在实际使用中,还可以有输出受限的双端队列(即一个端点允许插入和删除,另一个端点只允许插入的双端队列)和输入受限的双端队列(即一个端点允许插入和删除,另一个端点只允许删除的双端队列),前者如图4.3所示,后者如图4.4所示。而如果限定双端队列从某个端点插入的元素只能从该端点删除,则该双端队列就蜕变为两个栈底相邻的栈了。
   
          图4.3  一个输出受限的双端队列                图4.4  一个输入受限的双端队列
点击复制链接 与好友分享!回本站首页
分享到: 更多
您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力  
上一篇:1.3 功能
下一篇:1.5 小结
相关文章
图文推荐
JavaScript网页动画设
1.9 响应式
1.8 登陆页式
1.7 主题式
排行
热门
文章
下载
读书

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训
版权所有: 红黑联盟--致力于做最好的IT技术学习网站