4-数据结构数组实现环形队列思路和java代码实现

尚硅谷韩顺平Java数据结构与算法

数组模拟环形队列

---

思路分析

• front变量的含义调整：front指向队列的第一个元素，queue[front]就是队列的第一个元素，front的初始值=0；
• rear变量的含义调整：rear指向队列的最后一个元素的后一个位置，空出一个约定空间，rear初始值=0；
• 当队列满时，条件(rear+1) % maxSize == front;
• 当队列为空时，条件 rear == front；
• 获取队列中有效的数据个数 (rear+maxSize-front)%maxSize

图解

• 入队列图解
  

起始位置：rear=0,front=0;

添加元素：queue[rear] = value; rear++;

注意：由于使用数组实现，对于rear++操作是会引发数组越界异常的；这一操作需要取模算法完成rear = (rear+1)%maxSize;

如图3：queue[rear] = 3; rear = (2+1)%4=3

• 出队列图解
  

左图：队列已满

出队操作：int value = queue[front];front++;

注意：由于使用数组实现，对于front++操作是会引发数组越界异常的；这一操作需要取模算法完成front=(front+1)%maxSize

• 环形添加
  

代码实现

public class CircleArrayQueue implements InfQueer {
    private int maxSize; //记录队列的最大容量
    private int front;   //记录队列的头位置
    private int rear;    //记录队列的尾位置
    private int[] queue; //实现队列的数组

    public CircleArrayQueue(int maxSize){
        this.maxSize = maxSize;
        queue = new int[maxSize];
        //规定front,rear 起始位置
        front = 0;
        rear = 0;
    }

    //判断队列是否已满
    public boolean isFull(){
        return (rear+1)%maxSize == front;
    }

    //判断队列是否为空
    public boolean isEmpty(){
        return rear == front;
    }

    //获取有效数据个数
    public int size(){
        return (rear+maxSize-front)%maxSize;
    }
    //给队列添加数据
    public void addQueue(int value){
        //1-判断队列是否满
        if (isFull()){
            System.out.println("队列已满，不能添加元素。。。");
            return;
        }
        //2-添加元素
        queue[rear] = value;
        rear = (rear+1)%maxSize;
    }

    //从队列取出元素
    public int getQueue(){
        //1-判断队列是否空
        if (isEmpty()){
            throw new RuntimeException("队列空，不能取元素。。。");
        }
        //2-取元素
        int value = queue[front];
        front = (front+1)%maxSize;
        return value;
    }

    //显示队列的所有元素
    public void showQueue(){
        if (isEmpty()){
            throw new RuntimeException("队列空。。。");
        }
        for (int i = front; i < front + size(); i++) {
            System.out.printf("queue[%d]=%d\n",i%maxSize,queue[i%maxSize]);
        }
    }
}