数据结构与算法-环形队列

1.简介

针对简单队列中数组使用一次就不能用，无法复用的问题，将这个数组改成一个环形队列，使得数据取出后这个空间能够再次使用。

2.思路分析

1.将front变量的含义做调整，使得front指向队列的第一个元素（原先简单队列中front是指向队列第一个元素的前一个位置），也就是说arr[front]就是队列的第一个元素，front初始值为0.

2.将rear变量的含义做调整，使得rear指向队列最后一个元素的后一个位置。rear初始值为0.因为希望空出一个空间作为一个约定。（如果不预留空间，rear指向最后一个元素，无法判断队满和队空）

3.当队列满时，条件为(rear+1) % maxSize == front（注：原来简单队列队列满的条件是rear=maxSize-1。那么环形队列满的条件可以看成是原来的式子左右两边同时加1，然后模上这个maxSize，然后结果为front）

还可以记成：这不是叫环形队列吗？那就是个环，转一圈之后又到起点。那么尾指针的后面还有个预留空间，队满的时候尾指针加上1就跳过这个预留空间了，就到了新一轮的队头，就是front。尾指针和头指针都指向同一个元素了这不就是满了吗？

4.当队列空时，条件为rear==front

5.获取队列中有效的数据的个数。

（rear+maxSize-front）%maxSize

3.将数据加入队列思路

先判断是否队满，没满就QueueArr[rear] = n，因为rear指的是队尾数据的后一个，所以不用先rear+1.然后，赋值之后再将rear指针移位，不过不是直接rear+1，而是(rear+1)%maxSize，环形队列嘛，取模。

4.从队列取出数据思路

因为front直接指的是队头位置，先判断队列是否为空。不空就可以取数据。要取的数据直接是QueueArr[front]。然后，这个数据要保存到一个临时变量res，即res= QueueArr[front]。如果不保存的话front就没有后移的机会了。保存之后将front后移，也不是直接front+1，而是记住，环形队列，取模。front=(front+1)%maxSize。返回的结果就是前面保存的临时变量res。

5.判断队列满和空

(rear + 1) % maxSize == front则队满

rear == front则队空

6.获取队列有效元素个数

前面思路分析里说的环形队列有效元素个数为(rear + maxSize - front) % maxSize

7.显示队列所有数据

先判断队列是否为空。不空就遍历。不过这里要注意遍历时，我们以前简单队列中是for(int i=0;i<arr.length;i++)然后在循环里输出arr[i]。但是这里取i<arr.length就不行了，有可能前面的数据被取出了，显示出全部数组数据也没有意义。我们从front开始遍历，要遍历的元素个数就是前面的队列有效元素个数size。在循环里输出的也不是arr[i]而是arr[i%maxSize]，下标也取模

for(int i=front;i<front+size();i++){

System.out.printf(“QueueArr[%d]=%d\n”,i%maxSize,QueueArr[i%maxSize]);

}

8.代码

java">package com.xjj.queue;import java.util.Scanner;public class CircleQueue {public static void main(String[] args) {System.out.println("数组模拟环形队列");//创建一个队列MyCircleQueue circleQueue = new MyCircleQueue(4);//设置的4，可用的是3，即队列的有效数据个数最大为3//测试从控制台输入数据到队列char key = ' ';//接收用户输入Scanner scanner = new Scanner(System.in);boolean loop = true;while (loop) {System.out.print("s(show)展示队列\t");System.out.print("e(exit)退出\t");System.out.print("a(add)添加数据\t");System.out.print("g(get)取出数据\t");System.out.print("h(head)查看队头数据\t\n");key = scanner.next().charAt(0);//接收一个字符switch (key) {case 's':circleQueue.showQueue();break;case 'a':System.out.println("添加一个数据");try {int value = scanner.nextInt();//假如需要输入一个整数circleQueue.addQueue(value);} catch (Exception e) {System.out.println(e.getMessage());}break;case 'g':try {//这里用try catch是因为可能有异常抛出int res = circleQueue.getQueue();System.out.printf("取出的数据为：%d\n", res);} catch (Exception e) {System.out.println(e.getMessage());//这里的e.getMessage()就是方法里的异常消息}break;case 'h':try {int res = circleQueue.headQueue();System.out.printf("队头数据为：%d\n", res);} catch (Exception e) {System.out.println(e.getMessage());}break;case 'e':scanner.close();//关闭输入loop = false;break;default:break;}}System.out.println("程序退出");}
}//用数组模拟队列
class MyCircleQueue {private int maxSize;//队列的最大容量private int front;//队列头，指向队列头，初始值为0private int rear;//队列尾，指向队列最后一个元素的后一个位置private int[] QueueArr;//用于存放数据的数组，模拟队列//先创建队列的构造器public MyCircleQueue(int arrMaxSize) {maxSize = arrMaxSize;QueueArr = new int[maxSize];front = 0;//指向队列头部位置。rear = 0;//指向队列尾部。指向队列尾部的后一个数据（就是直接是队列最后一个数据后面一个）}//判断队列是否满public boolean isFull() {return (rear + 1) % maxSize == front;//根据思路分析里来，取模}//判断队列是否空public boolean isEmpty() {return rear == front;}//添加数据到队列public void addQueue(int n) {//先判断队列满没满，满了就加不了数据if (isFull()) {//抛出异常throw new RuntimeException("队满，无法加数据");}QueueArr[rear] = n;//这个队尾位置就直接放这个数据//然后需要将rear后移，因为环形队列，需要取模rear = (rear + 1) % maxSize;}//从队列中取数据，出队列public int getQueue() {if (isEmpty()) {//抛出异常throw new RuntimeException("队空，无法取数据");}//分析front是指向队列的第一个元素//先将front对应的值保留到一个临时变量。如果不保存起来，front就没有后移的机会了//再将front后移//再将临时保存的变量返回int res = QueueArr[front];front = (front + 1) % maxSize;//而不是直接front++，不然front会直接越界return res;//返回原队头这个数据}//显示队列所有数据public void showQueue() {if (isEmpty()) {System.out.println("队列为空，没有数据");return;}//遍历时就不能用i < QueueArr.length，因为可能前面的数据都被取了，这样显示出数组数据就没有意义了//从front开始遍历，要遍历多少个元素？结合思路中的获取队列中有效的数据的个数（rear+maxSize-front）%maxSize//下面再用一个方法求出有效元素的个数for (int i = front; i < front + size(); i++) {//因为是环形的，所以这里下标也要取模System.out.printf("QueueArr[%d]=%d\n", i % maxSize, QueueArr[i % maxSize]);}}//显示队列有效元素的个数public int size() {return (rear + maxSize - front) % maxSize;}//显示队列的队头数据public int headQueue() {//判断是否为空if (isEmpty()) {throw new RuntimeException("队列为空，没有数据");}//从队列头前一位指向队列头return QueueArr[front];}
}