C++数据结构 |
您所在的位置:网站首页 › 队列排列队形 › C++数据结构 |
C++数据结构——队列
参考博客: 数据结构图文解析之:队列详解与C++模板实现 C++ stl队列Queue用法介绍:删除,插入等操作代码举例
1、队列(Queue)与栈一样,是一种线性存储结构,它具有如下特点: (1)队列中的数据元素遵循“先进先出”(First In First Out)的原则,简称FIFO结构; (2)在队尾添加元素,在队头删除元素。 2、队列的相关概念: (1)队头与队尾: 允许元素插入的一端称为队尾,允许元素删除的一端称为队头; (2)入队:队列的插入操作; (3)出队:队列的删除操作。 3、队列的操作: (1)入队: 通常命名为push() (2)出队: 通常命名为pop() (3)求队列中元素个数 (4)判断队列是否为空 (5)获取队首元素 4、队列的分类: (1)基于数组的循环队列(循环队列) (2)基于链表的队列(链队列) 5、实例分析 C++队列queue模板类的定义在头文件中,queue 模板类需要两个模板参数,一个是元素类型,一个容器类型,元素类型是必要的,容器类型是可选的,默认为deque 类型。C++队列Queue是一种容器适配器,它给予程序员一种先进先出(FIFO)的数据结构。 那么我们如何判断队列是空队列还是已满呢? a、栈空: 队首标志=队尾标志时,表示栈空。 b、栈满 : 队尾+1 = 队首时,表示栈满。 使用标准库的队列时, 应包含相关头文件,在栈中应包含头文件: #include< queue> 。定义:queue< int > q; q.empty() 如果队列为空返回true,否则返回false q.size() 返回队列中元素的个数 q.pop() 删除队列首元素但不返回其值 q.front() 返回队首元素的值,但不删除该元素 q.push() 在队尾压入新元素 q.back() 返回队列尾元素的值,但不删除该元素(1)基于数组的循环队列(循环队列) 以数组作为底层数据结构时,一般讲队列实现为循环队列。这是因为队列在顺序存储上的不足:每次从数组头部删除元素(出队)后,需要将头部以后的所有元素往前移动一个位置,这是一个时间复杂度为O(n)的操作。具体的示例图参考:http://www.cnblogs.com/QG-whz/p/5171123.html。 循环队列,可以把数组看出一个首尾相连的圆环,删除元素时将队首标志往后移动,添加元素时若数组尾部已经没有空间,则考虑数组头部的空间是否空闲,如果是,则在数组头部进行插入。参考博客:【c++版数据结构】之循环队列的实现,判断循环队列是“空”还是“ 满”,有两种处理方法: A. 设置状态标志位以区别空还是满B. 少用一个元素,约定“队头front在队尾rear的下一个位置(指的是环的下一个位置)”作为“满”的标志C语言中,不能用动态分配的一维数组来实现循环队列,如果用户的应用程序中设有循环队列,则必须为它设定一个最大队列长度;如果用户无法预估所用队列的最大长度,则宜采用链队列。 定义front为队列头元素的位置,rear为队列尾元素的位置,MAXSIZE为循环队列的最大长度。注意以下几点,循环队列迎刃而解: A. 求元素的个数:(rear - front + MAXSIZE) % MAXSIZEB. front/rear指向逻辑的下一个空间 front =(front+1)%MAXSIZE,rear = (rear+1)%MAXSIZEC. 判空:front == rearD. 判满:(rear+1+MAXSZIE) == front
例子1、简单的队列操作 #include #include using namespace std; int main(){ queue q; for (int i = 0; i < 10; i++){ q.push(i); } if (!q.empty()){ cout |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |