数据结构详解：队列(Queue) - 先进先出的有序世界

引言

在我们的日常生活中，排队是一个非常常见的现象。无论是在银行等待办理业务，还是在餐厅等待用餐，甚至是在超市收银台付款，我们都遵循着一个基本原则：先到先得。这种"先来先服务"的模式，在计算机科学中被抽象为一种重要的数据结构——队列(Queue)。

队列是一种线性数据结构，遵循先进先出（First In First Out, FIFO）的原则。它就像一个管道，数据从一端进入，从另一端离开。这种特性使得队列在许多算法和系统设计中都扮演着关键角色。

队列的基本概念

什么是队列？

队列是一种抽象数据类型（Abstract Data Type, ADT），它定义了一系列操作：

入队（Enqueue）: 在队列的末尾添加元素
出队（Dequeue）: 从队列的前端移除元素
前端查看（Front/Peek）: 查看队列前端的元素但不移除
判断是否为空（isEmpty）: 检查队列是否为空
获取大小（Size）: 获取队列中元素的数量

队列的特性

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
队列的特点：
┌─────────────────────────────────────┐
│  先进先出 (FIFO)                      │
│  ┌───┐ ┌───┐ ┌───┐ ┌───┐           │
│  │ A │ │ B │ │ C │ │ D │ ← rear     │
│  └───┘ └───┘ └───┘ └───┘           │
│    ↑                               │
│  front                             │
│                                    │
│  出队方向 ←────────────── 入队方向    │
└─────────────────────────────────────┘

队列的可视化表示

让我们用ASCII艺术来表示队列的基本操作：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
初始空队列：
┌─────┐
│     │
└─────┘
front = rear = -1

入队操作 enqueue(10)：
┌─────┐
│ 10  │
└─────┘
front = 0, rear = 0

继续入队 enqueue(20), enqueue(30)：
┌─────┬─────┬─────┐
│ 10  │ 20  │ 30  │
└─────┴─────┴─────┘
front = 0, rear = 2

出队操作 dequeue()：
┌─────┬─────┐
│ 20  │ 30  │
└─────┴─────┘
front = 1, rear = 2
返回值: 10

现实生活中的队列实例

1. 餐厅排队系统

想象你在一家热门餐厅门口排队：

新客户加入队伍末尾（入队）
有空桌时，队伍前面的客户先进入（出队）
餐厅经理可以查看队伍前面是谁（peek）

2. 打印队列

办公室的网络打印机：

员工提交打印任务到队列末尾
打印机按顺序处理任务
系统管理员可以查看当前正在处理的任务

3. 操作系统进程调度

操作系统使用队列来管理进程：

新进程进入就绪队列
CPU调度器从队列前端选择进程执行
进程完成后从队列中移除

队列的实现方式

1. 基于数组的队列实现

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
/**
 * 基于数组实现的队列
 * 使用循环数组避免空间浪费
 */
public class ArrayQueue<T> {
    private Object[] array;      // 存储队列元素的数组
    private int front;           // 队列前端索引
    private int rear;            // 队列后端索引
    private int size;            // 当前队列中元素的数量
    private int capacity;        // 队列的最大容量

    /**
     * 构造函数，创建指定容量的队列
     * @param capacity 队列的最大容量
     */
    public ArrayQueue(int capacity) {
        this.capacity = capacity;
        this.array = new Object[capacity];
        this.front = 0;
        this.rear = -1;
        this.size = 0;
    }

    /**
     * 入队操作
     * 时间复杂度: O(1)
     * @param item 要入队的元素
     * @return 入队是否成功
     */
    public boolean enqueue(T item) {
        if (isFull()) {
            System.out.println("队列已满，无法入队");
            return false;
        }

        // 循环数组：当rear到达数组末尾时，回到开头
        rear = (rear + 1) % capacity;
        array[rear] = item;
        size++;

        System.out.println("入队: " + item + ", 当前大小: " + size);
        return true;
    }

    /**
     * 出队操作
     * 时间复杂度: O(1)
     * @return 出队的元素，队列为空时返回null
     */
    @SuppressWarnings("unchecked")
    public T dequeue() {
        if (isEmpty()) {
            System.out.println("队列为空，无法出队");
            return null;
        }

        T item = (T) array[front];
        array[front] = null;  // 避免内存泄漏
        front = (front + 1) % capacity;
        size--;

        System.out.println("出队: " + item + ", 当前大小: " + size);
        return item;
    }

    /**
     * 查看队列前端元素但不移除
     * 时间复杂度: O(1)
     * @return 队列前端的元素
     */
    @SuppressWarnings("unchecked")
    public T front() {
        if (isEmpty()) {
            return null;
        }
        return (T) array[front];
    }

    /**
     * 检查队列是否为空
     * @return 队列是否为空
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 检查队列是否已满
     * @return 队列是否已满
     */
    public boolean isFull() {
        return size == capacity;
    }

    /**
     * 获取队列当前大小
     * @return 队列中元素的数量
     */
    public int size() {
        return size;
    }

    /**
     * 显示队列内容（用于调试）
     */
    public void display() {
        if (isEmpty()) {
            System.out.println("队列为空");
            return;
        }

        System.out.print("队列内容: [");
        for (int i = 0; i < size; i++) {
            int index = (front + i) % capacity;
            System.out.print(array[index]);
            if (i < size - 1) {
                System.out.print(", ");
            }
        }
        System.out.println("]");
        System.out.println("Front索引: " + front + ", Rear索引: " + rear);
    }
}

2. 基于链表的队列实现

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
/**
 * 基于链表实现的队列
 * 动态大小，无容量限制
 */
public class LinkedQueue<T> {

    /**
     * 队列节点类
     */
    private class Node {
        T data;        // 节点数据
        Node next;     // 指向下一个节点的引用

        public Node(T data) {
            this.data = data;
            this.next = null;
        }
    }

    private Node front;    // 队列前端节点
    private Node rear;     // 队列后端节点
    private int size;      // 队列大小

    /**
     * 构造函数，创建空队列
     */
    public LinkedQueue() {
        this.front = null;
        this.rear = null;
        this.size = 0;
    }

    /**
     * 入队操作
     * 时间复杂度: O(1)
     * @param item 要入队的元素
     */
    public void enqueue(T item) {
        Node newNode = new Node(item);

        if (isEmpty()) {
            // 队列为空时，front和rear都指向新节点
            front = rear = newNode;
        } else {
            // 将新节点连接到rear后面，然后更新rear
            rear.next = newNode;
            rear = newNode;
        }

        size++;
        System.out.println("入队: " + item + ", 当前大小: " + size);
    }

    /**
     * 出队操作
     * 时间复杂度: O(1)
     * @return 出队的元素，队列为空时返回null
     */
    public T dequeue() {
        if (isEmpty()) {
            System.out.println("队列为空，无法出队");
            return null;
        }

        T item = front.data;
        front = front.next;
        size--;

        // 如果队列变为空，需要更新rear
        if (front == null) {
            rear = null;
        }

        System.out.println("出队: " + item + ", 当前大小: " + size);
        return item;
    }

    /**
     * 查看队列前端元素但不移除
     * 时间复杂度: O(1)
     * @return 队列前端的元素
     */
    public T front() {
        if (isEmpty()) {
            return null;
        }
        return front.data;
    }

    /**
     * 检查队列是否为空
     * @return 队列是否为空
     */
    public boolean isEmpty() {
        return front == null;
    }

    /**
     * 获取队列大小
     * @return 队列中元素的数量
     */
    public int size() {
        return size;
    }

    /**
     * 显示队列内容（用于调试）
     */
    public void display() {
        if (isEmpty()) {
            System.out.println("队列为空");
            return;
        }

        System.out.print("队列内容: [");
        Node current = front;
        while (current != null) {
            System.out.print(current.data);
            if (current.next != null) {
                System.out.print(", ");
            }
            current = current.next;
        }
        System.out.println("]");
    }
}

队列的类型

1. 循环队列 (Circular Queue)

循环队列是一种优化的数组队列实现，通过将数组的末尾连接到开头来形成一个环形结构。

流程图表

关系流向：

1
2
3
4
5
A[0] → B[1]
B → C[2]
C → D[3]
D → E[4]
E → A

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
 * 循环队列实现
 * 通过模运算实现环形结构
 */
public class CircularQueue<T> {
    private Object[] array;
    private int front;
    private int rear;
    private int capacity;

    public CircularQueue(int capacity) {
        this.capacity = capacity + 1;  // 多分配一个位置用于区分满和空
        this.array = new Object[this.capacity];
        this.front = 0;
        this.rear = 0;
    }

    public boolean enqueue(T item) {
        if (isFull()) {
            return false;
        }
        array[rear] = item;
        rear = (rear + 1) % capacity;
        return true;
    }

    @SuppressWarnings("unchecked")
    public T dequeue() {
        if (isEmpty()) {
            return null;
        }
        T item = (T) array[front];
        array[front] = null;
        front = (front + 1) % capacity;
        return item;
    }

    public boolean isEmpty() {
        return front == rear;
    }

    public boolean isFull() {
        return (rear + 1) % capacity == front;
    }

    public int size() {
        return (rear - front + capacity) % capacity;
    }
}

2. 优先级队列 (Priority Queue)

优先级队列中的元素按照优先级排序，优先级高的元素先出队。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
import java.util.Comparator;

/**
 * 优先级队列实现
 * 使用最小堆实现，也可以使用最大堆
 */
public class PriorityQueue<T> {
    private Object[] heap;
    private int size;
    private int capacity;
    private Comparator<T> comparator;

    public PriorityQueue(int capacity) {
        this(capacity, null);
    }

    public PriorityQueue(int capacity, Comparator<T> comparator) {
        this.capacity = capacity;
        this.heap = new Object[capacity];
        this.size = 0;
        this.comparator = comparator;
    }

    /**
     * 入队操作（插入元素）
     * 时间复杂度: O(log n)
     */
    public boolean enqueue(T item) {
        if (size >= capacity) {
            return false;
        }

        heap[size] = item;
        heapifyUp(size);
        size++;
        return true;
    }

    /**
     * 出队操作（移除最高优先级元素）
     * 时间复杂度: O(log n)
     */
    @SuppressWarnings("unchecked")
    public T dequeue() {
        if (isEmpty()) {
            return null;
        }

        T result = (T) heap[0];
        heap[0] = heap[size - 1];
        heap[size - 1] = null;
        size--;

        if (!isEmpty()) {
            heapifyDown(0);
        }

        return result;
    }

    @SuppressWarnings("unchecked")
    private void heapifyUp(int index) {
        while (index > 0) {
            int parentIndex = (index - 1) / 2;
            if (compare((T) heap[index], (T) heap[parentIndex]) >= 0) {
                break;
            }
            swap(index, parentIndex);
            index = parentIndex;
        }
    }

    @SuppressWarnings("unchecked")
    private void heapifyDown(int index) {
        while (index < size) {
            int minIndex = index;
            int leftChild = 2 * index + 1;
            int rightChild = 2 * index + 2;

            if (leftChild < size && compare((T) heap[leftChild], (T) heap[minIndex]) < 0) {
                minIndex = leftChild;
            }

            if (rightChild < size && compare((T) heap[rightChild], (T) heap[minIndex]) < 0) {
                minIndex = rightChild;
            }

            if (minIndex == index) {
                break;
            }

            swap(index, minIndex);
            index = minIndex;
        }
    }

    private void swap(int i, int j) {
        Object temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }

    @SuppressWarnings("unchecked")
    private int compare(T a, T b) {
        if (comparator != null) {
            return comparator.compare(a, b);
        }
        return ((Comparable<T>) a).compareTo(b);
    }

    public boolean isEmpty() {
        return size == 0;
    }

    @SuppressWarnings("unchecked")
    public T peek() {
        return isEmpty() ? null : (T) heap[0];
    }
}

3. 双端队列 (Deque - Double-ended Queue)

双端队列允许在两端进行插入和删除操作。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
/**
 * 双端队列实现
 * 支持在队列两端进行插入和删除操作
 */
public class Deque<T> {
    private Object[] array;
    private int front;
    private int rear;
    private int size;
    private int capacity;

    public Deque(int capacity) {
        this.capacity = capacity;
        this.array = new Object[capacity];
        this.front = 0;
        this.rear = -1;
        this.size = 0;
    }

    /**
     * 在前端插入元素
     */
    public boolean addFront(T item) {
        if (isFull()) {
            return false;
        }

        front = (front - 1 + capacity) % capacity;
        array[front] = item;
        size++;
        return true;
    }

    /**
     * 在后端插入元素
     */
    public boolean addRear(T item) {
        if (isFull()) {
            return false;
        }

        rear = (rear + 1) % capacity;
        array[rear] = item;
        size++;
        return true;
    }

    /**
     * 从前端删除元素
     */
    @SuppressWarnings("unchecked")
    public T removeFront() {
        if (isEmpty()) {
            return null;
        }

        T item = (T) array[front];
        array[front] = null;
        front = (front + 1) % capacity;
        size--;
        return item;
    }

    /**
     * 从后端删除元素
     */
    @SuppressWarnings("unchecked")
    public T removeRear() {
        if (isEmpty()) {
            return null;
        }

        T item = (T) array[rear];
        array[rear] = null;
        rear = (rear - 1 + capacity) % capacity;
        size--;
        return item;
    }

    @SuppressWarnings("unchecked")
    public T peekFront() {
        return isEmpty() ? null : (T) array[front];
    }

    @SuppressWarnings("unchecked")
    public T peekRear() {
        return isEmpty() ? null : (T) array[rear];
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean isFull() {
        return size == capacity;
    }

    public int size() {
        return size;
    }
}

队列操作的可视化演示

让我们通过一个完整的示例来演示队列的各种操作：

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
/**
 * 队列操作演示类
 */
public class QueueDemo {

    /**
     * 演示基本队列操作
     */
    public static void demonstrateBasicOperations() {
        System.out.println("=== 基本队列操作演示 ===");

        ArrayQueue<Integer> queue = new ArrayQueue<>(5);

        // 演示入队操作
        System.out.println("\n1. 入队操作：");
        queue.enqueue(10);
        queue.display();

        queue.enqueue(20);
        queue.display();

        queue.enqueue(30);
        queue.display();

        // 演示查看前端元素
        System.out.println("\n2. 查看前端元素：");
        System.out.println("前端元素: " + queue.front());
        queue.display();

        // 演示出队操作
        System.out.println("\n3. 出队操作：");
        Integer removed = queue.dequeue();
        System.out.println("出队元素: " + removed);
        queue.display();

        // 继续入队测试循环特性
        System.out.println("\n4. 继续入队测试循环特性：");
        queue.enqueue(40);
        queue.enqueue(50);
        queue.enqueue(60);
        queue.display();

        // 尝试入队到满队列
        System.out.println("\n5. 尝试入队到满队列：");
        queue.enqueue(70);  // 应该失败
    }

    /**
     * 演示优先级队列操作
     */
    public static void demonstratePriorityQueue() {
        System.out.println("\n\n=== 优先级队列操作演示 ===");

        // 创建优先级队列（数字越小优先级越高）
        PriorityQueue<Integer> pq = new PriorityQueue<>(10);

        System.out.println("\n入队顺序: 30, 10, 20, 5, 25");
        pq.enqueue(30);
        pq.enqueue(10);
        pq.enqueue(20);
        pq.enqueue(5);
        pq.enqueue(25);

        System.out.println("\n按优先级出队:");
        while (!pq.isEmpty()) {
            System.out.println("出队: " + pq.dequeue());
        }
    }

    /**
     * 演示双端队列操作
     */
    public static void demonstrateDeque() {
        System.out.println("\n\n=== 双端队列操作演示 ===");

        Deque<String> deque = new Deque<>(5);

        System.out.println("\n1. 在后端添加元素:");
        deque.addRear("A");
        deque.addRear("B");
        System.out.println("队列状态: A <- B");

        System.out.println("\n2. 在前端添加元素:");
        deque.addFront("X");
        deque.addFront("Y");
        System.out.println("队列状态: Y <- X <- A <- B");

        System.out.println("\n3. 从前端删除:");
        System.out.println("删除: " + deque.removeFront());
        System.out.println("队列状态: X <- A <- B");

        System.out.println("\n4. 从后端删除:");
        System.out.println("删除: " + deque.removeRear());
        System.out.println("队列状态: X <- A");
    }

    /**
     * 模拟餐厅排队系统
     */
    public static void simulateRestaurantQueue() {
        System.out.println("\n\n=== 餐厅排队系统模拟 ===");

        LinkedQueue<String> restaurantQueue = new LinkedQueue<>();

        // 客户陆续到达
        System.out.println("\n客户到达:");
        String[] customers = {"张三", "李四", "王五", "赵六", "孙七"};

        for (String customer : customers) {
            restaurantQueue.enqueue(customer);
            System.out.println(customer + " 加入队列");
        }

        restaurantQueue.display();

        // 餐厅有空桌，开始服务客户
        System.out.println("\n开始服务客户:");
        while (!restaurantQueue.isEmpty()) {
            String customer = restaurantQueue.dequeue();
            System.out.println("正在为 " + customer + " 服务");
            restaurantQueue.display();

            // 模拟服务时间
            try {
                Thread.sleep(1000);
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
            }
        }

        System.out.println("所有客户已服务完毕！");
    }

    public static void main(String[] args) {
        demonstrateBasicOperations();
        demonstratePriorityQueue();
        demonstrateDeque();
        simulateRestaurantQueue();
    }
}

性能分析

时间复杂度分析

操作	数组实现	链表实现	循环队列	优先级队列
入队 (Enqueue)	O(1)	O(1)	O(1)	O(log n)
出队 (Dequeue)	O(1)	O(1)	O(1)	O(log n)
查看前端 (Front/Peek)	O(1)	O(1)	O(1)	O(1)
检查是否为空	O(1)	O(1)	O(1)	O(1)
获取大小	O(1)	O(1)	O(1)	O(1)

空间复杂度分析

实现方式	空间复杂度	说明
数组实现	O(n)	固定大小数组，可能存在空间浪费
链表实现	O(n)	动态分配，额外的指针开销
循环队列	O(n)	固定大小，空间利用率高
优先级队列	O(n)	通常基于堆实现

各种实现的优缺点

数组实现

1
2
3
4
5
6
7
8
9
优点:
✓ 访问速度快（连续内存）
✓ 实现简单
✓ 缓存友好

缺点:
✗ 固定大小限制
✗ 可能存在空间浪费
✗ 扩容操作复杂

链表实现

1
2
3
4
5
6
7
8
9
优点:
✓ 动态大小
✓ 内存利用率高
✓ 插入删除效率高

缺点:
✗ 额外的指针开销
✗ 不支持随机访问
✗ 缓存不友好

循环队列

1
2
3
4
5
6
7
8
优点:
✓ 空间利用率最高
✓ 操作效率稳定
✓ 实现相对简单

缺点:
✗ 固定大小限制
✗ 满/空判断略复杂

队列的应用场景

1. 广度优先搜索 (BFS)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * 使用队列实现图的广度优先搜索
 */
public class BFSExample {

    public static void bfsTraversal(int[][] graph, int start) {
        int n = graph.length;
        boolean[] visited = new boolean[n];
        LinkedQueue<Integer> queue = new LinkedQueue<>();

        // 从起始节点开始
        queue.enqueue(start);
        visited[start] = true;

        System.out.println("BFS遍历顺序:");

        while (!queue.isEmpty()) {
            int current = queue.dequeue();
            System.out.print(current + " ");

            // 访问所有相邻的未访问节点
            for (int i = 0; i < n; i++) {
                if (graph[current][i] == 1 && !visited[i]) {
                    queue.enqueue(i);
                    visited[i] = true;
                }
            }
        }
        System.out.println();
    }
}

2. 任务调度系统

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/**
 * 简单的任务调度系统
 */
public class TaskScheduler {
    private LinkedQueue<Task> taskQueue;

    public TaskScheduler() {
        this.taskQueue = new LinkedQueue<>();
    }

    /**
     * 添加任务到队列
     */
    public void addTask(Task task) {
        taskQueue.enqueue(task);
        System.out.println("任务已添加: " + task.getName());
    }

    /**
     * 执行下一个任务
     */
    public void executeNextTask() {
        if (taskQueue.isEmpty()) {
            System.out.println("没有待执行的任务");
            return;
        }

        Task task = taskQueue.dequeue();
        System.out.println("正在执行任务: " + task.getName());
        task.execute();
    }

    /**
     * 执行所有任务
     */
    public void executeAllTasks() {
        while (!taskQueue.isEmpty()) {
            executeNextTask();
        }
    }

    // 任务类
    static class Task {
        private String name;

        public Task(String name) {
            this.name = name;
        }

        public String getName() {
            return name;
        }

        public void execute() {
            // 模拟任务执行
            System.out.println("任务 " + name + " 执行完成");
        }
    }
}

3. 缓冲区管理

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
 * 生产者-消费者模式的缓冲区
 */
public class Buffer<T> {
    private ArrayQueue<T> queue;
    private final Object lock = new Object();

    public Buffer(int capacity) {
        this.queue = new ArrayQueue<>(capacity);
    }

    /**
     * 生产者添加数据
     */
    public void produce(T item) throws InterruptedException {
        synchronized (lock) {
            while (queue.isFull()) {
                System.out.println("缓冲区已满，生产者等待...");
                lock.wait();
            }

            queue.enqueue(item);
            System.out.println("生产: " + item);
            lock.notifyAll();  // 通知消费者
        }
    }

    /**
     * 消费者获取数据
     */
    public T consume() throws InterruptedException {
        synchronized (lock) {
            while (queue.isEmpty()) {
                System.out.println("缓冲区为空，消费者等待...");
                lock.wait();
            }

            T item = queue.dequeue();
            System.out.println("消费: " + item);
            lock.notifyAll();  // 通知生产者
            return item;
        }
    }
}

队列在Java标准库中的实现

Java标准库提供了多种队列实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import java.util.*;
import java.util.concurrent.*;

/**
 * Java标准库中的队列使用示例
 */
public class JavaQueueExamples {

    public static void demonstrateStandardQueues() {
        // 1. LinkedList实现的队列
        Queue<String> linkedQueue = new LinkedList<>();
        linkedQueue.offer("A");
        linkedQueue.offer("B");
        System.out.println("LinkedList队列: " + linkedQueue.poll());

        // 2. ArrayDeque实现的双端队列
        Deque<Integer> arrayDeque = new ArrayDeque<>();
        arrayDeque.addFirst(1);
        arrayDeque.addLast(2);
        System.out.println("ArrayDeque前端: " + arrayDeque.removeFirst());

        // 3. PriorityQueue优先级队列
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        priorityQueue.offer(30);
        priorityQueue.offer(10);
        priorityQueue.offer(20);
        System.out.println("PriorityQueue: " + priorityQueue.poll()); // 输出10

        // 4. 阻塞队列（线程安全）
        BlockingQueue<String> blockingQueue = new ArrayBlockingQueue<>(10);
        try {
            blockingQueue.put("Item1");
            System.out.println("阻塞队列: " + blockingQueue.take());
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        }
    }
}

总结

队列作为一种基础数据结构，在计算机科学和软件开发中发挥着重要作用。通过本文，我们深入了解了：

核心概念

FIFO原则：先进先出是队列的基本特性
基本操作：入队、出队、查看前端、判空等
实现方式：数组、链表、循环数组各有优缺点

队列类型

普通队列：基础的FIFO队列
循环队列：优化空间利用率
优先级队列：基于优先级的排序队列
双端队列：支持两端操作的灵活队列

性能特点

1
2
3
4
5
6
7
8
9
队列操作的时间复杂度总结：
┌─────────────────┬─────────────────┐
│     操作        │    时间复杂度    │
├─────────────────┼─────────────────┤
│   入队 (enqueue) │      O(1)       │
│   出队 (dequeue) │      O(1)       │
│   查看前端 (peek) │      O(1)       │
│   判空 (isEmpty) │      O(1)       │
└─────────────────┴─────────────────┘

应用场景

队列在以下场景中特别有用：

任务调度和作业队列
广度优先搜索算法
缓冲区和数据流处理
生产者-消费者模式
操作系统进程管理

选择建议

在实际开发中选择队列实现时，考虑以下因素：

性能需求：是否需要高频的入队出队操作
内存限制：是否对内存使用有严格要求
并发需求：是否需要线程安全的实现
功能需求：是否需要优先级、双端操作等特殊功能

队列的设计哲学体现了计算机科学中"抽象"和"封装"的核心思想。通过提供简洁一致的接口，队列隐藏了底层实现的复杂性，使得开发者能够专注于业务逻辑而不是数据结构的细节。

掌握队列不仅能帮助我们更好地理解算法和数据结构，更重要的是培养了我们的抽象思维和系统设计能力。在现代软件开发中，无论是分布式系统的消息队列，还是前端框架的事件队列，队列的概念和原理都无处不在。

希望这篇文章能够帮助您深入理解队列这一重要的数据结构，并在实际项目中灵活运用。记住，好的数据结构选择往往是高效程序的基础！

数据结构详解：队列(Queue) - 先进先出的有序世界#

引言#

队列的基本概念#

什么是队列？#

队列的特性#

队列的可视化表示#

现实生活中的队列实例#

1. 餐厅排队系统#

2. 打印队列#

3. 操作系统进程调度#

队列的实现方式#

1. 基于数组的队列实现#

2. 基于链表的队列实现#

队列的类型#

1. 循环队列 (Circular Queue)#

流程图表#

2. 优先级队列 (Priority Queue)#

3. 双端队列 (Deque - Double-ended Queue)#

队列操作的可视化演示#

性能分析#

时间复杂度分析#

空间复杂度分析#

各种实现的优缺点#

数组实现#

链表实现#

循环队列#

队列的应用场景#

1. 广度优先搜索 (BFS)#

2. 任务调度系统#

3. 缓冲区管理#

队列在Java标准库中的实现#

总结#

核心概念#

队列类型#

性能特点#

应用场景#

选择建议#