队列（Queue）的一个使用场景

银行排队的案例：

队列（Queue）介绍

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

数组模拟队列

• 队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图，其中maxSize是该队列的最大容量。

• 因为队列的输出、输入分别从前后端来处理，因此需要两个变量front及rear分别记录队列前后端的下标，front会随着数据输出而改变，而rear则是随着数据输入而改变的。如图所示：

  

思路分析：

当我们将数据存入队列时称为“addQueue”，addQueue的处理需要有两个步骤：

• 将尾指针往后移：rear+1，当front == rear【空】
• 若尾指针rear小于队列的最大下标maxSize-1，则将数据存入rear所指的数组元素中，否则无法存入数据。rear == maxSize-1【队列满】

代码实现

import java.util.Scanner;

public class ArrayQueueDemo {

	public static void main(String[] args) {

		// 测试

		//创建一个队列

		ArrayQueue arrayQueue = new ArrayQueue(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(show)：添加数据到队列");

			System.out.println("g(get)：从队列取出数据");

			System.out.println("h(head)：查看队列头的数据");

			key = scanner.next().charAt(0);

			switch (key) {

			case 's'://显示队列

				arrayQueue.showQueue();

				break;

			case 'a'://添加数据到队列

				System.out.println("请输入一个数字：");

				int value = scanner.nextInt();

				System.out.println(value);

				arrayQueue.addQueue(value);

				break;

			case 'g'://从队列取出数据

				try {

					int res = arrayQueue.getQueue();

					System.out.printf("取出数据是%d\n",res);

				} catch (Exception e) {

					// TODO: handle exception

					System.out.println(e.getMessage());

				}

				break;

			case 'h'://查看队列头的数据

				try {

					int res = arrayQueue.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("程序退出~~");

	}

}

//使用数组模拟队列-编写一个ArrayQueue类

class ArrayQueue {

	private int maxSize;//表示数组最大容量

	private int front;//队列头部

	private int rear;//队列尾部

	private int[] arr;//该数组用于存放数据，模拟队列

	//创建队列的构造器

	public ArrayQueue(int arrMaxSize) {

		maxSize = arrMaxSize;

		arr = new int [maxSize];

		front = -1;//队列头部，指向队列头的前一个位置

		rear = -1;//队列尾部，指向队列尾的数据（就是队列最后一个数据）

	}

	//判断队列是否满

	public boolean isFull() {

		return rear == maxSize - 1;

	}

	//判断队列是否为空

	public boolean isEmpty() {

		return rear == front;

	}

	//添加数据到队列

	public void addQueue(int n) {

		//判断队列是否已满

		if(isFull()) {

			System.out.println("队列已满，无法加入数据~~");

			return;

		}

		rear ++;

		arr[rear] = n;

	}

	//获取队列的数据（出队列）

	public int getQueue() {

		if(isEmpty()) {

			throw new RuntimeException("队列为空，无法取数据~~");

		}

		front ++;

		return arr[front];

	}

	//显示所有数据

	public void showQueue() {

		//判断是否为空

		if(isEmpty()) {

			System.out.println("队列为空，没有数据~~");

			return;

		}

		for (int i = 0; i < arr.length; i++) {

			System.out.printf("arr[%d]=%d\n",i,arr[i]);

		}

	}

	//显示队列的头数据，（不是取出数据）

	public int headQueue() {

		if(isEmpty()) {

			throw new RuntimeException("队列为空，无法取数据~~");

		}

		return arr[front + 1];

	}

}

输出结果：

​

问题分析

目前数组使用一次就不能使用了，没有达到复用的效果

优化

• 对前面的数组模拟队列的优化，充分利用数组，因此将数组看做是有个环形的。（通过取模的方式来实现即可）

  说明：

  • 尾索引的下一个为头索引时表示队列满，即将队列容量空出一个作为约定，这个在做判断队列满的时候需要注意，(rear+1)%maxSize == front[满]
  • rear == front[空]

  思路如下：

  • front变量的含义做一个调整：front就指向队列的第一个元素，也就是说arr[front]就是队列的第一个元素，front的初始值=0。
  • rear变量的含义做一个调整：rear指向队列的最后一个元素的后一个位置。因为希望空出一个空间作为约定，rear的初始值=0。
  • 当队列满时，条件是：(rear+1)%maxSize==front【满】
  • 队列为空的条件：real==front【空】
  • 当我们这样分析后，队列中有效的数据的个数：(rear+maxSize-front) %maxSize

  有了这样一个思路，我们就可以在原来队列上修改得到一个环形队列。

优化后的代码

import java.util.Scanner;

/**

* @Author ITfxsen https://www.cnblogs.com/fxsenblog/

* @Time 2021-3-12 13:11:26

* @Version 1.0

* <p>Description:环形数组队列Demo</p>

*/

public class CircleArrayQueueDemo {

	public static void main(String[] args) {

		// 测试

		System.out.println("测试数组模拟环形队列~~");

		//创建一个环形队列

		CircleArray circleArray = new CircleArray(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(show)：添加数据到队列");

			System.out.println("g(get)：从队列取出数据");

			System.out.println("h(head)：查看队列头的数据");

			key = scanner.next().charAt(0);

			switch (key) {

			case 's'://显示队列

				circleArray.showQueue();

				break;

			case 'a'://添加数据到队列

				System.out.println("请输入一个数字：");

				int value = scanner.nextInt();

				System.out.println(value);

				circleArray.addQueue(value);

				break;

			case 'g'://从队列取出数据

				try {

					int res = circleArray.getQueue();

					System.out.printf("取出数据是%d\n",res);

				} catch (Exception e) {

					// TODO: handle exception

					System.out.println(e.getMessage());

				}

				break;

			case 'h'://查看队列头的数据

				try {

					int res = circleArray.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;//表示数组最大容量

	//front变量的含义做一个调整：front就指向队列的第一个元素，也就是说arr[front]就是队列的第一个元素，front的初始值=0。

	private int front;//队列头部

	//rear变量的含义做一个调整：rear指向队列的最后一个元素的后一个位置。因为希望空出一个空间作为约定，rear的初始值=0。

	private int rear;//队列尾部

	private int[] arr;//该数组用于存放数据，模拟队列

	public CircleArray(int arrMaxSize) {

		maxSize = arrMaxSize;

		arr = new int [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("队列已满，无法加入数据~~");

			return;

		}

		//直接将数据加入

		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()) {

			System.out.println("队列为空，没有数据~~");

			return;

		}

		//思路：从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];

	}

}

运行截图：

最新文章

1. zone.js - 暴力之美
2. Bzoj4008 [HNOI2015]亚瑟王
3. MongoDB CURD 介绍
4. oracle基本用法
5. 【BZOJ-1853&2393】幸运数字&Cirno的完美算数教室 容斥原理 + 爆搜 + 剪枝
6. 老项目的#iPhone6于iPhone6Plus适配#iPhone6分辨率与适配
7. C#根据当前日期获取星期和阴历日期
8. 遇到EDIUS视频条全变灰色编辑不了如何处理
9. debian的备份与还原
10. asp.net post方法;对象转json
11. 浅谈页面无刷新技术ajax
12. svn命令操作
13. Easyui treegrid复选框设置
14. Android采取async框架文件上传
15. layui loading
16. WebRTC学习之ICE深入理解
17. java创建线程的方法
18. Linux开机自动启动某一程序
19. python Thread对象的setDaemon(True)的作用。
20. Linux+Redis实战教程_day02_2、redis简述及安装与启动

热门文章

1. Spring Cloud实战 | 第十一篇：Spring Cloud Gateway 网关实现对RESTful接口权限控制和按钮权限控制
2. codeforces 7B
3. spring boot集成mybatis只剩两个sql 并提示 Cannot obtain primary key information from the database, generated objects may be incomplete
4. js load more select
5. 如何使用 js 实现一个 throttle 函数
6. how to convert Map to Object in js
7. js uppercase the first letter of string
8. Firewall & Network Security
9. Transporter iOS App
10. Android Studio 4.x