数据结构与算法02 普通队列和环形队列
用数组来表示队列
编写一个ArrayQueue类
内容包括：
构造器，Java代码：
private int rear=-1;private int font=-1;private int maxSize;private int[] arr;//构造器public ArrayQueue(int arrMaxSize){maxSize=arrMaxSize;this.font=font;this.rear=rear;arr=new int[maxSize];}添加数据
//添加数据public int addQueue(int data){//队是否为满？if(rear==maxSize-1){System.out.println("队满，无法添加~~~");}rear++;arr[rear]=data;return arr[rear];}取出队头元素
//取出队头数据public int getFont(){//是否为空if(rear==font){System.out.println("队列空，无法取出~~");}font++;return arr[font];}展示队列所有元素
//展示所有数据public void showQueue(){if(rear==font){System.out.println("队空！无法展示！！");}for(int i=font+1;i<arr.length;i++){//设置为从font+1开始遍历System.out.println(arr[i]);}}查询队头元素
//查询队头元素public int getHeadData(){//是否为空if(rear==font){System.out.println("队空！！");}return arr[font+1];}在主函数中调用ArrayQueue类的方法，测试是否正确
利用scanner对象从键盘读入数据，代码：
public static void main(String[] args) {ArrayQueue q=new ArrayQueue(3);System.out.println("=====start test！！=====");System.out.println("输入 e 表示退出测试");System.out.println("输入 s 显示队列所有元素");System.out.println("输入 a 向队列添加元素");System.out.println("输入 g 获取队头元素并将其从队列移出");//这里的移除=出指的是font++System.out.println("输入 h 查看队头元素");char key=' ';boolean loop=true;while (loop){Scanner scanner=new Scanner(System.in);key=scanner.next().charAt(0);//键入的第一个数据switch (key){case 'e':System.out.println("退出测试!!!");loop=false;break;case 's':q.showQueue();break;case 'a':System.out.println("请输入一个数据：");int value=scanner.nextInt();q.addQueue(value);break;case 'g':System.out.println(q.getFont());break;case 'h':System.out.println(q.getHeadData());break;default:break;}}
}汇总代码：
package ArrayQueue;
import java.security.Key;
import java.util.Scanner;
public class Queue {public static void main(String[] args) {ArrayQueue q=new ArrayQueue(3);System.out.println("=====start test！！=====");System.out.println("输入 e 表示退出测试");System.out.println("输入 s 显示队列所有元素");System.out.println("输入 a 向队列添加元素");System.out.println("输入 g 获取队头元素并将其从队列移出");//这里的移除=出指的是font++System.out.println("输入 h 查看队头元素");char key=' ';boolean loop=true;while (loop){Scanner scanner=new Scanner(System.in);key=scanner.next().charAt(0);//键入的第一个数据switch (key){case 'e':System.out.println("退出测试!!!");loop=false;break;case 's':q.showQueue();break;case 'a':System.out.println("请输入一个数据：");int value=scanner.nextInt();q.addQueue(value);break;case 'g':System.out.println(q.getFont());break;case 'h':System.out.println(q.getHeadData());break;default:break;}}
}
}
class ArrayQueue{private int rear=-1;private int font=-1;private int maxSize;private int[] arr;//构造器public ArrayQueue(int arrMaxSize){maxSize=arrMaxSize;this.font=font;this.rear=rear;arr=new int[maxSize];}//添加数据public int addQueue(int data){//队是否为满？if(rear==maxSize-1){System.out.println("队满，无法添加~~~");}rear++;arr[rear]=data;return arr[rear];}//取出队头数据public int getFont(){//是否为空if(rear==font){System.out.println("队列空，无法取出~~");}font++;return arr[font];}//展示所有数据public void showQueue(){if(rear==font){System.out.println("队空！无法展示！！");}for(int i=font+1;i<arr.length;i++){//设置为从font+1开始遍历System.out.println(arr[i]);}}//查询队头元素public int getHeadData(){//是否为空if(rear==font){System.out.println("队空！！");}return arr[font+1];}
}
优化队列变成环形队列
优化思路：在普通队列基础上修改其方法，队列变成一个环形，为了便于观察理解我们使得初始时font=0，rear=0，并且当队满时rear指向队列最后一位元素的后一位（队满时rear指向的是空），即下面情况为队满：
由图得到队满时条件：(rear+1)%maxSize==font
队空条件仍然是：font==rear
队列中实际元素个数是：(rear-font+maxSize)%maxSize
主函数测试代码不变，只需要修改前文队列类的java代码：
判断队空
public boolean isempty(){if(rear==font){// System.out.println("队空！！！");return true;}return false;}判断队满
public boolean isfull(){if((rear+1)%maxSize==font){System.out.println("队满！！！");return true;}return false;}添加元素
public void addQueue(int data){if(isfull()){// System.out.println("队满，无法插入了~~");return;}//注意rear的更新问题// rear=(rear+1)%maxSize;arr[rear%maxSize]=data;rear++;System.out.println("插入的值是："+data);// return data;}展示队列所有元素
//展示队列所有数据public void showQueue(){if(isempty()){System.out.println("队空，无法展示~~");}//从font，遍历出所有有效的数据for(int i=font;i<font+(rear-font+maxSize)%maxSize;i++){System.out.println(arr[i%maxSize]);}}队头元素出队
//取出队头元素public int getFont(){if(isempty()){System.out.println("队空，无法取出队头~~");}//int value=arr[font];font++;return value;}查询队头元素
//查询队头元素public int getHeadData(){if(isempty()){System.out.println("队空，无法查询队头~~");}return arr[font];}汇总代码：
package ArrayQueue;
import java.util.Scanner;
public class CircleQueue {public static void main(String[] args) {circleQueue1 cqueue=new circleQueue1(4);//这里因为约定rear最终指向队列最后一个元素的后一位，所以虽然队列长度是4，但是实际上只有3个位置能存放元素System.out.println("=====start test！！=====");System.out.println("输入 e 表示退出测试");System.out.println("输入 s 显示队列所有元素");System.out.println("输入 a 向队列添加元素");System.out.println("输入 g 获取队头元素并将其从队列移出");//这里的移除=出指的是font++System.out.println("输入 h 查看队头元素");char key=' ';boolean loop=true;while (loop){Scanner scanner=new Scanner(System.in);key=scanner.next().charAt(0);//键入的第一个数据switch (key){case 'e':System.out.println("退出测试!!!");loop=false;break;case 's':cqueue.showQueue();break;case 'a':System.out.println("请输入一个数据：");int value=scanner.nextInt();cqueue.addQueue(value);break;case 'g':System.out.println("取出的队头元素是："+cqueue.getFont());break;case 'h':System.out.println(cqueue.getHeadData());break;default:break;}}}
}
class circleQueue1{private int rear=0;private int font=0;private int maxSize;private int[] arr;//构造器public circleQueue1(int arrMaxSize){maxSize=arrMaxSize;this.font=font;this.rear=rear;arr=new int[maxSize];}public boolean isempty(){if(rear==font){// System.out.println("队空！！！");return true;}return false;}public boolean isfull(){if((rear+1)%maxSize==font){System.out.println("队满！！！");return true;}return false;}//增public void addQueue(int data){if(isfull()){// System.out.println("队满，无法插入了~~");return;}//注意rear的更新问题// rear=(rear+1)%maxSize;arr[rear%maxSize]=data;rear++;System.out.println("插入的值是："+data);// return data;}//展示队列所有数据public void showQueue(){if(isempty()){System.out.println("队空，无法展示~~");}//从font，遍历出所有有效的数据for(int i=font;i<font+(rear-font+maxSize)%maxSize;i++){System.out.println(arr[i%maxSize]);}}//取出队头元素public int getFont(){if(isempty()){System.out.println("队空，无法取出队头~~");}//int value=arr[font];font++;return value;}//查询队头元素public int getHeadData(){if(isempty()){System.out.println("队空，无法查询队头~~");}return arr[font];}
}
每日打卡一道数据结构与算法！！冲刺一百天，我要进大厂！！冲呀！！
=======周末愉快==========