队列介绍

1)队列是一个有序列表,可以用数组或是链表来实现。
2)遵循先入先出的原则。即:先存入队列的数据,要先取出,后存入的要后取出。

顺序队列

顺序队一般会设置两个指针进行管理:front指针指向队列的第一个元素,rear指针指向最后一个元素的下一个位置,初始值都是0

每次在队尾插入一个元素是,rear增1;每次在队头删除一个元素时,front增1。当front=rear时,队列中没有任何元素,称为空队列。

顺序队列中的溢出现象:

“下溢”现象:当队列为空时,做出队运算产生的溢出现象。“下溢”是正常现象,常用作程序控制转移的条件。

“真上溢”现象:当队列满时,做进队运算产生空间溢出的现象。“真上溢”是一种出错状态,应设法避免。

“假上溢”现象:由于入队和出队操作中,头尾指针只增加不减小,致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时,也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为”假上溢”现象。

顺序队列的缺陷:当rear增加到指向分配的连续空间之外时,队列无法再插入新元素,但这时往往还有大量可用空间未被占用,这些空间是已经出队的队列元素曾经占用过得存储单元。也就是数组使用过一次后就不能再使用了,没有达到复用的效果。

缺陷的解决思路:

第一种方法:队列元素的出列是在队头,即下标为0的位置,每次出队,队列中的所有元素都得向前移动,以保证队列的队头,也就是下标为0的位置不为空,此时时间复杂度为0(n),如图所示。

第二种方法:第一种方法每次出队所有元素都要前移,性能有所降低。我们可以设置front指针和rear指针越界(超过数组下标)时,从头开始循环,这就是下面要介绍的循环队列。

循环队列

定义:无论插入或删除,一旦rear指针增1或front指针增1 时超出了所分配的队列空间,就让它指向这片连续空间的起始位置,这种头尾相接的顺序存储结构称为循环队列。

front指针指向队列的第一个元素,rear指针指向最后一个元素的下一个位置,初始值都是0

当front=rear时,称为空队列,如下图:

那么问题来了,下图再入列a7时,rear=front,此时就不是空队列了,与上面矛盾。

所以当队列满时,我们修改其条件,保留一个元素空间。也就是说,队列满时,数组中还有一个空闲单元,如下图就是队列满了:

数组最大容量为QueueSize,那么队列满的条件是(rear+1)%QueueSize ==front(取模“%”的目的就是为了整合rear与front大小的问题)。如上图所示。

队列长度分为两段,一段是QueueSize-front,另一段是0+rear,加在一起,队列长度为rear-front+QueueSize。因此通用的计算队列长度公式为:(rear-front+QueueSize)%QueueSize

循环队列的代码实现:

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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
package com.nanzx.queue;

import java.util.Scanner;

public class CircleArrayQueueDemo {

public static void main(String[] args) {

// 测试一把
// 创建一个环形队列
CircleArray queue = new CircleArray(4);// 设置4,说明队列的有效数据最多为3个
char key = ' '; // 接收用户输入
Scanner scanner = new Scanner(System.in);
boolean loop = true;
// 输出一个菜单
while (loop) {
System.out.println("s(show): 显示队列");
System.out.println("e(exit): 退出程序");
System.out.println("a(add): 添加数据到队列");
System.out.println("g(get): 从队列取出数据");
System.out.println("h(head): 查看队列头的数据");
key = scanner.next().charAt(0);// 接收一个字符
switch (key) {
case 's':
queue.showQueue();
break;
case 'a':
System.out.println("输出一个数");
int value = scanner.nextInt();
queue.addQueue(value);
break;
case 'g': // 取出数据
try {
int res = queue.getQueue();
System.out.printf("取出的数据是%d\n", res);
} catch (Exception e) {
// TODO: handle exception
System.out.println(e.getMessage());
}
break;
case 'h': // 查看队列头的数据
try {
int res = queue.headQueue();
System.out.printf("队列头的数据是%d\n", res);
} catch (Exception e) {
// TODO: handle exception
System.out.println(e.getMessage());
}
break;
case 'e': // 退出
scanner.close();
loop = false;
break;
default:
break;
}
}

System.out.println("程序退出~~");
}
}

class CircleArray {
private int maxSize;// 表示数组最大容量
private int front;// 队列头,指向队列第一个数据,初始值为0
private int rear;// 队列尾,指向队列最后一个数据的后一个位置,初始值为0
private int[] arr;// 该数组用于存放数据,模拟队列

public CircleArray(int arrMaxSize) {
maxSize = arrMaxSize;
arr = new int[maxSize];
}

// 判断队列是否满了
boolean isFull() {
return (rear + 1) % maxSize == front;
}

// 判断队列是否为空
boolean isEmpty() {
return rear == front;
}

// 添加数据到队列
public void addQueue(int n) {
// 判断队列是否满了
if (isFull()) {
System.out.println("队列已满,不能添加数据");
return;
}
arr[rear] = n;
rear = (rear + 1) % maxSize; // rear后移
}

// 出队列
public int getQueue() {
// 判断队列是否为空
if (isEmpty()) {
throw new RuntimeException("队列为空,不能取数据");
}
int var = arr[front];
front = (front + 1) % maxSize;
return var;
}

// 显示队列所有数据
public void showQueue() {
if (isEmpty()) {
System.out.println("队列空的,没有数据");
}
for (int i = front; i < front + size(); i++) {
System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]);
}
}

// 求出当前队列有效数据的个数
public int size() {
return (rear + maxSize - front) % maxSize;
}

// 显示队列的头数据,注意不是取出数据
public int headQueue() {
if (isEmpty()) {
throw new RuntimeException("队列为空,没有数据");
}
return arr[front];
}
}