共计 3924 个字符,预计需要花费 10 分钟才能阅读完成。
目录:
- 什么是队列?
- 队列有什么个性?
- 队列名词阐明
- 队列类型详解
- 队列实操
注释:
什么是队列?
队列是一种非凡的线性表,非凡之处在于它只容许在表的前端(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!
循环队列实操
代码:
/**
* 循环队列
*/
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————————————
正文完