关于数据结构和算法:数据结构之队列知识详解

目录：

• 什么是队列？
• 队列有什么个性？
• 队列名词阐明
• 队列类型详解
• 队列实操

注释：

什么是队列？

队列是一种非凡的线性表，非凡之处在于它只容许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

队列有什么个性？

1. 只容许在一端插入和另一端删除
2. 遵循先进先出（FIFO）的准则

队列名词阐明

1. 队列元素
队列的数据元素又称为队列元素
2. 入队
队列的数据元素又称为队列元素
3. 出队
从队列中删除一个队列元素称为出队

队列类型

程序队列

定义：

程序队列构造必须为其动态调配或动静申请一片间断的存储空间，并设置两个指针进行治理。一个是队头指针front，它指向队头元素；另一个是队尾指针rear，它指向下一个入队元素的存储地位。

操作逻辑：

每次在队尾插入一个元素是，rear增1；每次在队头删除一个元素时，front增1。随着插入和删除操作的进行，队列元素的个数一直变动，队列所占的存储空间也在为队列构造所调配的间断空间中挪动。当front=rear时，队列中没有任何元素，称为空队列。当rear减少到指向调配的间断空间之外时，队列无奈再插入新元素，但这时往往还有大量可用空间未被占用，这些空间是曾经出队的队列元素已经占用过得存储单元。

程序队列中的溢出景象：

1. “下溢”景象：当队列为空时，做出队运算产生的溢出景象。“下溢”是失常景象，罕用作程序控制转移的条件。
2. “真上溢”景象：当队列满时，做进栈运算产生空间溢出的景象。“真上溢”是一种出错状态，应设法防止。
3. “假上溢”景象：因为入队和出队操作中，头尾指针只减少不减小，以致被删元素的空间永远无奈从新利用。当队列中理论的元素个数远远小于向量空间的规模时，也可能因为尾指针已超过向量空间的上界而不能做入队操作。该景象称为”假上溢”景象。

循环队列

定义
为了解决程序队列的空间节约状况，在此循环队列入世，能够使队列空间失去重复使用。
无论插入或删除，一旦rear指针增1或front指针增1 时超出了所调配的队列空间，就让它指向这片间断空间的起始地位。本人真从MaxSize-1增1变到0，可用取余运算rear%MaxSize和front%MaxSize来实现。这实际上是把队列空间设想成一个环形空间，环形空间中的存储单元循环应用，用这种办法治理的队列也就称为循环队列。
操作逻辑
在循环队列中，当队列为空时，有front=rear，而当所有队列空间全占满时，也有front=rear。为了区别这两种状况，规定循环队列最多只能有MaxSize-1个队列元素，当循环队列中只剩下一个空存储单元时，队列就曾经满了。因而，队列判空的条件时front=rear，而队列判满的条件时front=（rear+1）%MaxSize。

队列实操

程序队列实操

代码：

/**
 * 程序队列
 */
System.out.println("**********程序队列**************");
SequentialQueue<String> sequentialQueue = new SequentialQueue<>(5, new String[5]);

//判断是否为空队列
System.out.println("判断是否为空队列：");
System.out.println(sequentialQueue.isEmpty());

//入队
System.out.println("程序队列，入队 sequential queue hello world!：");
sequentialQueue.inQueue("sequential ");
sequentialQueue.inQueue("queue ");
sequentialQueue.inQueue("hello ");
sequentialQueue.inQueue("world!");
sequentialQueue.inQueue("1!");
sequentialQueue.display();

//获取队列大小
System.out.println("获取队列大小：");
System.out.println(sequentialQueue.getSize());

//获取队头
System.out.println("获取队头：");
System.out.println(sequentialQueue.getFront());

//出队
System.out.println("程序队列，出队一次！");
sequentialQueue.outQueue();

//获取队列大小
System.out.println("获取队列大小：");
System.out.println(sequentialQueue.getSize());

//获取队头
System.out.println("获取队头：");
System.out.println(sequentialQueue.getFront());

//判断是否为空队列
System.out.println("判断是否为空队列：");
System.out.println(sequentialQueue.isEmpty());

//展现队列
sequentialQueue.display();

sequentialQueue.inQueue("11");
sequentialQueue.inQueue("12");

sequentialQueue.display();

后果：

**********程序队列**************
判断是否为空队列：
true
程序队列，入队 sequential queue hello world!：
展现队列：
sequential  
queue  
hello  
world! 
1! 

获取队列大小：
5
获取队头：
sequential 
程序队列，出队一次！
获取队列大小：
4
获取队头：
queue 
判断是否为空队列：
false
展现队列：
queue  
hello  
world! 
1! 

展现队列：
queue  
hello  
world! 
1! 

循环队列实操

代码：

/**
 * 循环队列
 */
System.out.println("**********循环队列**************");
CircularQueue<String> circularQueue = new CircularQueue<>(10, new String[10]);

//判断是否为空队列
System.out.println("判断是否为空队列：");
System.out.println(circularQueue.isEmpty());

//入队
System.out.println("循环队列，入队：");
circularQueue.inQueue("circular ");
circularQueue.inQueue("queue ");
circularQueue.inQueue("hello ");
circularQueue.inQueue("world!");
circularQueue.inQueue("5!");
circularQueue.inQueue("6!");
circularQueue.inQueue("7!");
circularQueue.inQueue("8!");
circularQueue.inQueue("9!");
circularQueue.inQueue("10!");
circularQueue.display();

//获取队列大小
System.out.println("获取队列大小：");
System.out.println(circularQueue.getSize());

//获取队头
System.out.println("获取队头：");
System.out.println(circularQueue.getFront());

//出队
System.out.println("循环队列，出队一次！");
circularQueue.outQueue();

//获取队列大小
System.out.println("获取队列大小：");
System.out.println(circularQueue.getSize());

//获取队头
System.out.println("获取队头：");
System.out.println(circularQueue.getFront());

//判断是否为空队列
System.out.println("判断是否为空队列：");
System.out.println(circularQueue.isEmpty());

//展现队列
circularQueue.display();

circularQueue.inQueue("10！");
circularQueue.inQueue("11！");
circularQueue.inQueue("12！");
circularQueue.display();

后果：

**********循环队列**************
判断是否为空队列：
true
循环队列，入队：
展现队列：
circular  
queue  
hello  
world! 
5! 
6! 
7! 
8! 
9! 

获取队列大小：
9
获取队头：
circular 
循环队列，出队一次！
获取队列大小：
8
获取队头：
queue 
判断是否为空队列：
false
展现队列：
queue  
hello  
world! 
5! 
6! 
7! 
8! 
9! 
null 

展现队列：
queue  
hello  
world! 
5! 
6! 
7! 
8! 
9! 
10！ 

—————————————END————————————