目录

1. 队列的定义

2. 队列的特点

3. 队列的基本操作

4. 队列的实现方式

   • 4.1 数组实现（顺序队列）

   • 4.2 链表实现（链式队列）

5. 循环队列

6. 双端队列（Deque）

7. 优先队列（Priority Queue）

8. 队列的应用场景

9. 复杂度分析

---

1. 队列的定义

队列是一种先进先出（FIFO, First In First Out）的线性数据结构。元素的插入（入队）在队尾进行，元素的删除（出队）在队首进行。

---

2. 队列的特点

• 操作受限：只能在一端插入（rear），另一端删除（front）

• 动态集合：元素数量可动态变化

• FIFO 原则：最早入队的元素最先被处理

---

3. 队列的基本操作

操作	描述	时间复杂度
enqueue()	向队尾添加元素	O(1)
dequeue()	移除队首元素	O(1)
peek()	查看队首元素（不删除）	O(1)
isEmpty()	检查队列是否为空	O(1)
isFull()	检查队列是否已满（仅限固定大小队列）	O(1)

---

4. 队列的实现方式

4.1 数组实现（顺序队列）（java）

​
public class ArrayQueue {
    private int maxSize;
    private int front; // 指向队首前一个位置
    private int rear;  // 指向队尾元素
    private int[] arr;
​
    // 初始化队列
    public ArrayQueue(int size) {
        maxSize = size;
        arr = new int[maxSize];
        front = -1;
        rear = -1;
    }
​
    // 入队操作
    public void enqueue(int value) {
        if (isFull()) {
            System.out.println("队列已满");
            return;
        }
        if (isEmpty()) front = 0;
        arr[++rear] = value;
    }
​
    // 出队操作
    public int dequeue() {
        if (isEmpty()) throw new RuntimeException("队列空");
        int value = arr[front++];
        if (front > rear) { // 队列已空时重置指针
            front = -1;
            rear = -1;
        }
        return value;
    }
​
    // 判断队列是否为空
    public boolean isEmpty() {
        return front == -1 && rear == -1;
    }
​
    // 判断队列是否已满
    public boolean isFull() {
        return rear == maxSize - 1;
    }
}

4.2 链表实现（链式队列）

class Node {
    int data;
    Node next;
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}
​
public class LinkedQueue {
    private Node front;
    private Node rear;
​
    // 入队
    public void enqueue(int value) {
        Node newNode = new Node(value);
        if (rear == null) {
            front = rear = newNode;
        } else {
            rear.next = newNode;
            rear = newNode;
        }
    }
​
    // 出队
    public int dequeue() {
        if (isEmpty()) throw new RuntimeException("队列空");
        int value = front.data;
        front = front.next;
        if (front == null) rear = null;
        return value;
    }
}

---

5. 循环队列

解决数组实现的"假溢出"问题，通过取模运算实现空间复用。

class CircularQueue {
    private int[] data;
    private int front;
    private int rear;
    private int size;
​
    public CircularQueue(int k) {
        data = new int[k];
        front = -1;
        rear = -1;
        size = k;
    }
​
    public boolean enQueue(int value) {
        if (isFull()) return false;
        if (isEmpty()) front = 0;
        rear = (rear + 1) % size;
        data[rear] = value;
        return true;
    }
​
    public boolean deQueue() {
        if (isEmpty()) return false;
        if (front == rear) {
            front = -1;
            rear = -1;
        } else {
            front = (front + 1) % size;
        }
        return true;
    }
}

---

6. 双端队列（Deque）

允许两端进行插入和删除操作的高级队列。

操作	描述
addFirst()	在队首插入元素
addLast()	在队尾插入元素
removeFirst()	删除并返回队首元素
removeLast()	删除并返回队尾元素

---

7. 优先队列（Priority Queue）

元素带有优先级的队列，总是取出优先级最高的元素。通常使用堆（Heap）实现。

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(3);  // 插入元素
pq.poll();  // 取出最小元素

---

8. 队列的应用场景

1. CPU 任务调度

2. 打印机作业队列

3. 广度优先搜索（BFS）

4. 消息队列系统（如 RabbitMQ）

5. 实时系统事件处理

6. 呼叫中心电话排队

---

9. 复杂度分析

实现方式	入队	出队	查找	空间
数组队列	O(1)	O(1)	O(n)	O(n)
链表队列	O(1)	O(1)	O(n)	O(n)
循环队列	O(1)	O(1)	O(n)	O(n)
优先队列（堆）	O(log n)	O(log n)	O(n)	O(n)