数据结构之队列的介绍和代码实现
1 队列
1.1 介绍
- 队列是一个有序列表，可以用数组或是链表来实现
- 遵循先入先出的原则，即：先存入队列的数据，要先取出；后存入队列的数据，要后取出。
1.2 思路
- 队列添加数据：rear队尾往后移，+1
- 队列取出数据：font队头往后移，+1
- 队列为空：font == rear
- 队列已满：rear == 数组大小
1.3 简单代码实现
（1）创建队列类
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55public class NormalQueue {
private int size; //队列长度
private int font; //队头
private int rear; //队尾
private int[] queue; //队列
public NormalQueue(int size) {
this.size = size;
queue = new int[size];
font = -1;
rear = -1;
}
/**
* 向队列添加数据
* @param data 数据
*/
public void addData(int data) {
if(rear == size-1) {
System.out.println("队列已满，不能添加数据！");
}else {
rear ++;
queue[rear] = data;
}
}
/**
* 从获取队列数据
* @return int
*/
public int getData() {
if(font == rear) {
System.out.println("队列为空，没有数据可取！");
return 0;
}else {
font ++;
return queue[font];
}
}
/**
* 打印队列
*/
public void printQueue() {
if(font != rear) {
System.out.println("当前队列为：");
for(int i = font + 1; i<= rear; i++) {
System.out.println(queue[i]);
}
}else {
System.out.println("队列为空！");
}
}
}（2）测试
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29public static void main(String[] args) {
//简单队列测试
//1、创建队列
NormalQueue normalQueue = new NormalQueue(3);
//2、测试打印空队列
System.out.println("----测试打印空队列----");
normalQueue.printQueue();
//3、添满队列
normalQueue.addData(1);
normalQueue.addData(2);
normalQueue.addData(3);
System.out.println("----打印满队列数据----");
normalQueue.printQueue();
//4、测试队列已满添加数据
System.out.println("----测试队列已满添加数据----");
normalQueue.addData(4);
//5、测试取出数据后队列变化
System.out.println("----取出数据后的队列----");
normalQueue.getData();
normalQueue.printQueue();
//6、取出数据后再次添加数据
System.out.println("--取出数据后再次添加数据--");
normalQueue.addData(4);
}
1.4 个人环形队列代码实现
- 此环形队列的实现为个人思路，非官方标准答案
- 我们可以新增一个变量来记录空数据的个数，如果个数为0，就表示数据已满，不能插入；个数不为0，则可以插入
- （1）创建环形队列类
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83public class CircularQueue {
private int size; //队列大小
private int emptyCount; //空数据个数
private int font; //队头
private int rear; //队尾
private int[] queue; //队列
public CircularQueue(int size) {
this.size = size;
emptyCount = size;
font = -1;
rear = -1;
queue = new int[size];
}
/**
* 向队列添加数据
* @param data 数据
*/
public void addData(int data) {
if(emptyCount == 0) {
System.out.println("队列已满，不能添加数据！");
}else {
//判断队尾是否移动到数组尾部，是就将其设置回数组头部
if(rear == size-1) {
rear = 0;
}else {
rear ++;
}
emptyCount --; //空数据-1
queue[rear] = data;
}
}
/**
* 从队列中获取数据
* @return int
*/
public int getData() {
if(emptyCount == size) {
System.out.println("队列为空，没有数据可取！");
return 0;
}else {
//判断队头是否移动到数组尾部，是就将其设置回数组头部
if(font == size-1) {
font = 0;
}else {
font ++;
}
emptyCount ++; //空数据+1
return queue[font];
}
}
/**
* 打印队列
*/
public void printQueue() {
//判断是否为空
if(emptyCount != size) {
//比较队头和队尾的值
if(font < rear) {
//队头<队尾，队列在(队头，队尾]之间
System.out.println("当前队列为：");
for (int i=font+1; i<=rear; i++) {
System.out.println(queue[i]);
}
}else{
//队头>=队尾，队列在(队头, size) 和 [0, rear]之间
System.out.println("当前队列为：");
for(int i=font+1; i<size; i++) {
System.out.println(queue[i]);
}
for (int i=0; i<=rear; i++) {
System.out.println(queue[i]);
}
}
}else {
System.out.println("队列为空！");
}
}
}
- （2）测试
1
2
3
4
5
6
7
8
9
10
11
12
13
14public static void main(String[] args) {
//环形队列测试（重点测试取出数据后，再添加数据）
//1、创建环形队列并添满数据
CircularQueue circularQueue = new CircularQueue(3);
circularQueue.addData(1);
circularQueue.addData(2);
circularQueue.addData(3);
circularQueue.printQueue();
//2、取出数据再添加
circularQueue.getData();
circularQueue.addData(4);
circularQueue.printQueue();
}
1.5 标准环形队列代码实现
- （1）思路
- 取模（取余数），我们希望队头/队尾到达数组底部的时候通过取数组大小的余数返回数组开头
- 将队头指向该为第一个数据的下标，将队尾指向最后一个数据的下标+1
- 但取模会出现一个问题，即0 % 任何数都为0，所以我们取余数时要 + 1，来避开0，所以整体大小+1
- 队列中数据个数：
(rear + size - font) % size - 队列满条件：
(rear + size - font ) % size == size，可以简化为(rear + 1) % size == font - 队列为空条件：
font == rear
- （2）实现代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57public class CircularQueue {
private int size; //队列长度（比输入个数多1长度作为预留空间）
private int font; //队首（第一个元素index）
private int rear; //队尾（最后一个元素index+1）
private int[] queue; //队列（创建时多创一个空间作预留）
public CircularQueue(int size) {
this.size = size + 1;
font = 0;
rear = 0;
queue = new int[size + 1];
}
/**
* 向队列添加数据
* @param data 数据
*/
public void addData(int data) {
if((rear+1)%size == font) {
System.out.println("队列已满，无法添加数据！");
}else {
queue[rear] = data;
rear = (rear+1) % size;
}
}
/**
* 从队列中取出数据
* @return int
*/
public int getData() {
if((font == rear)) {
System.out.println("队列为空，没有数据可取！");
return 0;
}else {
int data = queue[font];
font = (font + 1) % size;
return data;
}
}
/**
* 打印队列
*/
public void printQueue() {
if(font == rear) {
System.out.println("队列为空！");
}else {
System.out.println("当前队列为：");
for(int i=font; i < font + (rear + size - font) % size; i++) {
System.out.println(queue[i % size]);
}
}
}
}