糖尿病康复 > Java数据结构：数组模拟的队列(Queue)和环形队列(Circle Queue)

Java数据结构：数组模拟的队列(Queue)和环形队列(Circle Queue)

时间：2021-02-06 14:02:10

一、应用场景

在银行排队进行服务的时候，通常会使用排队叫号的方法。如下图所示，四个小方块分别代表四个业务员，圆圈代表等待服务的顾客，圆圈中的数字代表客户的编号，号码大小根据客户排队顺序给出：

二、队列介绍

队列是一个有序列表，可以用数组或是链表来实现。遵循先入先出的原则。即：先存入队列的数据，要先取出。后存入的要后取出。示意图：(使用数组模拟队列示意图)

三、数组模拟队列

主要特点：front指向队列头部的前一个位置，rear指向队列的最后一个元素判断队列满的条件是rear-1==maxSize判断队列空的条件是rear==front出现问题：显然这样的方法是存在问题的，当使用一次以后，rear-1恒等于maxSize，会存在假溢出问题。因此前面的空位置就不能使用，整个队列不能达到复用的效果。解决办法：使用算法，将数组改为一个环形的数组。

四、数组模拟环形队列

主要特点：front指向队列头部，rear指向队列的最后一个元素的后一个位置判断队列满的条件是(rear+1)%maxSize==front判断队列空的条件是rear==front队列当中有效数据的大小：(rear-front+maxSize)%maxSize存在一个预留空间（可以通过运行代码结果观察到，创建一个大小为4的队列，实际上只能存储3个元素）代码：

package ds.sp.queue;import java.util.Scanner;public class CircleQueueDemo {public static void main(String[] args){// 测试：CircleQueue cq=new CircleQueue(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(show):退出程序");System.out.println("a(add):添加数据到队列");System.out.println("g(get):从队列取出数据");System.out.println("h(head):查看队列头部的数据");key=scanner.next().charAt(0);//接受一个字符switch (key){case 's':cq.showQueue();break;case 'a':System.out.println("请输入一个整数数值");int value=scanner.nextInt();cq.addQueue(value);break;case 'g':cq.getQueue();break;case 'h':System.out.println(cq.headQueue());break;default:break;}}System.out.println();}}class CircleQueue{private int maxSize;//表示数组的最大容量。private int rear;// 指向最后一个元素的后一个位置。rear的初始值为0.private int front;// 指向第一个元素。也就是说arr[front]是队列的第一个元素；// front的初始值为0.private int[] arr;public CircleQueue(int arrMaxSize){maxSize=arrMaxSize;arr=new int[maxSize];front=0; //指向队列头部rear=0; //指向队列尾部}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+1)%maxSize;}public int getQueue(){//判断队列空if(isEmpty()){//*如果为空通过抛出异常来处理throw new RuntimeException("队列为空，不能取数据。");}// 这里需要分析出front是指向队列的第一个元素// 1、先把front的值保留到一个临时变量当中// 2、将front向后移，同时要考虑取值// 3、把临时保存的值返回int temp=front;front=(front+1)%maxSize;return arr[temp];}public int size(){return (rear-front+maxSize)%maxSize;}public void showQueue(){//队列展示if(isEmpty()){System.out.println("数列为空。");return;}for(int i=front;i<front+size();i++){System.out.printf("arr=[%d]=%d\n",i%maxSize,arr[i%maxSize]);}}// 显示头元素public int headQueue(){if(isEmpty()){throw new RuntimeException("队列为空，不能取数据。");}return arr[front];}