简洁大气企业网站,爱站网长尾关键词,网站子站点是什么意思,网站后期目录
队列介绍#xff1a;
基本概念#xff1a;
应用#xff1a;
Java实现示例#xff1a;
循环队列的Java实现#xff1a; 队列介绍#xff1a;
队列#xff08;Queue#xff09;是一种常见的数据结构#xff0c;它按照先进先出#xff08;FIFO#xff0c;Fi…目录
队列介绍
基本概念
应用
Java实现示例
循环队列的Java实现 队列介绍
队列Queue是一种常见的数据结构它按照先进先出FIFOFirst-In-First-Out的原则管理数据。在现实生活中队列的概念很容易理解就像是排队等待服务的人群一样。在计算机科学领域队列同样扮演着重要的角色在算法和程序设计中被广泛应用。
基本概念
1. 入队和出队 队列的两个主要操作是入队enqueue和出队dequeue。入队指将元素添加到队列的末尾而出队则是从队列的头部移除一个元素。这两个操作遵循FIFO原则即先入队的元素会先被出队。 2. 队首和队尾 队列中的第一个元素称为队首front而最后一个元素称为队尾rear。入队操作会将元素添加到队尾而出队操作会移除队首元素。
应用 1. 算法中的应用 队列在算法中有着广泛的应用特别是在图的遍历、广度优先搜索BFS、迷宫求解等问题中。它们通常用于管理待处理的节点或状态以确保按照正确的顺序进行处理。 2. 数据结构中的应用 队列可以作为其他数据结构的基础例如实现线程池、任务调度器、缓冲区等。在这些应用中队列用于存储待处理的任务或数据并按照先进先出的顺序进行处理。
Java实现示例
注意此队列使用了动态数组可以自动扩容避免了固定大小数组的限制如果想用静态数组可以在代码的基础上修改一下这里我就不展示了
另外此队列代码实现运用了泛型的相关知识对泛型还不太了解的小伙伴可以看一下我下期作品深入探究Java中的泛型
public class QueueT {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 CircularQueueT {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;}
}
