循环队列

循环队列是 队列的一种特殊形式。首先介绍队列,然后引申出循环队列。
队列又称为“先进先出”FIFO线性表
限定插入操作只能在队尾进行,而删除操作只能在队首进行
队列也可以采用顺序存储结构或链表结构来实现,分别称为顺序队列和链队列

队列的顺序表示—顺序队列

用一组连续的存储单元依次存放从队首到队尾的元素,附设两个指针 head 和 tail 分别指向队首元素和队尾元素的位置,
(有的地方用 front 和 rear 表示)

img

当 head = tail = 0 时表示空队列

这里写图片描述

当插入新元素到队尾时,tail 加 1

这里写图片描述

当删除队首元素时,head 加 1,上图如果把 C 也删掉,那么就 head = tail 了

tail 始终指向队列元素的下一个位置

对应的操作:
队空:head=tail
求队长:tail - head
入队:新元素按 tail 指示位置加入,再将队尾指针加 1 ,即 tail = tail + 1
出队:将 head 指示的元素取出,再将队头指针加 1,即 head = head + 1

这里写图片描述

下面引入循环队列

这里写图片描述

这里写图片描述

入队,tail 指针变化: >tail = (tail + 1)%maxsize

这里写图片描述

出队,head 指针变化: >head =( head + 1)%maxsize

删除数据 C,队列为空

这里写图片描述

依次插入数据 D,E,F,G,H,I,J,K
队列满:head = tail

这里写图片描述

队满和队空时,均有 head=tail
因此,只凭 head=tail 还无法区分是满还是空。

如何判定队列满还是空?

方法 1:
用一个计数变量来记载队列中的元素个数
初始化队列时 c=0;
当入队时,计数变量+ 1( c=c+1 )
当出队时,计数变量-1 (c=c-1)
当计数变量= maxsize 时,队满
当计数变量= 0 时,队空

方法 2:
牺牲一个元素空间,来区别队空或队满。
入队前,先判 Q.rear+1 是否等于 Q.front,
若是则为队满。
而当 Q.front=Q.rear 时,为队空。
上图中:当数据 J 入队后,就认为队已满,
而当数据 K 再要入队时,就拒绝入队。

当队列已经满了,如果允许覆盖之前的数据:
这里写图片描述

队列已经满了之后,
继续插入数据 L,M,N,
之前的数据 D,E,F 被覆盖
此时,队列已经满了,
最新的数据是:G,H,I,J,K,L,M,N

在程序中,取队列的数据的时候,如果检测到 队列满了,
此时,需要一次性取出队列中的数据,一次性取出数据的时候,不用管 head 指针,直接按照 tail 指针指向的位置开始取数据,直到循环取到 tail-1 位置停止。最终取出的数据的个数是 队列的长度 maxsize
取出之后,可以对队列指针 head 和 tail 初始化为 0,需要将队列满整个标志设置为 False.

当应该用场景如下的时候:

  1. 数据是一条一条的进入队列的
  2. 队列中的数据是一次性读取的
    一次性读取出队列中的所有数据的方式:
    因为允许覆盖,有两种情况:
    当队列满了之后,
    需要根据 tail,从 tail 所在位置的数据,绕一圈到 tail-1 位置所在的数据,都按照顺序取出来,这些数据是按照顺序,最新的数据。
    当队列没有满的时候,
    队列中所有的数据是 Head 到 tail 之间的所有数据。

这里采用方式 2 来进行代码演示

参考代码:

分析:

  1. 当队列满时,条件是(rear + 1) % maxSize = front
  2. 队列为空的条件: rear == front
  3. 队列有效数据个数:(rear + maxSize - front) % maxSize
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
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
import java.util.Scanner;

/**
* @Author SerMs
* @Date 2022/3/20 18:39
* @Version 1.0
*/
public class CircleArrayQueueDemo {
public static void main(String[] args) {
System.out.println("测试数组模拟环形队列的案例~~~~~");
//创建一个队列
CircleArray circleArray = 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':
try {
circleArray.showQueue();
break;
} catch (Exception e) {
System.out.println(e.getMessage());
break;
}
case 'a':
System.out.println("请输入一个数");
int value = scanner.nextInt();
circleArray.addQueue(value);
break;
case 'g': //取出数据
try {
int res = circleArray.getQueue();
System.out.printf("取出的数据是: %d\n", res);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'h':
try {
int res = circleArray.headQueue();
System.out.printf("队列头数据是:%d\n", res);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'e':
scanner.close();
loop = false;
break;
default:
break;
}
}
System.out.println("退出队列~~~");
}
}

class CircleArray {
private int maxSize; //表示数组的最大容量
//front的初始值=0 也就是说arr[front]就是队列的第一个元素
private int front; //队列头
//rear的初始值=0 rear指向队列的最后一个元素的后一个位置,因为希望空出一个空间作为约定
private int rear; //队列尾
private int[] arr; //该数组用于存放数据,模拟队列

//创建队列构造器

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

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

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

//添加数据到队列
public void addQueue(int n) {
if (isFull()) {
System.out.println("队列满,不能加入数据~~~");
}
//直接将数据加入
arr[rear] = n;
//将rear后移,必须考虑取模
rear = (rear + 1) % maxSize;
}

//获取队列的数据,出队列
public int getQueue() {
//判断队列是否为空
if (isEmpty()) {
throw new RuntimeException("队列为空,不能获取数据");
}
//分析出front是指向队列的第一个元素
//1.先把front对应的值保存到临时变量
//2.将front后移 考虑取模
//3.将临时保存的变量返回
int value = arr[front];
front = (front + 1) % maxSize;
return value;
}

//显示所有数据
public void showQueue() {
//遍历
if (isEmpty()) {
throw new RuntimeException("队列为空,不能获取数据");
}
//思路:从front开始遍历,遍历多少个元素
//
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];
}
}