乐趣区

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

jiezi

目录：

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

注释：

什么是队列？

队列是一种非凡的线性表，非凡之处在于它只容许在表的前端（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————————————

退出移动版