数据结构图文解析之:队列详解与C++模板实现

0. 数据结构图文解析系列 数据结构系列文章
数据结构图文解析之:数组、单链表、双链表介绍及C++模板实现  
数据结构图文解析之:栈的简介及C++模板实现  
数据结构图文解析之:队列详解与C++模板实现  
数据结构图文解析之:树的简介及二叉排序树C++模板实现.  
数据结构图文解析之:AVL树详解及C++模板实现  
数据结构图文解析之:二叉堆详解及C++模板实现  
数据结构图文解析之:哈夫曼树与哈夫曼编码详解及C++模板实现  
1. 队列简介 1.1 队列的特点

队列(Queue)与栈一样,是一种线性存储结构,它具有如下特点:

队列中的数据元素遵循“先进先出”(First In First Out)的原则,简称FIFO结构。

在队尾添加元素,在队头添加元素。

1.2 队列的相关概念

队列的相关概念:

队头与队尾: 允许元素插入的一端称为队尾,允许元素删除的一端称为队头。

入队:队列的插入操作。

出队:队列的删除操作。

例如我们有一个存储整型元素的队列,我们依次入队:{1,2,3}

添加元素时,元素只能从队尾一端进入队列,也即是2只能跟在1后面,3只能跟在2后面。
如果队列中的元素要出队:

元素只能从队首出队列,出队列的顺序为:1、2、3,与入队时的顺序一致,这就是所谓的“先进先出”。

1.3 队列的操作

队列通常提供的操作:

入队: 通常命名为push()

出队: 通常命名为pop()

求队列中元素个数

判断队列是否为空

获取队首元素

1.4 队列的存储结构

队列与栈一样是一种线性结构,因此以常见的线性表如数组、链表作为底层的数据结构。
本文中,我们以数组、链表为底层数据结构构建队列。

2.基于数组的循环队列实现

以数组作为底层数据结构时,一般讲队列实现为循环队列。这是因为队列在顺序存储上的不足:每次从数组头部删除元素(出队)后,需要将头部以后的所有元素往前移动一个位置,这是一个时间复杂度为O(n)的操作:

可能有人说,把队首标志往后移动不就不用移动元素了吗?的确,但那样会造成数组空间的“流失”。
我们希望队列的插入与删除操作都是O(1)的时间复杂度,同时不会造成数组空间的浪费,我们应该使用循环队列。
所谓的循环队列,可以把数组看出一个首尾相连的圆环,删除元素时将队首标志往后移动,添加元素时若数组尾部已经没有空间,则考虑数组头部的空间是否空闲,如果是,则在数组头部进行插入。

那么我们如何判断队列是空队列还是已满呢?

栈空: 队首标志=队尾标志时,表示栈空,即红绿两个标志在图中重叠时为栈空。

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zzszgw.html