【数据结构与算法】用数组模拟实现环形队列

在之前的实践中，已经使用数组实现了队列，但是其有缺陷，就是数组只能使用一次，由此提出改进，用数组模拟实现环形队列

队列

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

队列遵循先入先出的原则

队列的输出输入分别从前后端处理，因此需要俩个变量front和rear分别记录队列前后端的下标，front会随着数据输出而改变，而rear则是随着数据输入而改变

环形队列

1.front指向队列的第一个元素，arr[front]是队列的第一个元素，front的初始值为0

2.rear指向队列最后一个元素的后一个位置，因为希望空出一个空间做约定，rear的初始值为0

3.队列满，(rear+1)%maxSize=front

4.队列空，rear==front

5.队列中有效的数据个数，(rear+maxSize-front)%maxSize

基于数组实现环形队列

class CircleArray{
    private int maxSize;
    private int front;
    private int rear;
    private int[] arr;
    public CircleArray(int arrMaxSize){
        maxSize=arrMaxSize;
        front=0;
        rear=0;
        arr=new int[maxSize];
    }
    //判断队列为满
    public boolean isFull(){
        return (rear+1) % maxSize==front;
    }
    //判断队列为空
    public boolean isEmpty(){
        return front==rear;
    }
    //求队列的有效个数
    public int size(){
        return (rear+maxSize-front)%maxSize;
    }
    //入队
    public void enqueue(int data){
        if(isFull()){
          throw new RuntimeException("队列满，不能入队");
        }
        arr[rear]=data;
        rear=(rear+1)%maxSize;
    }
    //出队
    public int dequeue(){
        if (isEmpty()){
            throw new RuntimeException("队列空，不能出队");
        }
        int getData=arr[front];
        front=(front+1)%maxSize;
        return getData;
    }
    //显示队列
    public void showQueue(){
        if (isEmpty()){
            throw new RuntimeException("队列空");
        }
        for (int i = front; i < front+size(); i++) {
            System.out.printf("arr[%d]=%d\n",i%maxSize,arr[i%maxSize]);
        }
    }

    //显示头数据
    public int headQueue(){
        if (isEmpty()){
            throw new RuntimeException("队列空");
        }
        return arr[front];
    }
}
           

测试环形队列

public class Test {
	public static void main(String[] args) {
	   int headQueue; //用于显示头数据
        CircleArray circleArray=new CircleArray(4);
        circleArray.enqueue(3);
        headQueue= circleArray.headQueue();
        circleArray.enqueue(5);
        headQueue= circleArray.headQueue();
        circleArray.enqueue(8);
        headQueue= circleArray.headQueue();
        circleArray.dequeue();
        headQueue= circleArray.headQueue();
        circleArray.dequeue();
        headQueue= circleArray.headQueue();
        circleArray.enqueue(13);
        headQueue= circleArray.headQueue();
        circleArray.enqueue(15);
        headQueue= circleArray.headQueue();
    }  
}
           

队列变化