队列是一种特殊的线性表,它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作。进行插入操作的端称为队尾,进行删除操作的端称为队头。队列中没有元素时,称为空队列。
在
队列这种
数据结构中,最先插入在元素将是最先被删除;反之最后插入的元素将最后被删除,因此队列又称为“先进先出”(FIFO—first
in first out)的线性表。
队列满的条件: rear = MAXSIZE
队列可以用
数组Q[1…m]来存储,数组的
上界m即是队列所容许的最大容量。在
队列的运算中需设两个
指针:head,队头指针,指向实际队头元素的前一个位置;tail,队尾指针,指向实际队尾元素所在的位置。一般情况下,两个
指针的初值设为0,这时队列为空,没有元素。图1
( a)画出了一个由6个元素构成的队列,
数组定义Q[1…10]。Q(i) i=3,4,5,6,7,8头
指针head=2,尾指针tail=8。队列中拥有的元素个数为:L=tail-head现要让排头的元素出队,则需将头指针加1。即head=head+1这时头指针向上移动一个位置,指向Q(3),表示Q(3)已出队。见图1
(b)。如果想让一个新元素入队,则需尾
指针向上移动一个位置。即tail=tail+1这时Q(9)入队。当队尾已经处理在最上面时,即tail=10,如果还要执行入队操作,则要发生"上溢",但实际上队列中还有三个空位置,所以这种溢出称为"
假溢出"。
克服
假溢出的方法有两种。一种是将
队列中的所有元素均向低地址区移动,显然这种方法是很浪费时间的;另一种方法是将
数组存储区看成是一个首尾相接的环形区域。当存放到n地址后,下一个地址就"翻转"为1。在结构上采用这种技巧来存储的队列称为
循环队列。
循环队的入队算法如下:
1、tail=tail+1;
2、若tail=n+1,则tail=1;
3、若head=tail尾
指针与头指针重合了,表示元素已装满队列,则作上溢出错处理;
4、否则,Q(tail)=X,结束(X为新入出元素)。
队列和栈一样,有着非常广泛的应用。
2队列的基本运算编辑
(1)初始化队列 Qini (Q)
(2)入队 QADD(Q,X)
(3)出队 QDel(Q,X)
(5)判断队列是否为满qfull(Q)
3C++中的应用编辑
语法
queue类是为程序员提供了一个队列的功能的容器适配器,具体而言,一个FIFO(先入先出)的数据结构
在头文件<queue>中定义。
原型
template<
class T,
class Container =std::deque<T>
> class queue;
成员函数
-
empty()判断队列空,当队列空时,返回true。
-
size()访问队列中的元素个数。
-
push()会将一个元素置入queue中。
-
front()会返回queue内的第一个元素(也就是第一个被置入的元素)。
-
back()会返回queue中最后一个元素(也就是最后被插入的元素)。
-
-
注意:pop()虽然会移除下一个元素,但是并不返回它,front()和back()返回下一个元素但并不移除该元素。
分享到:
相关推荐
心希盼 C++ STL Queue(队列)
STL、线段树代码库 关于队列和栈的有关STL的操作vc++实现
STL的Vector、List、deque、set、map、queue、stack等的使用,包含了基本的用法
stl容器queue的使用 包含6.0代码 以及详细的文档说明
【STL源代码】中包含了许多常用的数据结构(如vector、list、map等)和算法(如排序、查找、遍历等)。通过阅读代码可以仔细研究这些数据结构和算法的实现,了解它们的内部工作原理和使用方式。
stl-queue.cpp
priority_queue用法,希望对大家会有所帮助
c++中常用模板库头文件及其源代码,例如<stl_queue.h>,<stl_vector.h>,<stl_map.h>等
C++实现STL容器之queue
在c++中如何使用STL里的stack,queue,vector,里面有常用操作还有示意
主要介绍了 STL priority_queue(优先队列)详解的相关资料,需要的朋友可以参考下
C++资料 STL SATCK QUEUE,对于喜欢c++的人会有以帝国的参考作用
acm中常用的STL。vector、set、map、string、priority-queue、list、bitset等含详细代码以及注释。
STL容器部分主要由头文件、、、、、和<queue>组成。 (2)算法(Algorithms)。包括各种基本算法,如比较、交换、查找、排序、遍历操作、复制、修改、移除、反转、合并等等。 STL算法部分主要由头文件和组成。 ...
sgi stl 内部文件(sgi stl真正实现于此) 018 1.8.3 sgi stl 的组态设定(configuration) 019 1.9可能令你困惑的c++ 语法 026 1.9.1 stl_config.h 中的各种组态 027 组态3:static template member 027 组态5...
第一篇 预备知识 第1章 C++编程技术 2 1.1 类和对象 2 1.2 类的继承 5 1.3 函数重载 5 1.4 访问控制 7 1.5 操作符重载 8 1.6 显式类型转换 9 1.7 异常处理 13 ...附录 STL版权说明 438
组成的库来说提供了更好的代码重用机会。在C++标准中,STL被组织为下面的几个头文件:、、、、、、、、、、<queue>、、和。文件中主要介绍了前面八个的使用,并且重点介绍了他们的属性和一些成员函数的使用。
STL 源码解析,纯c++代码,对于希望了解STL里各个容器(如map,set, vector, queue等)的实现原理有很大帮助,希望能帮到大家。
STL(Standard Template Library,标准模板库)是惠普实验室开发的一系列软件的统称。现然主要出现在C++中,但在被引入C++之前该...在C++标准中,STL被组织为下面的13个头文 件:、、、、、、、、、<queue>、、 和。
# The following STL containers are currently supported: # # std::vector<T> -- via pvector command # std::list<T> -- via plist or plist_member command # std::map,T> -- via pmap or pmap_member command #...