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

注释：

什么是队列？

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

队列有什么个性？

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

队列名词阐明

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

队列类型

程序队列

定义：

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

操作逻辑：

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

程序队列中的溢出景象：

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

循环队列

定义
为了解决程序队列的空间节约状况，在此循环队列入世，能够使队列空间失去重复使用。
无论插入或删除，一旦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!

循环队列实操