如何衡量一个网站的价值,局域网如何做视频网站建设,wordpress接erp,网站建设的目的意义队列#xff08;Queue#xff09;是一种重要的线性数据结构#xff0c;遵循先进先出、后进后出的原则。本文将更详细地介绍队列的概念、特点、Java 实现以及应用场景。
模运算小复习#xff1a;
a % b 的值总是小于b
5 % 4 1 5 % 2 1
1 % 5 1 4 % 5 4
1. 队列…
队列Queue是一种重要的线性数据结构遵循先进先出、后进后出的原则。本文将更详细地介绍队列的概念、特点、Java 实现以及应用场景。
模运算小复习
a % b 的值总是小于b
5 % 4 1 5 % 2 1
1 % 5 1 4 % 5 4
1. 队列概念概述
想象一下排队买票先排队的人总是先买到票。队列就像这样元素从一端进入称为队尾Rear或尾指针tail从另一端取出称为队首Front或头指针head。元素的添加操作称为入队Enqueue或加入队列删除操作称为出队Dequeue或移出队列。 队列是一种抽象数据类型 (ADT)这意味着我们只关心它的操作和特性而不关心具体的实现方式。队列的关键操作包括 enqueue(item): 将元素 item 添加到队尾。 dequeue(): 移除并返回队首元素。 peek(): 返回队首元素但不移除它。 isEmpty(): 检查队列是否为空。 size(): 返回队列中元素的数量 (部分实现可能不包含此方法需要额外维护一个计数变量)。
2. 队列的特点 先进先出 (FIFO): 这是队列最核心的特点最先入队的元素总是最先出队。 操作受限: 只能在队尾入队在队首出队。这限制了访问元素的灵活性但也保证了操作的高效性 (时间复杂度通常为 O(1))。
3. 队列的 Java 实现
Java 中可以使用链表或环形数组实现队列。
3.1 基于链表的实现 public class LinkedListQueueT {private NodeT head; // 指向队首节点的指针private NodeT tail; // 指向队尾节点的指针private int size; // 记录队列大小private static class NodeT { // 链表节点的内部类T data;NodeT next;Node(T data) {this.data data;}}public LinkedListQueue() {this.head null;this.tail null;this.size 0;}public boolean isEmpty() {return size 0; // 或 head null}public int size() {return size;}//入队public void enqueue(T item) {NodeT newNode new Node(item);if (isEmpty()) {head newNode; // 如果队列为空新节点既是队首也是队尾} else {tail.next newNode; // 否则将新节点添加到队尾}tail newNode; // 更新队尾指针size;}//出队public T dequeue() {if (isEmpty()) {throw new NoSuchElementException(Queue is empty); // 使用更具体的异常类型}T data head.data;head head.next; // 更新队首指针if (head null) { // 如果队列只有一个元素出队后队列变空tail 也需要置空tail null;}size--;return data;}//返回队首元素public T peek() {if (isEmpty()) {throw new NoSuchElementException(Queue is empty);}return head.data;}
} 3.2 基于环形数组的实现 好处 对比普通数组起点和终点更为自由不用考虑数据移动 “环”意味着不会存在【越界】问题 数组性能更佳 环形数组比较适合实现有界队列、RingBuffer 等
public class ArrayQueueT {private T[] data;private int head; // 队首指针private int tail; // 队尾指针private int capacity; // 数组容量private int size; // 队列大小public ArrayQueue(int capacity) {this.capacity capacity;this.data (T[]) new Object[capacity];this.head 0;this.tail 0;this.size 0;}public boolean isEmpty() {return size 0; // 或 head tail}public boolean isFull() {return size capacity; // 使用 size 判断是否满}public int size() { return size; }//入队public void enqueue(T item) {if (isFull()) {//throw new RuntimeException(Queue is full);resizeArray(); // 扩容操作}data[tail] item;tail (tail 1) % capacity; // 环形数组的关键使用模运算size;}//出队public T dequeue() {if (isEmpty()) {throw new NoSuchElementException(Queue is empty);}T item data[head];data[head] null; // 避免对象游离head (head 1) % capacity; // 环形数组的关键使用模运算size--;return item;}//返回队首元素public T peek() {if (isEmpty()) {throw new NoSuchElementException(Queue is empty);}return data[head];}private void resizeArray() { // 扩容方法示例int newCapacity capacity * 2;T[] newData (T[]) new Object[newCapacity];for (int i 0; i size; i) {newData[i] data[(head i) % capacity];}data newData;head 0;tail size;capacity newCapacity;}
} 4. 队列的基本操作图解
4.1 下标计算
例如数组长度是 5当前位置是 3 向前走 2 步此时下标为 (3 2) % 5 0 cur 当前指针位置 step 前进步数 length 数组长度
4.2 判空
引入size属性后有两种方式
return tail size; //队列大小return size 0; 4.3 判满
引入size属性后有两种方式
return size capacity; //数组容量return (tail 1) % length head; 4.4 入队
假设入队前队空此时head tail 入队后head 不变tail 1代码中这样书写 tail (tail 1) % length保证了不会越界的情况不能设置为 tail 。此时a即是队头也是队尾。 4.5 出队
这里要牢记队列的特点先进先出、后进后出
假设此时a、b已入队现在a要出队出队前a是队头b是队尾 a出队后此时b成为新队头 4.6 返回队头元素
略具体实现首先确保不是空队列然后返回 data[head] 5. 各个操作的时间复杂度 入队 (enqueue): 数组实现: 均摊 O(1) (因为需要考虑扩容的情况但大多数情况下是 O(1)), 链表实现: O(1) 出队 (dequeue): O(1) 查看队首元素 (peek): O(1)
6. 队列的局限性 数组实现的假溢出: 使用环形数组实现时虽然解决了普通数组的一次性问题但仍然存在容量限制。需要仔细处理扩容操作。 固定大小在某些实现中队列的大小是固定的这意味着一旦队列满了就不能再添加新的元素除非移除一些元素。这可能导致数据丢失或需要额外的逻辑来处理溢出。 性能问题在基于数组的队列实现中如果队列经常达到其最大容量那么在队列的末尾添加元素可能需要数组的复制这会带来额外的时间成本。虽然这个操作是偶尔发生的但在高负载情况下可能会影响性能。 不适合随机访问队列不支持随机访问这意味着你不能直接访问队列中间的元素。如果你需要随机访问可能需要使用其他数据结构如数组或链表。 不适合实时系统在实时系统中队列可能不是最佳选择因为队列的操作入队和出队可能需要等待特别是在有大量并发操作时。 空间效率在基于数组的实现中即使队列中没有很多元素数组也可能被预分配了较大的空间这可能导致空间的浪费。 操作的局限性队列只允许在队尾添加元素在队头移除元素。如果需要在队列中间进行操作队列可能不是最合适的选择。 并发问题在多线程环境中队列的操作需要同步以避免竞态条件和数据不一致的问题。这可能需要额外的锁机制从而影响性能。 不适合处理大量数据如果需要处理大量数据队列可能不是最佳选择因为队列的操作可能会因为数据量大而变得缓慢。 不适合需要频繁插入和删除的场景如果应用场景中需要频繁地在队列的中间进行插入和删除操作队列可能不是最佳选择因为这些操作在队列中是不允许的。 不适合需要多种访问模式的场景如果应用需要多种不同的数据访问模式如堆栈的后进先出LIFO特性队列可能不足以满足需求。
7. 总结和应用场景
队列是一种简单但强大的数据结构其 FIFO 特性使其在许多场景下都非常有用例如 任务调度: 操作系统中的任务调度通常使用队列来管理待执行的任务保证先提交的任务先执行。例如打印队列按照先来先服务的顺序打印文档。 宽度优先搜索 (BFS): 图算法中常用的宽度优先搜索算法使用队列来存储待访问的节点 ensuring that nodes closer to the starting node are visited first. 缓冲区: 在生产者-消费者模型中队列可以作为缓冲区平衡生产者和消费者的速度差异。生产者将数据放入队列消费者从队列中取出数据。队列可以缓解生产和消费速度不匹配的问题避免数据丢失或程序阻塞. 例如网络请求中的缓冲区。 消息队列: 在分布式系统中消息队列用于异步通信。发送方将消息放入队列接收方从队列中取出消息。消息队列可以解耦发送方和接收方提高系统的可靠性和可扩展性。 例如Kafka, RabbitMQ.
理解队列的概念和实现对于程序员来说至关重要它能帮助我们更好地设计和优化程序。
希望本文能帮助各位看官更好地理解队列这种重要的数据结构下期见谢谢~
