目录
队列介绍:
队列(Queue)是一种常见的数据结构,它按照先进先出(FIFO,First-In-First-Out)的原则管理数据。在现实生活中,队列的概念很容易理解,就像是排队等待服务的人群一样。在计算机科学领域,队列同样扮演着重要的角色,在算法和程序设计中被广泛应用。
基本概念:
1. 入队和出队
队列的两个主要操作是入队(enqueue)和出队(dequeue)。入队指将元素添加到队列的末尾,而出队则是从队列的头部移除一个元素。这两个操作遵循FIFO原则,即先入队的元素会先被出队。
2. 队首和队尾
队列中的第一个元素称为队首(front),而最后一个元素称为队尾(rear)。入队操作会将元素添加到队尾,而出队操作会移除队首元素。
应用:
1. 算法中的应用
队列在算法中有着广泛的应用,特别是在图的遍历、广度优先搜索(BFS)、迷宫求解等问题中。它们通常用于管理待处理的节点或状态,以确保按照正确的顺序进行处理。
2. 数据结构中的应用
队列可以作为其他数据结构的基础,例如实现线程池、任务调度器、缓冲区等。在这些应用中,队列用于存储待处理的任务或数据,并按照先进先出的顺序进行处理。
Java实现示例:
注意:此队列使用了动态数组可以自动扩容,避免了固定大小数组的限制,如果想用静态数组可以在代码的基础上修改一下,这里我就不展示了
另外,此队列代码实现运用了泛型的相关知识,对泛型还不太了解的小伙伴,可以看一下我下期作品:深入探究Java中的泛型
public class Queue<T> {
private T[] elements; // 用于存储队列元素的数组
private int front; // 指向队列头部的指针
private int rear; // 指向队列尾部的指针
private int size; // 队列中元素的数量
private static final int DEFAULT_CAPACITY = 10; // 默认初始容量
private static final int RESIZE_FACTOR = 2; // 扩容因子
// 构造函数,初始化队列
public Queue() {
elements = (T[]) new Object[DEFAULT_CAPACITY];
front = 0;
rear = -1;
size = 0;
}
// 入队操作,将元素添加到队尾
public void enqueue(T element) {
// 检查队列是否需要扩容
if (size == elements.length) {
resize();
}
// 队尾指针移动并添加元素
rear = (rear + 1) % elements.length;
elements[rear] = element;
size++;
}
// 出队操作,从队首移除元素并返回
public T dequeue() {
// 检查队列是否为空
if (isEmpty()) {
throw new IllegalStateException("队列为空");
}
// 获取队首元素并移动队首指针
T element = elements[front];
front = (front + 1) % elements.length;
size--;
return element;
}
// 获取队首元素,但不移除
public T peek() {
// 检查队列是否为空
if (isEmpty()) {
throw new IllegalStateException("队列为空");
}
return elements[front];
}
// 检查队列是否为空
public boolean isEmpty() {
return size == 0;
}
// 获取队列大小
public int size() {
return size;
}
// 扩容队列
private void resize() {
int newCapacity = elements.length * RESIZE_FACTOR;
T[] newElements = (T[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newElements[i] = elements[(front + i) % elements.length];
}
elements = newElements;
front = 0;
rear = size - 1;
}
}
循环队列的Java实现:
循环利用数组空间: 循环队列通过循环利用数组空间,避免了因队列元素出队导致的空间浪费问题。
入队、出队操作高效: 循环队列的入队和出队操作时间复杂度均为 O(1),因为它们只涉及修改队尾指针和队首指针,并不需要移动数组元素。
固定大小: 循环队列通常具有固定的大小,一旦初始化后大小不会改变。
public class CircularQueue<T> {
private T[] elements; // 用于存储队列元素的数组
private int front; // 队列头部指针,指向队首元素
private int rear; // 队列尾部指针,指向队尾元素的下一个位置
private int size; // 队列中元素的数量
private static final int DEFAULT_CAPACITY = 10; // 默认初始容量
// 默认构造函数,创建指定容量的循环队列
public CircularQueue() {
elements = (T[]) new Object[DEFAULT_CAPACITY];
front = 0;
rear = -1;
size = 0;
}
// 带有容量参数的构造函数,创建指定容量的循环队列
public CircularQueue(int capacity) {
elements = (T[]) new Object[capacity];
front = 0;
rear = -1;
size = 0;
}
// 入队操作,将元素添加到队尾
public void enqueue(T element) {
// 检查队列是否已满
if (isFull()) {
throw new IllegalStateException("队列已满");
}
// 计算新的rear位置
rear = (rear + 1) % elements.length;
elements[rear] = element;
size++;
}
// 出队操作,从队首移除元素并返回
public T dequeue() {
// 检查队列是否为空
if (isEmpty()) {
throw new IllegalStateException("队列为空");
}
T element = elements[front];
// 移动front指针
front = (front + 1) % elements.length;
size--;
return element;
}
// 获取队首元素,但不移除
public T peek() {
if (isEmpty()) {
throw new IllegalStateException("队列为空");
}
return elements[front];
}
// 检查队列是否为空
public boolean isEmpty() {
return size == 0;
}
// 检查队列是否已满
public boolean isFull() {
return size == elements.length;
}
// 获取队列大小
public int size() {
return size;
}
}
标签:elements,Java,队列,front,数据结构,public,rear,size
From: https://blog.csdn.net/2202_75569688/article/details/137355845