队列的定义和基本操作
队列是一种特殊的线性数据结构,它只允许在表的前端(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)!