基本介绍
队列是一个有序列表,可以用数组或者链表来实现
遵循先入先出的原则,即先存入队列的数据,要先取出.后存入的要后取出
数组模拟队列
队列本身是有序列表,若使用数组的结构来存储队列的数据,则队列数组的声明如下图,其中maxSize是该队列的最大容量.
因为队列的输入\输出是分别从前后端来处理,因此需要两个变量front及rear分别记录队列前后端的下标,front会随着数据输出而改变,而rear则是随着数据输入而改变.
代码案例
- package com.structures.queue;
- 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(add):添加数据到队列");
- 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();
- arrayQueue.addQueue(value);
- break;
- case 'g':
- try {
- int queue = arrayQueue.getQueue();
- System.out.printf("取出的数据是%d", queue);
- }catch (Exception e){
- System.out.println(e.getMessage());
- }
- break;
- case 'e':
- scanner.close();
- loop = false;
- break;
- case 'h':
- try {
- int head = arrayQueue.headQueue();
- System.out.printf("取出队列头的数据是%d", head);
- }catch (Exception e){
- System.out.println(e.getMessage());
- }
- 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++;//让rear 后移
- arr[rear] = n;
- }
- //获取队列数据,出队列
- public int getQueue() {
- if (isEmpty()) {
- throw new RuntimeException("队列为空,不能取数据");
- }
- front++;
- return arr[front];
- }
- //显示队列所有数据
- public void showQueue() {
- if (isEmpty()) {
- System.out.println("队列为空,没有数据");
- }
- for (int i = 0; i < this.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];
- }
- }
问题分析
改进成环形队列的思路分析
环形队列代码案例
- package com.structures.queue;
- import java.util.Scanner;
- public class CircleArrayQueue {
- public static void main(String[] args) {
- CircleArray arrayQueue = 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':
- arrayQueue.showQueue();
- break;
- case 'a':
- System.out.println("输入一个整数");
- int value = scanner.nextInt();
- arrayQueue.addQueue(value);
- break;
- case 'g':
- try {
- int queue = arrayQueue.getQueue();
- System.out.printf("取出的数据是%d", queue);
- }catch (Exception e){
- System.out.println(e.getMessage());
- }
- break;
- case 'e':
- scanner.close();
- loop = false;
- break;
- case 'h':
- try {
- int head = arrayQueue.headQueue();
- System.out.printf("取出队列头的数据是%d", head);
- }catch (Exception e){
- System.out.println(e.getMessage());
- }
- 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("队列为空,没有数据");
- }
- //从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];
- }
- }
本文转载自公众号读芯术(ID:AI_Discovery) 下面这个模型在一项图像识别竞赛中经...
据IDC评述网(idcps.com)报道,ntldstats.com最新数据显示,截止至2016年3月31...
TOP云 (west.cn)8月14日消息,本期的sedo 域名交易 榜共有63个 域名 超2000美...
云计算服务正在以前所未有的速度在各行各业快速普及,成为IT应用的最主流实现形...
【编者的话】本文作者利用自己云原生工程师的优势,分享了他对2021年及之后的云...
步入2月,美股新一轮财报季渐入高潮。 本周二,包括阿里巴巴、亚马逊、谷歌在内...
Cloud-init是开源的云初始化程序,能够对新创建弹性云服务器中指定的自定义信息...
每年618是年中购物节,每到这一天,大家都会进入网购模式,疯狂的买买买。618购...
1. 接口描述 接口请求域名: cvm.tencentcloudapi.com 。 本接口 (ResetInstance...
操作场景 本节操作介绍在Windows和Linux环境中使用SSH密钥对方式远程登录Linux云...