数据结构 - 队列

队列也是一种操纵受限的线性数据结构，与栈很相似。

01界说

栈的操纵受限表现为只允许在队列的一端举行元素插入操纵，在队列的另一端只允许删除操纵。这一特性可以总结为先辈先出（First In First Out，简称FIFO）。这意味着在队列中第一个到场的元素将第一个被移除。

入****队：向队列中添加新元素的活动叫做入队；
出****队：从队列中移除元素的活动叫做出队；
队头：在队列中允许举行元素移除活动的一端称为队头；
队尾：在队列中运行举行元素添加活动的一端称为队尾；
空****队列：当队列中没有元素时称为空队列。
满****队列：当队列是有限容量，而且容量已用完，则称为满队列。
队列****容量：当队列是有限容量，队列容量表现队列可以容纳的最大元素数量。
队列****巨细：表现当前队列中的元素数量。

02分类

队列根据存储方式和功能特性有两种分类方式。
1、根据存储方式分类

队列是逻辑结构，因此以存储方式的差别可以分为序次队列和链式队列。
序次队列就是全部的队列元素都存储在一连的地点空间中，因此可以通过数组来实现序次队列，由于数组的特性也导致序次队列容量是固定的，不易扩容，这也导致轻易浪费空间，同时还要留意元素溢出等题目。
链式队列顾名思义就是接纳链式方式存储，可以通过链表实现，因此链式队列可以做到无穷扩容，大大的进步了内存利用率。

2、根据功能特性分类

根据功能特性可以分类出很多专有队列，下面我们摆列几个简单先容一下。
壅闭队列：当空队列时会壅闭出队操纵，当满队列时会壅闭入队操纵。
优先队列：队列中每个元素都有一个优先级别属性，而元素的出队操纵取决于这个优先级别属性，即优先级别高则优先出队。
耽误队列：队列中每个元素都标记一个时间纪录，元素只有在指定的延时时间后才会触发出队操纵。
循环队列：当利用数组实现队列时，可以通过把队头和队尾相毗连，即当队尾到达数组的尾端可以“绕回”数组的开头，通过这种奇妙的计划来进步数组空间利用率。
双端队列：是一种两端都可以举行入队和出队操纵的数据结构。
根据这些队列特性，在差别的场景中可以起到意想不到的效果。
下面我们将序次队列和链式队列的实现举行具体解说。
03实现（序次队列）

下面我们借助数组来实现序次队列，其焦点头脑是把数组的起始位置作为队头，把数组尾方向作为队尾。当发生出队活动时，必要把剩余全部数据向队头方向移动一位，为什么要做这步操纵呢？
起首序次队列内部是数组，假设数组内可以存放7个元素，此时数组已存满，因此不可以再举行添加新元素入队操纵了，然后我们对数组头元素举行出队操纵，此时数组由于出队会留下一个空位，如下图。

那么此时是否可以举行入队操纵呢？直接告诉我们应该可以，由于数组头已经有空位了。但是我们约定了队列只能从数组尾举行入队操纵，而此时数组尾并没有空位提供给新入队的元素，因此实际上无法举行入队操纵。
那要如那里理呢？最简单的方法就是当发生出队操纵时，背面全部的元素都向着队头方向移动一位，把队尾空出一位，这每出一个元素就可以入一个元素。

固然这也不是唯一方案，还是通过循环队列办理这一题目，有爱好的可以研究一下。
1、ADT界说

我们起首来界说序次队列的ADT。
ADT Queue{

1. 数据对象：D 是一个非空的元素集合，D = {a1, a2, ..., an}，其中 ai 表示队列中的第i个元素，n是队列的长度。
3. 数据关系：D中的元素通过它们的索引（位置）进行组织，索引是从0到n-1的整数，并且遵循元素先进先出的原则。
5. 基本操作：[
7. Init(n) ：初始化一个指定容量的空队列。
9. Capacity：返回队列容量。
11. Length：返回队列长度。
13. Head：返回队头元素，当为空队列则报异常。
15. Tail：返回队尾元素，当为空队列则报异常。
17. IsEmpty()：返回是否为空队列。
19. IsFull()：返回是否为满队列。
21. Enqueue()：入队即添加元素，当为满队列则报异常。
23. Dequeue()：出队即返回队头元素并把其从队列中移除，当为空队列则报异常。
24. ]

复制代码

}
界说好队列ADT，下面我们就可以开始自己实现的队列。
2、初始化 Init

起首界说3个变量用于存放队列元素数组、队列容量以及队尾索引，而没有界说队头索引是由于队头索引永久便是0。
初始化结构告急做几件事。

• 初始化队列的容量；
  
• 初始化存放队列元素数组；
  
• 初始化队尾索引；
  

具体实当代码如下：

1. //存放队列元素
2. private T[] _array;
3. //队列容量
4. private int _capacity;
5. //队尾索引，为-1表示空队列
6. private int _tail;
7. //初始化队列为指定容量
8. public MyselfQueueArray<T> Init(int capacity)
9. {
10.     //初始化队列容量为capacity
11.     _capacity = capacity;
12.     //初始化指定长度数组用于存放队列元素
13.     _array = new T[_capacity];
14.     _tail = -1;
15.     //返回队列
16.     return this;
17. }

复制代码

3、获取队列容量 Capacity

这个比力简单直接把队列容量私有字段返回即可。

1. //队列容量
2. public int Capacity
3. {
4.     get
5.     {
6.         return _capacity;
7.     }
8. }

复制代码

4、获取队列长度 Length

我们并没有界说队列长度的私有字段，由于队尾索引即表现数组末了一个元素索引，即可以代表队列长度，因此只需用队尾索引加1即可得到队列长度，同时必要留意判断队列是否为空，如果为空则报错。

1. //队列长度
2. public int Length
3. {
4.     get
5.     {
6.         if (IsEmpty())
7.         {
8.             return 0;
9.         }
10.         //队列长度等于队尾索引加1
11.         return _tail + 1;
12.     }
13. }

复制代码

5、获取队头元素 Head

基于我们上面的约定，队头元素永久对应数组的第一个元素，因此可以直接获取索引为0的数组元素。空队列则报错。具体代码如下：

1. //获取队头元素
2. public T Head
3. {
4.     get
5.     {
6.         if (IsEmpty())
7.         {
8.             //空队列，不可以进行获取队头元素操作
9.             throw new InvalidOperationException("空队列");
10.         }
11.         return _array[0];
12.     }
13. }

复制代码

6、获取队尾元素 Tail

由于我们界说了队尾索引私有变量，因此可以直接通过队尾索引获取。具体代码如下：

1. //获取队尾元素
2. public T Tail
3. {
4.     get
5.     {
6.         if (IsEmpty())
7.         {
8.             //空队列，不可以进行获取队头元素操作
9.             throw new InvalidOperationException("空队列");
10.         }
11.         return _array[_tail];
12.     }
13. }

复制代码

7、获取是否空队列 IsEmpty

是否空队列只需判断队尾索引是否小于0即可。

1. //是否空队列
2. public bool IsEmpty()
3. {
4.      //队尾索引小于0表示空队列
5.      return _tail < 0;
6. }

复制代码

8、获取是否满队列 IsFull

是否满队列只需判断队尾索引是否与队列容量减1相称，代码如下：

1. //是否满队列
2. public bool IsFull()
3. {
4.     //队头索引等于容量大小减1表示满队列
5.     return _tail == _capacity - 1;
6. }

复制代码

9、入队 Enqueue

入队只需向队列内部数组尾添加一个新元素即可，因此先把队尾索引先后移动一位，然后再把新元素赋值给队尾元素，同时还必要查抄是否为满队列，如果是满队列则报错，具体实当代码如下：

1. //入队
2. public void Enqueue(T value)
3. {
4.     if (IsFull())
5.     {
6.         //满队列，不可以进行入队列操作
7.         throw new InvalidOperationException("满队列");
8.     }
9.     //队尾索引向后移动1位
10.     _tail++;
11.     //给队尾元素赋值新值
12.     _array[_tail] = value;
13. }

复制代码

10、出队 Dequeue

出队则大抵分为以下几步：

• 判断是否为空队列，空队列则报错；
  
• 取出队头元素暂存，重置队头元素为默认值；
  
• 把队头背面全部元素向队头方向移动一位；
  
• 重置队尾元素为默认值；
  
• 队尾索引向队头方向移动一位，即队尾索引减1；
  
• 返回暂存的队头元素；
  

具体实当代码如下：

1. //出队
2. public T Dequeue()
3. {
4.     if (IsEmpty())
5.     {
6.         //空队列，不可以进行出队列操作
7.         throw new InvalidOperationException("空队列");
8.     }
9.     //取出队头元素
10.     var value = _array[0];
11.     //对头元素重置为默认值
12.     _array[0] = default;
13.     //队头元素后面所有元素都向队头移动一位
14.     for (int i = 0; i < _tail; i++)
15.     {
16.         _array[i] = _array[i + 1];
17.     }
18.     //队尾元素重置为默认值
19.     _array[_tail] = default;
20.     //队尾索引向队头方向移动一位
21.     _tail--;
22.     //返回队头元素
23.     return value;
24. }

复制代码

04实现（链式队列）

我们借助链表来实现链式队列，其焦点头脑是把链表尾节点作为队尾，把链表首元节点作为队头。
1、ADT界说

相对于序次队列的ADT来说，链式队列的ADT少了两个方法即获取队列容量和是否满队列，这也是链表特性带来的长处。
2、初始化 Init

起首必要界说链表节点类，包罗两个属性数据域和指针域。
然后必要界说3个变量用于存放队头节点、队尾节点以及队列长度。
而初始化结构告急初始化3个变量初始值，具体实现如下：

1. public class MyselfQueueNode<T>
2. {
3.     //数据域
4.     public T Data;
5.     //指针域，即下一个节点
6.     public MyselfQueueNode<T> Next;
7.     public MyselfQueueNode(T data)
8.     {
9.         Data = data;
10.         Next = null;
11.     }
12. }
13. public class MyselfQueueLinkedList<T>
14. {
15.     //队头节点即首元节点
16.     private MyselfQueueNode<T> _head;
17.     //队尾节点即尾节点
18.     private MyselfQueueNode<T> _tail;
19.     //队列长度
20.     private int _length;
21.     //初始化队列
22.     public MyselfQueueLinkedList<T> Init()
23.     {
24.         //初始化队头节点为空
25.         _head = null;
26.         //初始化队尾节点为空
27.         _tail = null;
28.         //初始化队列长度为0
29.         _length = 0;
30.         //返回队列
31.         return this;
32.     }
33. }

复制代码

3、获取队列长度 Length

这个比力简单直接把队列长度私有字段返回即可。

1. //队列长度
2. public int Length
3. {
4.     get
5.     {
6.         return _length;
7.     }
8. }

复制代码

4、获取队头元素 Head

获取队头元素可以通过队头节点数据域直接返回，但是要留意判断队列是否为空队列，如果为空队列则报非常。具体代码如下：

1. //获取队头元素
2. public T Head
3. {
4.     get
5.     {
6.         if (IsEmpty())
7.         {
8.             //空队列，不可以进行获取队头元素操作
9.             throw new InvalidOperationException("空队列");
10.         }
11.         //返回队头节点数据域
12.         return _head.Data;
13.     }
14. }

复制代码

5、获取队尾元素 Tail

获取队尾元素可以通过队尾节点数据域直接返回，但是要留意空栈则报非常。具体代码如下：

1. //获取队尾元素
2. public T Tail
3. {
4.     get
5.     {
6.         if (IsEmpty())
7.         {
8.             //空队列，不可以进行获取队尾元素操作
9.             throw new InvalidOperationException("空队列");
10.         }
11.         //返回队尾节点数据域
12.         return _tail.Data;
13.     }
14. }

复制代码

6、获取是否空队列 IsEmpty

是否空队列只需判断队头节点和队尾节点是否都为空即可。

1. //是否空队列
2. public bool IsEmpty()
3. {
4.     //队头节点为null和队尾节点都为空表示空队列
5.     return _head == null && _tail == null;
6. }

复制代码

7、入队 Enqueue

入队大抵分为以下几步：

• 必要先创建一个新节点；
  
• 如果原队尾节点不为空，则把原队尾节点指针域指向新节点；
  
• 把原队尾节点更新为新节点；
  
• 如果队头节点为空，则阐明这是第一个元素，以是队头和队尾都是同一个节点，因此要把队尾节点赋值给队头节点；
  
• 队列长度加1；
  

具体实当代码如下：

1. //入队
2. public void Enqueue(T value)
3. {
4.     //创建新的队尾节点
5.     var node = new MyselfQueueNode<T>(value);
6.     //如果队尾节点不为空，则把新的队尾节点连接到尾节点后面
7.     if (_tail != null)
8.     {
9.         _tail.Next = node;
10.     }
11.     //队尾节点变更为新的队尾节点
12.     _tail = node;
13.     //如果队头节点为空，则为其赋值为队尾节点
14.     if (_head == null)
15.     {
16.         _head = _tail;
17.     }
18.     //队列长度加1
19.     _length++;
20. }

复制代码

8、出队 Dequeue

出队则大抵分为以下几步：

• 判断是否空队列，空队列则报错；
  
• 获取队头节点数据域暂存；
  
• 更新头节点为原队头节点对应的下一个节点；
  
• 如果队头节点为空，则阐明为空队列，队尾节点也要置空；
  
• 队列长度减1；
  
• 返回暂存的队头节点数据；
  

具体实当代码如下：

1. //出队
2. public T Dequeue()
3. {
4.     if (IsEmpty())
5.     {
6.         //空队列，不可以进行出队列操作
7.         throw new InvalidOperationException("空队列");
8.     }
9.     //获取队头节点数据
10.     var data = _head.Data;
11.     //把队头节点变更为原队头节点对应的下一个节点
12.     _head = _head.Next;
13.     //如果队列为空，表明为空队列，同时更新队尾为空
14.     if (_head == null)
15.     {
16.         _tail = null;
17.     }
18.     //队列长度减1
19.     _length--;
20.     //返回队头节点数据
21.     return data;
22. }

复制代码

注：测试方法代码以及示例源码都已经上传至代码库，有爱好的可以看看。https://gitee.com/hugogoos/Planner