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)的时间复杂度，同时不会造成数组空间的浪费，我们应该使用循环队列。 所谓的循环队列，可以把数组看出一个首尾相连的圆环，删除元素时将队首标志往后移动，添加元素时若数组尾部已经没有空间，则考虑数组头部的空间是否空闲，如果是，则在数组头部进行插入。

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

栈空： 队首标志=队尾标志时，表示栈空，即红绿两个标志在图中重叠时为栈空。栈满 : 队尾+1 = 队首时，表示栈空。图三最下面的队列即为一个满队列。尽管还有一个空位，我们不存储元素。

2.1 循环队列的抽象数据类型

template <typename T> class LoopQueue { public: LoopQueue(int c = 10); ~LoopQueue(); public: bool isEmpty(); //队列的判空 int size(); //队列的大小 bool push(T t); //入队列 bool pop(); //出队列 T front(); //队首元素 private: int capacity; int begin; int end; T* queue; }; begin：队首标志end：队尾标志capacity：数组容量queue：数组

2.2 队列的具体实现

队列的操作非常简单，这里不再多说

template<typename T> LoopQueue<T>::LoopQueue(int c = 10) : capacity(c), begin(0), end(0), queue(nullptr) { queue = new T[capacity]; }; template<typename T> LoopQueue<T>::~LoopQueue() { delete[]queue; } template <typename T> bool LoopQueue<T>::isEmpty() { if (begin == end) return true; return false; }; template<typename T> int LoopQueue<T>::size() { return (end-begin+capacity)