队列（Queue）
队列是一个有序列表，可以用数组或是链表实现
遵循先入先出的原则，即先存入的数据先取出，后存入的数据后取出
数组模拟队列
队列本身是有序列表，若使用数组的结构来存储队列的数据，则将该数组称为队列数组
思路分析
maxSize是队列的最大容量，也就是数组的空间大小
front和rear都是数组的下标，用来记录队列的存入或取出的位置，即队列的头和尾
代码实现
（1）先定义一个队列类
classArrayQueue{privateint maxSize;//表示数组的最大容量privateint rear;//队列尾，随着数据的存入而改变privateint front;//队列头，随着数据的取出而改变privateint[] arr;//该数组用于存放数据,模拟队列//构造方法，直接创建一个maxSize大小的数组存储数据publicArrayQueue(int maxSize){this.maxSize= maxSize;this.arr=newint[maxSize];this.front=-1;//指向队列头部的前一个this.rear=-1;//指向队列的最后一个数据的具体位置}}（2）判断队列是否满或空
//当队列满时，rear应该指向数组最后一个数据publicbooleanisFull(){return rear== maxSize-1;}//当队列空时，front和rear相等publicbooleanisEmpty(){return rear== front;}（3）添加数据
先判断队列是否满，如果满则添加失败
因为rear指向数组中最后一个数据，添加数据时应该先往后指一个位置，在该位置添加数据
publicbooleanaddQueue(int val){//判断队列是否满if(this.isFull()){
System.out.println("队列已满,不能加入");returnfalse;}else{this.rear++;
arr[rear]= val;returntrue;}}（4）取出数据
先判断队列是否空，如果空则取出数据失败
队列的数据取出从头部开始，即front指向的下一个数据，因此front先往后指一个位置，从该位置取出数据
publicintgetQueue(){if(this.isEmpty()){//通过抛出异常处理thrownewRuntimeException("队列为空,不能取数据");}else{this.front++;return arr[front];}}（5）遍历数据
数组的遍历方法
publicvoidshowQueue(){if(isEmpty()){
System.out.println("队列为空,无数据");return;}for(int i=this.front+1; i< arr.length; i++){
System.out.printf("%d\n",arr[i]);}}（6）显示头数据
注意不是取出
publicintheadQueue(){if(isEmpty()){thrownewRuntimeException("队列为空,无数据");}else{return arr[front+1];}}循环队列
因为数组队列会造成空间的浪费，因此使用循环队列来进一步优化
调整思路
1、front变量的含义做调整：front指向队列打的第一个元素，即arr[front]就是队列的第一个元素，初始值为0
2、rear变量的含义做调整：rear指向队列的最后一个元素的最后一个位置，因此队列需要空出一个位置，来作为队列是否满的标识，初始值为0
3、循环队列时，rear指向最后一个有效数据的下一个位置，因此判断队列是否满时，说明rear+1应该等于front：(rear+1) % maxSize == front
4、当队列为空时，rear == front
5、判断原始队列有效数据时，一般为rear-front，但循环队列时，可能会出现front > rear的情况，因此为保证结果为正数，判断循环队列有效数据为：(rear - front + maxSize) % maxSize
代码实现
（1）先定义一个队列类，成员变量不变，意义改变
privateint maxSize;//表示数组的最大容量privateint rear;//队列尾:指向最后一个有效数据的下一个privateint front;//队列头:指向第一个有效数据privateint[] arr;//该数据用于存放数据,模拟队列//创建队列的构造器publicCircleArray(int maxSize){this.maxSize= maxSize;this.arr=newint[maxSize];this.front=0;this.rear=0;}}（2）判断队列是否满或空
publicbooleanisFull(){return(this.rear+1)% maxSize== front;}publicbooleanisEmpty(){return rear== front;}（3）添加数据
rear意义改变，为最后一个有效数据的下一个位置，因此可以先添加在rear的位置，在 将rear向后移一个
publicbooleanaddQueue(int val){//判断队列是否满if(this.isFull()){
System.out.println("队列已满,不能加入");returnfalse;}else{
arr[rear]= val;
rear=(rear+1)% maxSize;returntrue;}}（4）取出数据
从front指向的位置取出
publicintgetQueue(){if(this.isEmpty()){//通过抛出异常处理thrownewRuntimeException("队列为空,不能取数据");}else{//front指向队列的第一个元素//1 先把front对应的值保存到一个临时变量//2 将front后移int val= arr[front];
front=(front+1)% maxSize;return val;}}（5）求当前队列有效数据个数及遍历队列
publicintsize(){return(rear- front+ maxSize)% maxSize;}//显示队列所有数据publicvoidshowQueue(){if(isEmpty()){
System.out.println("队列为空,无数据");return;}int count=size();for(int i= front; i< front+ count; i++){
System.out.printf("%d\n",arr[i% maxSize]);}}（6）显示头数据
注意不是取出
publicintheadQueue(){if(isEmpty()){thrownewRuntimeException("队列为空,无数据");}else{return arr[front];}}（7）测试类
publicclassCircleArrayQueue{publicstaticvoidmain(String[] args){
CircleArray arrayQueue=newCircleArray(4);char key=' ';//接收用户输入
Scanner scan=newScanner(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= scan.next().charAt(0);//接受一个字符串switch(key){case's':
arrayQueue.showQueue();break;case'e':
scan.close();
loop=false;break;case'a':
System.out.println("请输入添加的值");int val= scan.nextInt();
arrayQueue.addQueue(val);break;case'g':try{int temp= arrayQueue.getQueue();
System.out.println("取出的值为"+ temp);}catch(Exception e){
System.out.println(e.getMessage());}break;case'h':try{int res= arrayQueue.headQueue();
System.out.println("头数据为"+ res);}catch(Exception e){
System.out.println(e.getMessage());}break;}}}}循环队列关键点：脚标的改变以及对%的理解运用