Java循环队列实现：少用一个存储单元区分判空和判满

循环队列是一种高效的数据结构，适用于需要频繁进行入队和出队操作的场景。本文将介绍如何使用Java实现一个循环队列，并采用少用一个存储单元的方式来巧妙地判断队列的空和满状态。

1. 循环队列类设计javapublic class CircularQueue { private int capacity; // 队列容量 private int[] queue; // 存储元素的数组 private int front; // 队头指针 private int rear; // 队尾指针

public CircularQueue(int capacity) {        this.capacity = capacity;        this.queue = new int[capacity];        this.front = -1;         this.rear = -1;     }

// ... 其他方法定义 ...}

capacity：表示循环队列的最大容量。- queue：用于存储队列元素的数组。- front：指向队头元素的索引，初始值为-1，表示队列为空。- rear：指向队尾元素的下一个可插入位置的索引，初始值为-1，表示队列为空。

2. 判空、判满和队列大小

采用少用一个存储单元的方式，判空和判满的条件如下：

isEmpty()：当front == rear时，队列为空。- isFull()：当(rear + 1) % capacity == front时，队列已满。java public boolean isEmpty() { return front == rear; }

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

public int size() { if (isEmpty()) { return 0; } else if (rear >= front) { return rear - front + 1; } else { return capacity - (front - rear - 1); } }

3. 入队操作java public void enqueue(int item) { if (isFull()) { resize(); // 队列已满，进行扩容 }

    if (isEmpty()) {            front = 0;             rear = 0;         } else {            rear = (rear + 1) % capacity;         }        queue[rear] = item;    }

首先检查队列是否已满，如果已满则调用resize()方法进行扩容。- 如果队列为空，则将front和rear都设置为0，表示第一个元素将被插入到数组的第一个位置。- 否则，将rear指针向后移动一位，并对capacity取模，确保其始终在数组范围内循环。- 最后将新元素插入到rear指针指向的位置。

4. 出队操作java public int dequeue() { if (isEmpty()) { throw new IllegalStateException('Queue is empty'); }

    int item = queue[front];

    if (front == rear) { // 移除的是最后一个元素            front = -1;            rear = -1;        } else {            front = (front + 1) % capacity;        }

    return item;    }

首先检查队列是否为空，如果为空则抛出异常。- 获取front指针指向的元素，即要出队的元素。- 如果移除的是最后一个元素，则将front和rear都重置为-1，表示队列为空。- 否则，将front指针向后移动一位，并对capacity取模，确保其始终在数组范围内循环。- 最后返回出队的元素。

5. 扩容机制

当队列已满时，需要进行扩容操作以容纳更多元素。扩容操作包括以下步骤：java private void resize() { int newCapacity = capacity * 2; // 容量翻倍 int[] newQueue = new int[newCapacity];

    // 将原队列元素复制到新队列        if (rear >= front) {            System.arraycopy(queue, front, newQueue, 0, size());        } else {            System.arraycopy(queue, front, newQueue, 0, capacity - front);            System.arraycopy(queue, 0, newQueue, capacity - front, rear + 1);        }

    this.capacity = newCapacity;        this.queue = newQueue;        this.front = 0;        this.rear = size() - 1;     }

创建一个容量为原队列两倍的新数组newQueue。- 将原队列的元素复制到新队列中，需要注意处理rear指针小于front指针的情况，需要分两段复制。- 更新队列的容量、数组和队头、队尾指针。

6. 完整代码示例javapublic class CircularQueue { // ... (上述代码) ...

public static void main(String[] args) {        CircularQueue queue = new CircularQueue(5);         System.out.println('Is queue empty? ' + queue.isEmpty()); 

    queue.enqueue(10);        queue.enqueue(20);        queue.enqueue(30);        queue.enqueue(40);        queue.enqueue(50); 

    System.out.println('Is queue full? ' + queue.isFull());         System.out.println('Queue size: ' + queue.size());

    System.out.println('Dequeued item: ' + queue.dequeue());        System.out.println('Dequeued item: ' + queue.dequeue());

    queue.enqueue(60);         queue.enqueue(70); 

    System.out.println('Is queue full? ' + queue.isFull());        System.out.println('Queue size: ' + queue.size());    }}

7. 总结

本文介绍了如何使用Java实现一个循环队列，并采用少用一个存储单元的方式来高效地判断队列的空和满状态。循环队列是一种非常常用的数据结构，掌握其原理和实现方法对于提升编程技能非常有帮助。