Java数据结构与算法：数组模拟队列、环形队列、思路分析

队列

队列可以用数组和链表来实现。遵循FIFO (先进先出)

1、数组模拟队列

该数组模拟队列不是环形的，该列子用于理解队列的工作过程。

思路分析

数组模拟队列示意图

rear表示尾部(指向尾元素)，front表示头部(头元素的前一个位置)。

从图中可看出，当数组队列中没有任何元素时，rear和front都是指向-1的位置；当有元素加入到队列中，rear就依次增加指向，front没有动；当有元素移除队列时，rear不会动，front依次增加指向。

数组模拟队列

• addQueue(添加元素)操作：

rear = front = -1

先判断 rear==front 是否相等，如果相等，说明队列中没有任何元素。

向队列中添加一个元素rear+1 ，若rear小于队列的最大下表MaxSize-1，则可以添加元素，将元素添加到rear指向的位置。

如果rear == (MaxSize-1)说明队列已满。

代码实现

代码

public class ArrayQueueDisposable {

    public static void main(String[] args) {
        ArrayQueueDis arrayQueueDis = new ArrayQueueDis(3);
        System.out.println("队列是否为空："+arrayQueueDis.isEmpty());
        System.out.println();

        System.out.println("添加元素...");
        arrayQueueDis.addQueue(3);
        arrayQueueDis.addQueue(4);
        System.out.println("队列是否已满："+arrayQueueDis.isFull());
        System.out.println("此时头元素："+arrayQueueDis.getHead());
        arrayQueueDis.addQueue(5);
        System.out.println("队列是否已满："+arrayQueueDis.isFull());
        System.out.println("队列遍历：");
        arrayQueueDis.showQueue();

        System.out.println();
        System.out.println("取出第一个元素:");
        System.out.println(arrayQueueDis.getQueue());
        System.out.println("队列遍历：");
        arrayQueueDis.showQueue();

        System.out.println();
        System.out.println("取出第二个元素:");
        System.out.println(arrayQueueDis.getQueue());
        System.out.println("此时头元素："+arrayQueueDis.getHead());
        System.out.println("队列遍历：");
        arrayQueueDis.showQueue();

        System.out.println();
        System.out.println("取出第三个元素:");
        System.out.println(arrayQueueDis.getQueue());
        System.out.println("队列是否为空："+arrayQueueDis.isEmpty());
        System.out.println("队列遍历：");
        arrayQueueDis.showQueue();
    }
}

class ArrayQueueDis{
    private int maxSize; // 数组最大长度
    private int front; // 指向头部元素的前一个位置
    private int rear; // 指向尾部元素的位置
    private int arr[]; // 数组

    public ArrayQueueDis(int maxSize) {
        this.maxSize = maxSize;
        this.rear = -1;
        this.front = -1;
        this.arr = new int[maxSize];
    }

    // 判断是否已满
    public boolean isFull(){
        return rear == maxSize-1;
    }

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

    // 向数组队列加入元素
    public boolean addQueue(int num){
        if(isFull()){
            System.out.println("数组已满！");
            return false;
        }
        rear++;
        arr[rear] = num;
        return true;
    }

    // 从数组队列获取元素
    public int getQueue(){
        if(isEmpty()){
            throw new RuntimeException("数组为空！");
        }
        front++;
        int num = arr[front];
        arr[front] = 0;
        return num;
    }

    // 从数组队列中获取头元素
    public int getHead(){
        if(isEmpty()){
            throw new RuntimeException("数组为空！");
        }
        return arr[front+1];
    }

    // 展示数组队列中的所有元素
    public void showQueue(){
        for (int i = 0; i < arr.length; i++) {
            System.out.println("arr["+i+"] "+arr[i]+"\t");
        }
    }
}

结果

队列是否为空：true

添加元素...
队列是否已满：false
此时头元素：3
队列是否已满：true
队列遍历：
arr[0] 3	
arr[1] 4	
arr[2] 5	

取出第一个元素:
3
队列遍历：
arr[0] 0	
arr[1] 4	
arr[2] 5	

取出第二个元素:
4
此时头元素：5
队列遍历：
arr[0] 0	
arr[1] 0	
arr[2] 5	

取出第三个元素:
5
队列是否为空：true
队列遍历：
arr[0] 0	
arr[1] 0	
arr[2] 0

存在的问题

从上面代码运行来看，理解到了数组队列的原理以及基本实现。存在的问题是不能重复使用数组，比如索引为1的位置使用，并把元素删除之后，这个位置就不能再次被使用了，只能使用一次，因此就引出了环形队列，可以使得数组的空间利用率增高。

2、数组模拟环形队列

由于需要改进第一个队列的缺点，进行优化，因此有了以下优化调整：

思路分析

由于是环形队列，rear到达size-1的位置时，下一次会回到索引为0的位置继续开始循环

• 设定front指向头部元素，front初始值为0
• 设定rear指向最后一个元素的下一个位置(下一个位置永远是保留的)，希望永远留出一个位置作为一个约定，因此MaxSize的数组，最多只能存入MaxSize-1个元素，rear初始值为0
• 当front == rear时数组中没有元素，为空数组
• rear 指向下一个位置 (rear+1) % MaxSize
• 当rear指向下一个位置与front相等时及(rear+1) % MaxSize == front 数组中已存满元素
• 当(rear + MaxSize - front) % MaxSize 得到有效元素个数

当然，数组模拟的环形队列有很多种思路和写法，我提供的只是其中的一种。

代码实现

代码

public class ArrayQueueCircle {
    public static void main(String[] args) {
        ArrayQueueCir arrayQueueCir = new ArrayQueueCir(3);
        System.out.println("队列是否为空："+arrayQueueCir.isEmpty());
        System.out.println();

        System.out.println("添加元素...");
        arrayQueueCir.addQueue(3);
        arrayQueueCir.addQueue(4);
        System.out.println("队列是否已满："+arrayQueueCir.isFull());
        System.out.println("此时头元素："+arrayQueueCir.getHead());
        arrayQueueCir.addQueue(5);
        System.out.println("队列是否已满："+arrayQueueCir.isFull());
        System.out.println("队列遍历：");
        arrayQueueCir.showQueue();

        System.out.println();
        System.out.println("取出第一个元素:");
        System.out.println(arrayQueueCir.getQueue());
        System.out.println("队列遍历：");
        arrayQueueCir.showQueue();

        System.out.println();
        System.out.println("再添加一个新元素...");
        arrayQueueCir.addQueue(5);
        System.out.println("队列遍历：");
        arrayQueueCir.showQueue();

        System.out.println();
        System.out.println("取出第二个元素:");
        System.out.println(arrayQueueCir.getQueue());
        System.out.println("队列是否为空："+arrayQueueCir.isEmpty());
        System.out.println("队列遍历：");
        arrayQueueCir.showQueue();

        System.out.println();
        System.out.println("再添加一个新元素...");
        arrayQueueCir.addQueue(6);
        System.out.println("队列遍历：");
        arrayQueueCir.showQueue();
    }
}

class ArrayQueueCir{
    private int maxSize; // 数组最大长度
    private int front; // 指向头部元素的前一个位置，初始值0
    private int rear; // 指向尾部元素的位置，初始值0
    private int arr[]; // 数组

    public ArrayQueueCir(int arrSize) {
        this.maxSize = arrSize;
        this.arr = new int[arrSize];
    }

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

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

    // 向数组队列加入元素
    public boolean addQueue(int num){
        if(isFull()){
            System.out.println("数组已满，不能再添加元素！");
            return false;
        }
        arr[rear] = num;
        rear = (rear+1)%maxSize;
        return true;
    }

    // 从数组队列获取元素，并删除该元素
    public int getQueue(){
        if(isEmpty()){
            throw new RuntimeException("数组为空！");
        }
        int num = arr[front];
        front = (front+1)%maxSize;
        return num;
    }

    // 从数组队列中获取头元素
    public int getHead(){
        if(isEmpty()){
            throw new RuntimeException("数组为空！");
        }
        return arr[front];
    }

    // 展示数组队列中的所有元素
    public void showQueue(){
        if(!isEmpty()){
            int size = size();
            for (int i = front; i < front+size; i++) {
                System.out.println(arr[(i)%maxSize]+" ");
            }
        }else {
            System.out.println("队列中无元素");
        }
    }

    public int size(){
        return (rear - front + maxSize)%maxSize;
    }
}

结果

队列是否为空：true

添加元素...
队列是否已满：true
此时头元素：3
数组已满，不能再添加元素！
队列是否已满：true
队列遍历：
3 
4 

取出第一个元素:
3
队列遍历：
4 

再添加一个新元素...
队列遍历：
4 
5 

取出第二个元素:
4
队列是否为空：false
队列遍历：
5 

再添加一个新元素...
队列遍历：
5 
6