循环队列的大小在创建时通过capacity参数确定，实际可存储元素为capacity-1，因需预留一个空间区分队空与队满；初始容量应根据应用场景预估最大长度设定，若无法预估可设合理初始值并在满时扩容，建议选择2的幂次以提升效率；处理并发访问时需解决线程安全问题，1. 可使用reentrantlock或synchronized加锁保证enqueue和dequeue操作的原子性；2. 可采用atomicinteger原子更新front和rear指针，避免锁开销但需处理aba问题；3. 可直接使用java并发包中的arrayblockingqueue等线程安全队列替代手动实现；循环队列适用于生产者-消费者模型、消息队列、网络数据包缓存、音视频播放缓冲、操作系统任务调度及日志异步写入等需要fifo特性和高效空间利用的场景。
循环队列的核心在于解决顺序队列的“假溢出”问题，简单来说，就是队列明明还有空闲空间，但由于入队和出队操作导致 rear 和 front 指针“跑到”数组末尾，无法继续入队。循环队列通过将数组“首尾相连”，形成一个环状结构，巧妙地解决了这个问题。
解决方案：
循环队列的关键在于正确计算 rear 和 front 指针。当 rear 或 front 到达数组末尾时，需要“绕回”到数组的起始位置。这可以通过取模运算实现。
立即学习“Java免费学习笔记（深入）”；
public class CircularQueue {
private int[] queue;
private int front;
private int rear;
private int capacity;
public CircularQueue(int capacity) {
this.capacity = capacity;
this.queue = new int[capacity];
this.front = 0;
this.rear = 0; // 初始时，front 和 rear 指向同一个位置
}
public boolean isFull() {
return (rear + 1) % capacity == front;
}
public boolean isEmpty() {
return front == rear;
}
public boolean enqueue(int data) {
if (isFull()) {
System.out.println("Queue is full");
return false;
}
queue[rear] = data;
rear = (rear + 1) % capacity;
return true;
}
public int dequeue() {
if (isEmpty()) {
System.out.println("Queue is empty");
return -1; // 或者抛出异常
}
int data = queue[front];
front = (front + 1) % capacity;
return data;
}
public void display() {
if (isEmpty()) {
System.out.println("Queue is empty");
return;
}
System.out.print("Queue elements: ");
int i = front;
while (i != rear) {
System.out.print(queue[i] + " ");
i = (i + 1) % capacity;
}
System.out.println();
}
public static void main(String[] args) {
CircularQueue q = new CircularQueue(5);
q.enqueue(1);
q.enqueue(2);
q.enqueue(3);
q.enqueue(4);
q.display(); // Output: Queue elements: 1 2 3 4
System.out.println("Dequeued element: " + q.dequeue()); // Output: Dequeued element: 1
q.enqueue(5);
q.display(); // Output: Queue elements: 2 3 4 5
q.enqueue(6); // Output: Queue is full
}
}循环队列的大小如何确定？初始容量设定多少合适？
循环队列的大小需要在创建队列时确定，也就是
CircularQueue(int capacity)构造函数中的
capacity参数。 这个 capacity 实际上代表的是队列底层数组的长度。 但是，需要注意的是，为了区分队列为空和队列满的状态，通常会浪费一个数组空间。 也就是说，实际能存储的元素数量是
capacity - 1。
初始容量的选择需要根据实际应用场景来决定。 如果能预估队列的最大长度，那么直接设置为这个最大长度即可。 如果无法预估，可以设置一个合理的初始值，并在队列满时进行扩容。 扩容操作会涉及创建一个更大的数组，并将原有数据复制过去，这会带来一定的性能开销，因此需要谨慎选择初始容量。 一个常见的做法是，选择一个2的幂作为初始容量，例如8, 16, 32等等，这可以提高某些操作的效率。
如何处理循环队列的并发访问？线程安全问题怎么解决？
循环队列在并发环境下，由于涉及到共享的
front和
rear指针的修改，因此需要考虑线程安全问题。 多个线程同时进行入队或出队操作可能会导致数据不一致，甚至程序崩溃。
常见的线程安全解决方案包括：
-
使用锁（Lock）： 可以使用
ReentrantLock
或synchronized
关键字来保护enqueue
和dequeue
方法。 确保在修改front
和rear
指针之前获取锁，操作完成后释放锁。 这样可以保证同一时刻只有一个线程可以访问队列。
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
public class ConcurrentCircularQueue {
private int[] queue;
private int front;
private int rear;
private int capacity;
private Lock lock = new ReentrantLock();
public ConcurrentCircularQueue(int capacity) {
this.capacity = capacity;
this.queue = new int[capacity];
this.front = 0;
this.rear = 0;
}
public boolean enqueue(int data) {
lock.lock();
try {
if (isFull()) {
System.out.println("Queue is full");
return false;
}
queue[rear] = data;
rear = (rear + 1) % capacity;
return true;
} finally {
lock.unlock();
}
}
public int dequeue() {
lock.lock();
try {
if (isEmpty()) {
System.out.println("Queue is empty");
return -1;
}
int data = queue[front];
front = (front + 1) % capacity;
return data;
} finally {
lock.unlock();
}
}
private boolean isFull() {
return (rear + 1) % capacity == front;
}
private boolean isEmpty() {
return front == rear;
}
}使用原子变量（Atomic Variables）： 可以使用
AtomicInteger
来原子地更新front
和rear
指针。 这种方式可以避免使用锁，提高并发性能，但是实现起来相对复杂。 需要注意的是，使用原子变量需要仔细考虑 ABA 问题。使用并发集合： Java 并发包
java.util.concurrent
中提供了一些线程安全的队列实现，例如ConcurrentLinkedQueue
和ArrayBlockingQueue
。 这些队列已经实现了线程安全，可以直接使用，无需自己编写并发控制代码。ArrayBlockingQueue
可以通过设置容量来模拟循环队列的行为。
选择哪种方案取决于具体的应用场景和性能需求。 如果并发量不高，使用锁可能是一个简单的选择。 如果对性能要求较高，可以考虑使用原子变量或并发集合。
循环队列在实际开发中有什么应用场景？
循环队列在很多场景下都有应用，以下是一些常见的例子：
生产者-消费者模型： 循环队列可以作为生产者和消费者之间的缓冲区。 生产者将数据放入队列，消费者从队列中取出数据。 循环队列可以有效地平衡生产者和消费者的速度差异。
消息队列： 在消息队列系统中，循环队列可以用来存储待处理的消息。 消息的发送者将消息放入队列，消息的接收者从队列中取出消息进行处理。
网络数据包处理： 在网络编程中，循环队列可以用来缓存接收到的网络数据包。 网络数据包的接收速度可能超过处理速度，循环队列可以避免数据包丢失。
音频/视频播放： 在音频/视频播放器中，循环队列可以用来缓存音频/视频帧。 播放器可以从队列中取出帧进行播放，保证播放的流畅性。
操作系统任务调度： 在操作系统中，循环队列可以用来管理就绪的任务。 任务调度器可以按照一定的策略从队列中取出任务进行执行。
日志处理： 在日志系统中，循环队列可以用来缓存待写入磁盘的日志。 可以异步地将日志写入磁盘，提高系统的性能。
总的来说，循环队列适用于任何需要缓存数据，并且具有先进先出（FIFO）特性的场景。它能够有效地利用存储空间，避免假溢出问题，是一种高效的数据结构。
