数据结构入门教程-环形队列

上节我们对队列有了简单的了解，并利用数组的特性通过代码实现了，但在测试中我们发现，队列中的数据是无法复用，这也是我们上节遗留的问题，那么本片文章我就是为了解决该问题的，直接入正题。

数组模拟环形队列

我们主要是对前面的数组缺陷进行优化，我们完全可以将一个数组看成一个环形的，通过取模的方式来实现，接下来我们通过图解方式来分析我们的思路，如图：

环形分析队列图.png

• 思路如下：

1. 首先我们对头部指针front进行调整：由之前的指向头部元素的前一个位置改为就指向队列的第一个元素，即array[front],且初始值为front为0.
2. 同样我们对尾部指针rear进行一个调整：由之前的指向尾部元素的位置改为指向当前队列最后一个元素的后一个位置，这里有一个小铺垫，我们空出一个空间位置作为预备位置(也就是我们自己的一个约束而已，方便理解)，同样rear的初始值为0.
3. 那么我们就需要考虑队列满时的条件：
   3.1. 我们上节的分析中，只要rear= maxSize -1时，就认为队列是满的，因为我们并没有考虑到队列的复用性，为了复用性我们利用取模的方式来设计队列,而且我们对队列的front和rear作了调整，那么我们队列满时的条件应该为：(rear +1) %maxSize = front时，就认为它已经满，举例来说，当前的maxSize=3,(最大容量)，rear=1,front=0,那么取模为0，即两者是相等的，这里涉及到了经验和算法的东西，(呜呜呜~~~~)，大家感兴趣的可以自己画图理解理解
4. 队列为null的条件还是不变，当front=rear时即可满足

分析完了，我们来改造我们上节的代码

代码实现

• 首先我们需要申明一个队列，这其中包括队列自身的属性，代码如下：

 class CircleQueue{
private int maxSize; //表示数组的最大容量
/**front做了一个简单地调整：front就指向队列的第一个元素，也就是array[front] 其初始值为：0*/
private int front;  //队列的头指针
/**rear做了一个简单地调整：rear就指向队列最后一个元素的后一个位置,希望空出一个位置，其初始值为0*/
private int rear; //队列尾指针
private int[] array; //存放数据的数组（真正模拟的队列的数组）

public CircleQueue(int arrMaxSize){
    maxSize = arrMaxSize;
    front = 0;
    rear = 0;
    array = new int[maxSize];
}

上述代码是对队列的申明和初始化的过程，代码很简单，接着看

• 如果当前队列已满，是不能存数据的，因此需要我们来编写该方法，代码如下：

//2.判断队列是否已满
public boolean isFull(){

    return  (rear +1) %maxSize == front;
}

至于原因，我们前面分析了，只有通过取模的方式我们才可能是一个环形队列，接着看：

• 队列为null的判断方法，代码如下

//3.判断队列是否为null
public boolean isEmpty(){

    return rear == front;
}

• 添加操作，代码如下：

//4.添加数据到队列中
public void addQueue(int data){
    //判断队列是否已满
    if (isFull()){
        System.out.println("队列已满，无法添加...");
        return;
    }
    //直接加，因为rear表示的是当前元素的后一个位置
    array[rear] = data;
    //将rear后移，考虑到取模
    rear = (rear +1) %maxSize; //可能当前位置已经到了最后一个，但是前面有空间存储
}

• 获取队列中的数据，代码如下：

 //5.出队列
public int getQueue(){
    //判断队列是否为null
    if (isEmpty()){
        throw new RuntimeException("队列为null,emmmmm");
    }
   //1.需要先分析出front是指向队列的第一个元素
   //1.1.先把front对应的值保存到一个临时的变量中
  //1.2.将front往后移，考虑取模
  //1.3.将临时保存的变量返回
  int value = array[front]; //因为front表示的就是当前位置的元素
  front = (front + 1)%maxSize;
  return value;
}

• 获取当前队列的有效个数，代码如下：

//6.求出当前队列有效数据的个数
public int size(){
    //如：
    // rear=1 maxSize=3; front=0
    //那么只有一个值
    return (rear+maxSize -front) %maxSize;
}

代码注释很详细，接着看：

• 显示队列的所有数据

public void printQueue(){
    //判断
    if (isEmpty()){
        System.out.println("队列为null");
        return;
    }
    //从front开始遍历，遍历多少个元素
    //i%maxSize:遍历到的当前元素的下标
    //array[i%maxSize]:当前下标元素所对应的值
    for (int i =front; i<front +size();i++){
        System.out.printf("array[%d]=%d\n",i%maxSize, array[i%maxSize]);
    }
}

• 在来看一个显示头部的数据

//8.显示队列的头数据
public int peek(){
    if (isEmpty()){
        throw new RuntimeException("队列为null");
    }
    return array[front];
}

测试的过程就不写了，还是上节那个过程，这就是数组取模实现环形队列的过程，千看万看，不如手动敲一遍这样理解的更深，文章仅供自己学习总结笔记...