队列

队列是一个有序列表，可以用数组或链表实现

队列遵循先进先出的原则，也就是说先进队列的数据，要先出队列

数组模拟队列

• 队列的本身是有序的列表，如果使用数组的结构来存储队列的数据，那么该队列是有一个最大容量，我们称为maxSize

• 因为队列他有输入和输出，输入输出分别从前后端来处理，因此需要两个变量front和rear分别记录队列的前后端的下标，front随着数据的输出而改变，rear随着数据的输入而改变

存入队列(addQueue)

当我们将数据存入到对列时，称为addQueue，存入时需要两个步骤：

• 将尾指针往后移：rear+1，特别注意：当front==rear时，我们认为队列为空

• 如果rear小于队列的最大小标maxSize-1，那么数据就可以存入到rear所指的数组元素中，否则无法存入数据

• 当rear=maxSize-1时，我们认为队列已经满了。

代码实现

// 使用数组模拟一个队列-编写一个ArrayQueue类
static class ArrayQueue{private int maxSize;// 队列的最大容量private int front; // 队列头private int rear;// 队列尾private int[] arr;// 数组用于，模拟队列
​// 创建队列构造器public ArrayQueue(int arrMaxSize){maxSize=arrMaxSize;arr=new int[maxSize];front=-1;rear=-1;}
​// 判断队列是否满public boolean isFull(){return rear==maxSize-1;}
​// 判断队列是否为空public boolean isEmpty(){return front==rear;}
​// 添加数据到队列public void addQueue(int val){// 判断队列是否满if (isFull()){throw new RuntimeException("队列已满，无法添加元素");}rear++;arr[rear]=val;}
​// 获取队列数据，出队列public int getQueue(){// 判断队列是否为空if (isEmpty()){throw new RuntimeException("队列为空");}front++;return arr[front];}
​// 显示队列所有的数据public void showQueue(){if (isEmpty()){System.out.println("队列为空，没有数据");return;}for (int i = 0; i < arr.length; i++) {System.out.println(arr[i]);}}
​// 显示队列头元素public int peek(){// 判断if (isEmpty()){throw new RuntimeException("队列为空");}return arr[front+1];}}

这个方法是对以上我们写的队列方法的一个测试

public static void main(String[] args) {// 创建一个队列ArrayQueue arrayQueue = new ArrayQueue(3);// 添加数据arrayQueue.addQueue(3);arrayQueue.addQueue(1);arrayQueue.addQueue(2);// 显示所有元素arrayQueue.showQueue();//出队列(结果是最开始进入队列的元素3)System.out.println(arrayQueue.getQueue());//获取头元素(由于我们前面进行了一次出队列，所以这里我们的头元素就是1)System.out.println(arrayQueue.peek());arrayQueue.addQueue(4);// 报异常 java.lang.RuntimeException: 队列已满，无法添加元素
}

问题

这里我们发现，明明已经把元素3队列了，为什么我们再次加元素4反而报了异常，说我们队列已满，这里就是我们此次构造的队列的复用性不够，当我们在进行出队列等方法时，我们的头指针和尾指针也在移动，这就导致我们前面已经用过的位置 虽然没有了元素，当他的位置还在占用，所以其复用性不够