什么是队列？
队列是一个有序列表，可以用数组或链表来实现。遵循先入先出的原则。
我们来用代码实现一个简单的队列
public class ArrayQueue<T> { private int maxSize;//表示数组的最大容量 private int front;//队列头 private int rear;//队列尾 private T[] arr;//用于存放数据的数组 public ArrayQueue(int arrMaxSize){ this.maxSize = arrMaxSize; Object[] objects = new Object[maxSize]; arr = (T[]) objects; front = -1;//指向队列头的前一个位置 rear = -1;//指向队列最后一个数据 } //判断队列是否满 public boolean isFull(){ return rear == maxSize-1; } //判断队列是否为空 public boolean isEmpty(){ return rear == front; } //往队列添加数据 public void add(T value){ //如果队列满了就不能添加 if(isFull()){ System.out.println("队列已满，不能添加数据"); return; } //rear后移，添加数据 arr[++rear] = value; } //从队列中取出数据 public T get(){ //如果队列是空，抛出异常 if(isEmpty()){ throw new RuntimeException("队列为空，不能取出数据"); } return arr[++front]; } //显示队列中的所有数据 public void show(){ if(isEmpty()){ System.out.println("队列为空"); return; } for (int i = 0; i <= rear; i++) { System.out.println(arr[i].toString()); } } //显示队列头的数据 public T head(){ if(isEmpty()){ throw new RuntimeException("队列为空"); } return arr[front+1]; } }
这种队列存在一个问题，就是在存入数据再取出后，front会指向最后取出的数据的位置，如果之前存入并取出的数据已经到了队列可以存入数据的最大值，这时候再存入数据就会提示队列已满。即，这个队列是一次性的，只能使用一次。
针对这个问题进行优化，可以把这个单向队列优化成一个环形队列。
思路分析：
1，front变量的含义做一个调整：front指向队列的一个元素，也就是说arr[front]就是队列的一个元素
front初始值为0
2，rear变量的含义做一个调整：rear指向队列的最后一个元素的后一个位置，因为希望留出一个空间作为约定。
rear的初始值为0
3，判断队列满的条件：（rear+1）%maxSize == front 就是满
4，判断队列为空的条件：rear == front 就是空
5，队列中有效数据的个数：（rear+maxSize-front）%maxSize
代码实现：
public class CircleQueue<T> { int maxSize;//表示数组的最大容量 /*front指向队列的一个元素，也就是说arr[front]就是队列的一个元素 front初始值为0*/ int front;//队列头 /*rear指向队列的最后一个元素的后一个位置，因为希望留出一个空间作为约定。 rear的初始值为0*/ int rear;//队列尾 private T[] arr;//用于存放数据的数组 public CircleQueue(int arrMaxSize){ this.maxSize = arrMaxSize; Object[] objects = new Object[maxSize]; arr = (T[]) objects; //int类型默认值就是0，下面两句可以不写 front = 0;//指向队列头的前一个位置 rear = 0;//指向队列最后一个数据 } //判断队列是否满 public boolean isFull(){ return (rear+1)%maxSize == front; } //判断队列是否为空 public boolean isEmpty(){ return rear == front; } //往队列添加数据 public void add(T value){ //如果队列满了就不能添加 if(isFull()){ System.out.println("队列已满，不能添加数据"); return; } //直接加入数据 arr[rear] = value; //将rear后移，这里使用取模，因为环形队列要复用数组 rear = (rear+1) % maxSize; } //从队列中取出数据 public T get(){ //如果队列是空，抛出异常 if(isEmpty()){ throw new RuntimeException("队列为空，不能取出数据"); } //先把front对应的值保存到一个变量，然后将front后移，这里也得使用取模，不然会角标越界 T val = arr[front]; front = (front +1) % maxSize; return val; } //显示队列中的所有数据 public void show(){ if(isEmpty()){ System.out.println("队列为空"); return; } //从front开始遍历，遍历 front+有效数据的个数 次 for (int i = front; i <= front + size(); i++) { System.out.printf(arr[i].toString()); } } //计算队列中的有效数据的个数 public int size(){ return (rear+maxSize-front)%maxSize; } //显示队列头的数据 public T head(){ if(isEmpty()){ throw new RuntimeException("队列为空"); } return arr[front]; } }
