当前位置：首页 > news >正文

线性数据结构之队列

news 2024/11/2 9:44:05

队列的基本概念

1. 特点

FIFO：先进先出，即第一个加入队列的元素将第一个被移除。
基本操作：
- Enqueue：在队尾插入新元素。
- Dequeue：移除队首元素并返回其值。
- Peek：查看队首元素但不移除它。
- isEmpty：检查队列是否为空。
- Size：返回队列中元素的数量。

2. 应用场景

资源调度：如 CPU 任务调度、操作系统的进程管理。
数据缓冲：如网络数据包缓冲、I/O 缓存。
广度优先搜索：在图或树中实现广度优先搜索（BFS）。

一、普通队列（Queue）

定义与实现原理

普通队列是一种典型的 FIFO 数据结构，可以用数组或链表实现。队列的起始端称为队首（Front），元素从队尾（Rear）插入并从队首移除。

1. 优点

结构简单：操作仅限于队首和队尾，逻辑清晰。
实现简单：基于数组或链表均可方便实现。

2. 缺点

内存浪费：使用数组实现时，元素出队后，前端空间无法复用。
容量固定：基于数组的实现需要预定义大小，可能导致溢出或浪费。

3. 适用场景

任务调度：如打印机作业队列、操作系统进程管理。
数据流缓冲：如网络传输、消息队列。

4. 示例代码（Java）

class Queue {private int[] queue;private int front;private int rear;private int capacity;private int size;public Queue(int capacity) {this.capacity = capacity;queue = new int[capacity];front = 0;rear = -1;size = 0;}// 入队操作public void enqueue(int value) {if (isFull()) {throw new IllegalStateException("队列已满，无法入队");}rear = (rear + 1) % capacity;queue[rear] = value;size++;}// 出队操作public int dequeue() {if (isEmpty()) {throw new IllegalStateException("队列为空，无法出队");}int value = queue[front];front = (front + 1) % capacity;size--;return value;}// 查看队首元素public int peek() {if (isEmpty()) {throw new IllegalStateException("队列为空，无法查看队首");}return queue[front];}public boolean isEmpty() {return size == 0;}public boolean isFull() {return size == capacity;}public int getSize() {return size;}
}

二、循环队列（Circular Queue）

定义与实现原理

循环队列在普通队列的基础上通过“环形”结构解决了内存浪费问题。即当队列尾部到达数组末端时，若数组前端有空位，则队尾可以“循环”至数组的起始位置。这种设计使得队列可以利用已出队元素的空间，提高了内存利用率。

1. 优点

内存利用率高：通过循环结构实现空间复用，避免了数组前端的空位浪费。
操作简单：依然只需维护队首和队尾的指针。

2. 缺点

容量固定：依然需要预设大小，不支持动态扩展。

3. 适用场景

缓存区：如多媒体数据流缓冲、循环缓冲区。
调度系统：如 CPU 任务轮询调度。

4. 示例代码（Java）

class CircularQueue {private int[] queue;private int front;private int rear;private int capacity;private int size;public CircularQueue(int capacity) {this.capacity = capacity;queue = new int[capacity];front = 0;rear = -1;size = 0;}// 入队操作public void enqueue(int value) {if (isFull()) {throw new IllegalStateException("队列已满，无法入队");}rear = (rear + 1) % capacity;queue[rear] = value;size++;}// 出队操作public int dequeue() {if (isEmpty()) {throw new IllegalStateException("队列为空，无法出队");}int value = queue[front];front = (front + 1) % capacity;size--;return value;}public boolean isEmpty() {return size == 0;}public boolean isFull() {return size == capacity;}
}

三、双端队列（Deque）

定义与实现原理

双端队列（Deque）是一种扩展的队列，支持从两端进行插入和删除。Deque 分为 输入受限双端队列（仅允许从一端插入元素）和 输出受限双端队列（仅允许从一端删除元素）。

1. 优点

灵活性高：可在队列两端操作，既支持先进先出也支持后进先出。
多功能性：适合实现复杂的队列结构，如双向遍历或优先级调度。

2. 缺点

实现复杂：操作两端的逻辑较复杂，且链表实现时内存消耗较大。

3. 适用场景

浏览器前进后退功能：实现历史记录的快速访问。
滑动窗口算法：在数据流中实时计算窗口内的最小值或最大值。

4. 示例代码（Java）

import java.util.LinkedList;class Deque {private LinkedList<Integer> deque;public Deque() {deque = new LinkedList<>();}// 队首入队public void addFront(int value) {deque.addFirst(value);}// 队尾入队public void addRear(int value) {deque.addLast(value);}// 队首出队public int removeFront() {if (deque.isEmpty()) {throw new IllegalStateException("队列为空，无法出队");}return deque.removeFirst();}// 队尾出队public int removeRear() {if (deque.isEmpty()) {throw new IllegalStateException("队列为空，无法出队");}return deque.removeLast();}// 查看队首元素public int peekFront() {if (deque.isEmpty()) {throw new IllegalStateException("队列为空");}return deque.getFirst();}// 查看队尾元素public int peekRear() {if (deque.isEmpty()) {throw new IllegalStateException("队列为空");}return deque.getLast();}
}

四、优先队列（Priority Queue）

定义与实现原理

优先队列是一种特殊的队列，元素按优先级排列。出队时优先级最高的元素先出队。可以通过堆（如二叉堆）或 排序链表 实现优先队列。

1. 优点

灵活性强：根据优先级决定元素出队顺序，而不是固定的 FIFO。
适合处理多任务调度：优先级越高的任务越先得到处理。

2. 缺点

实现复杂：需要排序或堆操作，插入和删除操作相对复杂。
性能依赖于实现：不同实现方法对性能的影响较大，使用堆可达到 O(log n) 的插入和删除效率。

3. 适用场景

任务调度：CPU 任务调度、网络数据包优先级管理。
最短路径算法：如 Dijkstra 算法中优先处理距离最短的节点。

4. 示例代码（Java）

Java 中的 PriorityQueue 类实现了优先队列，以下示例展示了使用 Java 内置优先队列。

import java.util.PriorityQueue;public class PriorityQueueExample {public static void main(String[] args) {// 创建优先队列，默认情况下，优先级越小的元素越先出队PriorityQueue<Integer> pq = new PriorityQueue<>();pq.add(30);pq.add(10);pq.add(20);// 出队，按优先级顺序出队while (!pq.isEmpty()) {System.out.println(pq.poll()); // 输出 10 20 30}}
}

总结对比

类型	特点	优点	缺点	适用场景
普通队列	先进先出（FIFO）	结构简单，操作高效	内存浪费（数组实现）	任务调度、数据流缓冲
循环队列	环形结构，解决内存浪费问题	内存利用率高	容量固定	缓冲区、轮询调度
双端队列	支持两端插入和删除	灵活性高	实现复杂	浏览器历史、滑动窗口
优先队列	按优先级出队	灵活性强，适合调度任务	实现复杂，性能依赖于实现方法	任务调度、最短路径算法