Java数组队列及环形数组队列超详细讲解

什么是队列

队列（Queue）是一种先进先出（FIFO, first in first out）的数据结构，常见的队列有数组队列和链式队列两种实现方式。

数组队列

数组队列是一种线性结构，底层使用静态数组来存储数据。队列的头部（front）指向队列头部元素，队列尾（rear）指向队列尾部元素。当有新元素入队时，队列尾指针往后移动一位，并将新元素放入队列尾部。当有元素出队时，队列头部指针往后移动一位，并返回头部元素值。当队列头部和队列尾部指针重合时，表示队列为空。当队列尾部指针指向数组最后一个元素时，即使队列中已有空闲位置，也无法再增加元素，这就是数组队列的局限性。

Java实现

public class ArrayQueue {

    private int maxSize;  // 队列的最大容量
    private int[] queue;  // 队列存储数组
    private int front;    // 队列头部指针
    private int rear;     // 队列尾部指针

    public ArrayQueue(int maxSize) {
        this.maxSize = maxSize;
        this.queue = new int[maxSize];
        this.front = -1;  // 指向队列头部前一个位置
        this.rear = -1;   // 指向队列尾部
    }

    public boolean isFull() {
        return rear == maxSize - 1;
    }

    public boolean isEmpty() {
        return front == rear;
    }

    public void add(int num) {
        if (isFull()) {
            throw new RuntimeException("队列已满");
        } else {
            rear++;
            queue[rear] = num;
        }
    }

    public int remove() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空");
        } else {
            front++;
            return queue[front];
        }
    }

    public void print() {
        if (isEmpty()) {
            System.out.println("队列为空");
        } else {
            for (int i = front + 1; i <= rear; i++) {
                System.out.print(queue[i] + "\t");
            }
            System.out.println();
        }
    }
}

示例1

public static void main(String[] args) {
    ArrayQueue queue = new ArrayQueue(5);
    queue.add(1);
    queue.add(2);
    queue.add(3);
    queue.print();   // output: 1  2  3
    queue.remove();
    queue.print();   // output: 2  3
}

环形数组队列

环形数组队列（Circular Queue）是一种将数组当做环来使用的队列，当队列尾部指针指向数组末尾时，指针回到数组头部，并继续从头部插入元素或从头部删除元素。这样的话，队列空间几乎可以无限扩充。

Java实现

public class CircularQueue {

    private int maxSize;  // 环形队列的最大容量
    private int[] queue;  // 环形队列存储数组
    private int front;    // 队列头部指针
    private int rear;     // 队列尾部指针

    public CircularQueue(int maxSize) {
        this.maxSize = maxSize;
        this.queue = new int[maxSize];
        this.front = 0;  // 指向队列头部
        this.rear = 0;   // 指向队列尾部
    }

    public boolean isFull() {
        return (rear + 1) % maxSize == front;
    }

    public boolean isEmpty() {
        return front == rear;
    }

    public void add(int num) {
        if (isFull()) {
            throw new RuntimeException("队列已满");
        }
        queue[rear] = num;
        rear = (rear + 1) % maxSize;
    }

    public int remove() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空");
        }
        int num = queue[front];
        front = (front + 1) % maxSize;
        return num;
    }

    public void print() {
        if (isEmpty()) {
            System.out.println("队列为空");
        } else {
            int size = (rear + maxSize - front) % maxSize;
            for (int i = 0; i < size; i++) {
                int index = (front + i) % maxSize;
                System.out.print(queue[index] + "\t");
            }
            System.out.println();
        }
    }
}

示例2

public static void main(String[] args) {
    CircularQueue queue = new CircularQueue(5);
    queue.add(1);
    queue.add(2);
    queue.add(3);
    queue.print();   // output: 1  2  3
    queue.remove();
    queue.print();   // output: 2  3
    queue.add(4);
    queue.add(5);
    queue.add(6);
    queue.print();   // output: 4  5  6
}

总结

本篇文章介绍了Java数组队列及环形数组队列的实现原理和代码实现，其中数组队列适用于队列容量较小的场景，而环形数组队列适用于队列容量较大或容量无法预估的场景。对于需要频繁进行入队和出队操作的场景，应优先选择链式队列。