2数据结构之队列_maxsize

队列介绍：

队列是一个有序列表，可以用数组或者链表来实现。
遵循先进先出的原则。也就是说，添加数据的时候从队列尾部添加，取数据的时候从队列首部开始取。
模拟图：

1. maxSize指的是队列容量大小，也就是能存储多少个元素。

2. front 指向队列头部第一个元素的前一个元素，初始值我们假设为 -1

3. rear指向队列尾部最后一个元素元素，初始值我们假设为为 -1

当rear=maxSize - 1时，此时队列表示已满；

当rear<maxSize - 1时，此时队列表示还可以继续添加数据；

当rear=frount时，此时队列里面没有元素，为空；

环形！！！！！！

我们做环形的思路是，当rear>maxSize时，此时重新设置为0，rear+1是预留一个位置，不牺牲这个位置会导致无法判断队列是否为空或满。

思路

(rear+1)%maxSize=foont，此时可判断已满（满）
怎么理解呢？
现在不是之前的原数组，当容量满了之后就不再添加数据，现在是一个环形的数组，满了之后从头开始加。
此时：（需要在队列后面空出一个位置 所以此时队列容量大小为maxSize-1）

1. maxSize指的是队列容量大小，也就是能存储多少个元素。

2. front 指向队列头部第一个元素。

3. rear(初始值0)指向队列尾部最后一个元素的后一个位置(空留出来的)元素。
   
   (rear+1)%maxSize=fount(0)，此时可判断已满（满），也可做为当队列头有空位的时候，rear+1取模之后变为0 又开始循环。。--------也就是说此时的rear=(rear+1)%maxSize

1.判断队列是否为空

当frount==rear时

2.判断队列是否为满

为何要在 rear 之后，front 之前空出一个元素的空间？因为如果不空出一个元素，队列判空条件为：front == rear ，队列判满的条件也是：front == rear ，有歧义！

队列容量：因为空出了一个元素，所以队列容量就变成了 (maxSize - 1)

当空出一个元素的空间，如何判满？当还剩一个元素时，队列就已经满了，所以判断条件为 (rear + 1) % maxSize == front

3.队列元数个数：

计算公式：(rear + maxSize - front) % maxSize ，这样来思考：

当 rear 比 front 大时，即 (rear -front) > 0 ，这时还没有形成环形结构，(rear -front) 即是队列元素个数

当 rear 比 front 小时，即 (rear -front) < 0 ，这时已经形成了环形结构，(rear -front) 表示数组还差多少个元素存满（负数），(rear + maxSize - front) 即是队列元素个数

综上：(rear + maxSize - front) % maxSize(防止溢出)

4.队列入队：

首先，队列不满才能入队

由于 rear 指向队列尾部元素的后一个元素，所以直接设置即可： arr[rear] = value

接下来，rear 应该向后移动一个位置：rear = (rear + 1) % maxSize

取模是为了防止数组越界，让指针从新回到数组第一个元素

5.队列出队：

首先，队列不空才能出队

由于 front 直接指向队列头部元素，所以直接返回该元素即可：int value = arr[front ]

接下来，front 应该向后移动一个位置：front = (front + 1) % maxSize

取模是为了防止数组越界，让指针从新回到数组第一个元素

下面是代码实现：

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): 查看队列头的数据");
			System.out.println();
			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("程序退出~~");
	}

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

参考：https://blog.csdn.net/oneby1314/article/details/107584566