队列
- 队列是一个有序列表，可以用
数组(顺序存储)或是链表(链式存储)来实现。 - 遵循
先入先出的原则。即：先存入队列的数据，要先取出。后存入的要后取出。
使用数组模拟队列
- 队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图，其中maxSize是该队列的最大容量。
- 因为队列的输出，输入是分别从前后端来处理，因此需要两个变量front及rear分别记录队列前后端的下标，front会随着数据输出从而改变，而rear则是随着数据输入而改变。
如图所示：
思路分析：
当我们将数据存入队列时称为
addQueue，addQueue的处理需要有两个步骤
- 将尾指针往后移：
rear+1，当front == rear[空] - 若尾指针
rear小于队列的最大下标maxSize - 1，则将数据存入rear所指的数组元素中，否则无法存入数据。rear == maxSize -1[队列满]。
代码实现：
使用数组模拟队列，编写一个ArrayQueue类
class ArrayQueue{ private int maxSize; //表示数组的最大容量 private int front; //队列头 private int rear; //队列尾 private int [] arr; //该数组用于存放数据，模拟队列 //创建队列的构造器 public ArrayQueue(int arrMaxSize){ this.maxSize=arrMaxSize; this.arr=new int[this.maxSize]; this.front=-1; //指向队列头部，分析出front是指向队列头的前一个位置。 this.rear=-1; //指向队列尾，指向队列尾的数据(就是队列中最后一个数据)。 } //判断队列是否满 public boolean isFull(){ return this.rear == this.maxSize-1; } //判断队列是否为空 public boolean isEmpty(){ return this.rear == this.front; } //添加数据到队列 public void addQueue(int n){ if (isFull()){ System.out.println("队列满，不能加入数据"); return; } this.rear++; //让rear后移 this.arr[rear]=n; } //获取队列的数据，出队列 public int getQueue(){ //判断队列是否为空 if (isEmpty()){ //通过抛出异常 throw new RuntimeException("队列空，不能取数据"); } front++; //front后移 return arr[front]; } //显示队列的所有数据 public void showQueue(){ if (isEmpty()){ System.out.println("队列空，没有数据"); } for (int i=0;i<arr.length;i++){ System.out.printf("arr[%d]=%d\n",i,arr[i]); } } //显示队列的头数据，注意：不是取数据 public int headQueue(){ //判断 if (isEmpty()){ throw new RuntimeException("队列空的，没有数据"); } return arr[front+1]; } }
对模拟队列进行测试
public static void main(String[] args) { ArrayQueue arrayQueue= new ArrayQueue(3); Scanner inpunt =new Scanner(System.in); Boolean b=true; do { switch (inpunt.nextInt()){ case 1:{ try { System.out.println("显示队列所有数据"); arrayQueue.showQueue(); }catch (Exception e){ e.printStackTrace(); } break; } case 2:{ System.out.println("添加数据到队列"); arrayQueue.addQueue(inpunt.nextInt()); break; } case 3:{ try { System.out.println("显示队列的头数据"); int headQueue = arrayQueue.headQueue(); System.out.println("队列头："+headQueue); }catch (Exception e){ e.printStackTrace(); } break; } case 4:{ try { System.out.println("从队列中取数据"); int queueQueue = arrayQueue.getQueue(); System.out.println("取数据："+queueQueue); }catch (Exception e){ e.printStackTrace(); } break; } default:{ b=false; } } }while (b); }
- 测试1：添加数据并显示队列所有数据
可以看出现在队列中添加了三个数据分别为 10,20,30
测试2：查看头数据，然后取出数据后，再次查看头数据 因为队列遵循先进先出的原则，这边取完数据再查看队列，头数据为第二次添加的数据。
测试3：取出所有数据在添加数据。注意看这里，当我们数据取完后，在添加数据就会出现问题。
问题分析及优化：
- 目前我们的数组使用一次就不能用了，没有达到复用的效果。
- 我们可以将这个数组使用算法改进成一个环形的队列。
使用数组模拟环形队列
思路分析
- front变量的含义做一个调整，front就指向队列的第一个元素，也就是说 arr[front]就是队列的第一个元素，front的初始值 = 0；
- rear 变量的含义也做一个调整，rear指向队列的最后一个元素的最后一个位置。因为希望空出一个空间做为约定。rear的初始值也 = 0;
- 当队列满时，条件是
（rear+1）% maxSize = front [满] - 当队列为空的条件是
rear == front空。 - 队列中有效数据的个数
(rear+maxSize-front)%maxSize// rear = 1 front = 0
代码实现
对前面的数组模拟队列进行优化，充分利用数组，因此将数组看作是一个环形的。(通过取模的方式来实现即可)
class CircleArray{ private int maxSize; //表示数组的最大容量 //front变量的含义做一个调整，front就指向队列的第一个元素，也就是说 arr[front]就是队列的第一个元素，front的初始值 = 0； private int front; //rear 变量的含义也做一个调整，rear指向队列的最后一个元素的最后一个位置。因为希望空出一个空间做为约定。rear的初始值也 = 0; private int rear; private int [] arr; //该数组用于存放数据，模拟队列 public CircleArray(int arrMaxSize){ maxSize = arrMaxSize; arr = new int[maxSize]; } //判断队列是否满 public boolean isFull(){ return (rear + 1) % maxSize == front; } //判断队列是否为空 public boolean isEmpty(){ return this.rear == this.front; } //添加数据到队列 public void addQueue(int n){ if (isFull()){ System.out.println("队列满，不能加入数据"); return; } //直接将数据加入 arr[rear] = n; //将 rear 后移，这里必须考虑去模 rear = (rear + 1) % maxSize; } //获取队列的数据，出队列 public int getQueue(){ //判断队列是否为空 if (isEmpty()){ //通过抛出异常 throw new RuntimeException("队列空，不能取数据"); } /** * 这里需要分析出 front 是指向队列的第一个元素 * 1.先把 front 对应的值保留到一个临时变量 * 2.将 front 后移，考虑取模 * 3.将临时保存的变量返回 */ int value = arr[front]; front = (front + 1) % maxSize; return value; } //显示队列的所有数据 public void showQueue(){ //遍历 if (isEmpty()){ throw new RuntimeException("队列空，没有数据"); } //思路：从front开始遍历，遍历多少个元素 for (int i= front; i < front + size();i++){ System.out.printf("arr[%d]=%d\n",i % maxSize,arr[i % maxSize]); } } //求出当前队列有效数据的个数 public int size(){ return (rear + maxSize - front) % maxSize; } //显示队列的头数据，注意：不是取数据 public int headQueue(){ //判断 if (isEmpty()){ throw new RuntimeException("队列空的，没有数据"); } return arr[front]; } }
对环形队列进行测试
public static void main(String[] args) { //测试数组模拟环形队列 CircleArray circleArray= new CircleArray(4); //设置4,其队列的有效数据最大是3 Scanner inpunt =new Scanner(System.in); Boolean b=true; do { switch (inpunt.nextInt()){ case 1:{ try { System.out.println("显示队列所有数据"); circleArray.showQueue(); }catch (Exception e){ e.printStackTrace(); } break; } case 2:{ System.out.println("添加数据到队列"); circleArray.addQueue(inpunt.nextInt()); break; } case 3:{ try { System.out.println("显示队列的头数据"); int headQueue = circleArray.headQueue(); System.out.println("队列头："+headQueue); }catch (Exception e){ e.printStackTrace(); } break; } case 4:{ try { System.out.println("从队列中取数据"); int queueQueue = circleArray.getQueue(); System.out.println("取数据："+queueQueue); }catch (Exception e){ e.printStackTrace(); } break; } default:{ b=false; } } }while (b); }
- 测试1往环形队列中添加数据
- 测试2 从环形队列中取数据
- 测试3 取数据后重新添加数据
