队列的定义和基本操作
队列是一种特殊的线性数据结构，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。
队列中没有元素时，称为空队列。
队列的数据元素又称为队列元素。
在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。
因为队列只允许在一端插入，在另一端删除，所以又称为先进先出（FIFO—first in first out）线性表。
基本定义
在Java中，我们可以使用数组或链表来实现队列。这里以数组为例，定义一个简单的队列：
public class Queue {
private int maxSize;
private int front;
private int rear;
private int[] queueArray;
public Queue(int size) {
maxSize = size;
front = 0;
rear = -1;
queueArray = new int[maxSize];
}
public void enqueue(int value) {
if (isFull()) {
System.out.println("队列已满，无法入队");
} else {
rear++;
queueArray[rear] = value;
}
}
public boolean isFull() {
return (rear == maxSize - 1);
}
public int dequeue() {
if (isEmpty()) {
System.out.println("队列为空，无法出队");
return -1; // 或者抛出异常
} else {
int temp = queueArray[front];
front++;
return temp;
}
}
public boolean isEmpty() {
return (front > rear);
}
}基本操作
以Java数组实现的队列会有一个问题，就是在出队之后，队头的index会往后移动，由于数组的容量是一定的，如果一直入队再出队，就会由于容量限制而导致队列无法使用，解决方案是使用循环队列。
循环队列（Circular Queue）是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首以形成一个环。这种设计使得我们可以更有效地利用存储空间，因为当队尾到达数组的末尾时，它可以回到数组的开始位置继续入队操作，而不是受限于数组的固定大小。
下面是一个用Java数组实现循环队列的示例：
java复制代码
public class CircularQueue {
private int[] queue;
private int front; // 队首
private int rear; // 队尾
private int capacity; // 队列容量
private int size; // 队列当前元素个数
public CircularQueue(int k) {
capacity = k + 1; // 队列实际大小比容量多1，用于区分队列为空和队列满的情况
queue = new int[capacity];
front = 0;
rear = 0;
size = 0;
}
// 入队操作
public boolean enqueue(int value) {
if (isFull()) {
return false; // 队列已满，无法入队
}
queue[rear] = value;
rear = (rear + 1) % capacity; // 循环到数组开头
size++;
return true;
}
// 出队操作
public boolean dequeue() {
if (isEmpty()) {
return false; // 队列为空，无法出队
}
front = (front + 1) % capacity; // 循环到数组开头
size--;
return true;
}
// 查看队首元素
public int Front() {
if (isEmpty()) {
throw new NoSuchElementException("队列为空");
}
return queue[front];
}
// 查看队尾元素
public int Rear() {
if (isEmpty()) {
throw new NoSuchElementException("队列为空");
}
// 注意：当队列只有一个元素时，front和rear相等
return queue[(rear == 0) ? capacity - 1 : rear - 1];
}
// 检查队列是否为空
public boolean isEmpty() {
return size == 0;
}
// 检查队列是否已满
public boolean isFull() {
return size == capacity - 1; // 队列满的条件是元素个数等于容量减一
}
// 获取队列当前元素个数
public int getSize() {
return size;
}
}在这个实现中，我们使用了 front 和 rear 两个指针来追踪队列的开始和结束位置。当 rear 到达数组的末尾时，我们通过取模操作 (rear + 1) % capacity 将其循环回数组的开头。同样地，当 front 到达数组的末尾时，也通过取模操作 (front + 1) % capacity 循环回数组的开头。
capacity 变量存储队列的容量（即数组的大小），但实际上我们让 capacity 比所需的队列大小多一个元素。这是为了确保在队列满的情况下，front 和 rear 不会指向同一个位置（这会导致我们无法区分队列是满的还是空的）。通过比较 size 和 capacity - 1，我们可以判断队列是否已满。
请注意，当队列只有一个元素时，front 和 rear 会指向同一个位置。因此，在 Rear() 方法中，我们需要特别处理这种情况，确保返回正确的队尾元素。
使用循环队列可以更有效地管理内存，尤其是在频繁进行入队和出队操作的情况下。
原文地址：https://blog.csdn.net/QiuMingAE86START/article/details/136998439
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！