一、队列简介
队列是一种采用先进先出(FIFO)策略的抽象数据结构，它的想法来自于生活中排队的策略。
二、用数组模拟队列
package Queue; import java.util.Scanner; public class ArrayQueue { //用数组模拟队列 private int maxsize;//队列的最大容量 private int front;//队列头 private int rear;//队列尾 private int[] arr;//模拟队列 //创建队列的构造器 public ArrayQueue(int arrMaxsize){ this.maxsize=arrMaxsize; arr=new int[arrMaxsize]; front=-1;//指向队列头的前一个位置 rear=-1;//指向队列尾 } //判断队列是否已满 public boolean isFull(){ return rear==maxsize-1; } //判断队列是否为空 public boolean isEmpty(){ return rear==front; } //向队列中添加元素 public void add(int n){ if(isFull ()){ System.out.println ("队列已满，无法继续添加元素！" ); return; } arr[++rear]=n; System.out.println ("添加成功！" ); } //删除队列的元素 public void delete(){ if(isEmpty ()){ throw new RuntimeException ("队列为空，无法添加元素"); } front++; System.out.println ("删除成功" ); } //显示队列的所有数据 public void show(){ if(isEmpty ()){ System.out.println ("队列为空，无数据" ); return; } System.out.println ("队列中的元素为：" ); for(int i=front+1;i<=rear;i++){ System.out.printf("%d\n",arr[i]); } } //取队头元素 public int getFront(){ if(isEmpty ()){ throw new RuntimeException ("队列为空，无法取出队头元素"); } return arr[front+1]; } public void menu(){ System.out.println ("a(add):向队列中添加元素" ); System.out.println ("d(delete):删除队列元素" ); System.out.println ("s(show):展示队列元素" ); System.out.println ("g(getHead):获取队头元素" ); System.out.println ("e(exit):退出程序" ); } public static void main(String[] args) { ArrayQueue arrayQueue = new ArrayQueue (10); Scanner sc=new Scanner (System.in); char ch; boolean loop=true; while(loop){ arrayQueue.menu(); ch=sc.next ().charAt (0); switch (ch){ case 'a': System.out.println ("请输入要添加的元素" ); int n=sc.nextInt (); arrayQueue.add (n); break; case 's' :arrayQueue.show (); break; case 'd':arrayQueue.delete ();break; case 'g': System.out.println ("队头元素为:" +arrayQueue.getFront ()); break; case 'e' :loop=false; break; default: System.out.println ("您的输入有误！" ); } } } }
三、环形队列
数组模拟队列存在问题：目前数组只能使用一次，不能复用
故将数组使用算法进行改进为一个环形队列取模：%
思路如下：
1.front变量含义变为指向队列的第一个元素，初始值为0
2.rear变量含义为指向队列的后一个元素的后一个位置，初始值为0
3.队列满时：（rear+1）%maxsize==front
4.队列空时：rear==front
5.队列中有效数据的个数：（rear-front+maxsize）%maxsize
package Queue; import java.util.Scanner; public class CircleArrayQueue { //用数组模拟队列 private int maxsize;//队列的最大容量 private int front;//队列头 private int rear;//队列尾 private int[] arr;//模拟队列 //创建队列的构造器 public CircleArrayQueue(int arrMaxsize){ this.maxsize=arrMaxsize; arr=new int[arrMaxsize]; front=0;//指向队列的第一个位置 rear=0;//指向队列最后一个元素的后一个位置 } //判断循环队列是否已满 public boolean isFull(){ return (rear+1)%maxsize==front; } //判断循环队列是否为空 public boolean isEmpty(){ return rear==front; } //向队列中添加元素 public void add(int n){ if(isFull ()){ System.out.println ("队列已满，无法继续添加元素！" ); return; } //直接将数组加入 arr[rear]=n; //将rear后移，这里必须考虑取模 rear=(rear+1)%maxsize; System.out.println ("添加成功！" ); } //删除队列的元素 public void delete(){ if(isEmpty ()){ throw new RuntimeException ("队列为空，无法添加元素"); } front=(front+1)%maxsize;//防止越界 System.out.println ("删除成功" ); } //显示队列的所有数据 public void show(){ if(isEmpty ()){ System.out.println ("队列为空，无数据" ); return; } System.out.println ("队列中的元素为：" ); for(int i=front;i<rear;i++){ System.out.printf("%d\n",arr[i]); } } //取队头元素 public int getFront(){ if(isEmpty ()){ throw new RuntimeException ("队列为空，无法取出队头元素"); } return arr[front];//front指向队列第一个元素 } public void menu(){ System.out.println ("a(add):向队列中添加元素" ); System.out.println ("d(delete):删除队列元素" ); System.out.println ("s(show):展示队列元素" ); System.out.println ("g(getHead):获取队头元素" ); System.out.println ("e(exit):退出程序" ); } public static void main(String[] args) { Queue.ArrayQueue arrayQueue = new Queue.ArrayQueue (10); Scanner sc=new Scanner (System.in); char ch; boolean loop=true; while(loop){ arrayQueue.menu(); ch=sc.next ().charAt (0); switch (ch){ case 'a': System.out.println ("请输入要添加的元素" ); int n=sc.nextInt (); arrayQueue.add (n); break; case 's' :arrayQueue.show (); break; case 'd':arrayQueue.delete ();break; case 'g': System.out.println ("队头元素为:" +arrayQueue.getFront ()); break; case 'e' :loop=false; break; default: System.out.println ("您的输入有误！" ); } } } }
