02. 队列

moye Lv6
  2024-07-18 14:19:37 2024-07-18 14:19:37 创建   2025-12-11 14:39:48 2025-12-11 14:39:48 更新      

队列：优雅的数据结构

队列是一种经典的数据结构，它以先进先出（First In First Out，FIFO）的方式管理数据。

在计算机科学中，队列被广泛应用于各种场景，从操作系统任务调度到网络通信，都能看到它的身影。

1. 队列的基本概念

队列是一种线性数据结构，具有两个主要操作：入队（enqueue）和出队（dequeue）。数据项从队尾入队，从队头出队，保证了先进入队列的元素先被取出。这种特性使得队列非常适用于需要按照顺序处理的问题。

2. 队列的实现

2.1 队列的实现思路

队列本身是有序列表，若使用数组结构存储队列数据，则队列数据声明如下图，其中maxSize是该队列的最大容量。

队列的输入、输出分别从前后端来处理，因此需要两个变量front、rear分别记录队列前后端的下标，front会随着数据输出而改变，而rear则随着数据输入而改变。

数据存入称为addQueue：

  1. 队尾指针往后移: rear+1, front == rear时队列为空
  2. 队尾指针rear小于队列的最大标maxSize-1，则将数据存入rear所指的数组元组中，否则无法存入数据。rear == maxSize-1时，队列满。

2.2 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
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
package org.example;  
  
import java.util.Scanner;  
  
public class ArrayQueue {  
    private int maxSize;  
    private int front;  
    private int rear;  
    private int[] arr;//该数组用于存放数据，模拟队列  
  
    //创建队列的构造器  
    public ArrayQueue(int arrMaxSize) {  
        maxSize = arrMaxSize;  
        arr = new int[maxSize];  
        front = -1;//指向队列头部，分析出front是指向队列头的前一个位置  
        rear = -1;//指向队列尾部，指向队列尾的数据（即就是队列最后一个数据）  
    }  
  
    //判断队列是否满  
    public boolean isFull() {  
        return rear == maxSize - 1;  
    }  
  
    //判断队列是否为空  
    public boolean isEmpty() {  
        return rear == front;  
    }  
  
    //添加数据到队列  
    public void addQueue(int n) {  
        //判断队列是否满  
        if (isFull()) {  
            System.out.println("队列满，不能加入数据");  
            return;  
        }  
        rear++;//让rear后移  
        arr[rear] = n;  
    }  
  
    //获取队列的数据，出队列  
    public int getQueue() {  
        //判断队列是否为空  
        if (isEmpty()) {  
            //通过抛出异常  
            throw new RuntimeException("队列空，不能取数据");  
        }  
        front++;//front后移  
        return arr[front];  
    }  
  
    //显示队列的所有数据  
    public void showQueue() {  
        //遍历  
        if (isEmpty()) {  
            System.out.println("队列空的，没有数据");  
            return;  
        }  
        for (int i = 0; i < arr.length; i++) {  
            System.out.printf("arr[%d]=%d\n", i, arr[i]);  
        }  
    }  
  
    //显示队列的头数据，注意不是取出数据  
    public int headQueue() {  
        //判断  
        if (isEmpty()) {  
            throw new RuntimeException("队列空的，没有数据");  
        }  
        return arr[front + 1];  
    }  
  
    public static void main(String[] args) {  
        //测试一把  
        System.out.println("测试数组模拟队列的案例~~~");  
        //创建一个队列  
        ArrayQueue queue = new ArrayQueue(3);  
        char key = ' ';//接收用户输入  
        Scanner scanner = new Scanner(System.in);  
        boolean loop = true;  
        //输出一个菜单  
        while (loop) {  
            System.out.println("s(show):显示队列");  
            System.out.println("e(exit):退出程序");  
            System.out.println("a(add):添加数据到队列");  
            System.out.println("g(get):从队列取出数据");  
            System.out.println("h(head):查看队列头的数据");  
            //接收一个字符  
            key = scanner.next().charAt(0);  
            switch (key) {  
                case 's'://显示队列  
                    queue.showQueue();  
                    break;  
                case 'a'://添加数据到队列  
                    System.out.println("输出一个数");  
                    int value = scanner.nextInt();  
                    queue.addQueue(value);  
                    break;  
                case 'g'://从队列取出数据  
                    try {  
                        int res = queue.getQueue();  
                        System.out.printf("取出的数据是%d\n", res);  
                    } catch (Exception e) {  
                        System.out.println(e.getMessage());  
                    }  
                    break;  
                case 'h'://查看队列头的数据  
                    try {  
                        int res = queue.headQueue();  
                        System.out.printf("队列头的数据是%d\n", res);  
                    } catch (Exception e) {  
                        System.out.println(e.getMessage());  
                    }  
                    break;  
                case 'e'://退出  
                    scanner.close();  
                    loop = false;  
                    break;  
                default:  
                    break;  
            }  
        }  
        System.out.println("程序退出~~~");  
    }  
}

2.3 Python实现队列的基本结构

队列可以使用数组或链表等数据结构来实现。以下是一个简单的队列实现示例（使用Python）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
```python
class Queue:
    def __init__(self):
        self.items = []

    def is_empty(self):
        return len(self.items) == 0

    def enqueue(self, item):
        self.items.append(item)

    def dequeue(self):
        if not self.is_empty():
            return self.items.pop(0)

    def size(self):
        return len(self.items)

2.4示例：使用队列解决问题

场景：打印任务队列

考虑一个打印任务队列的场景。当多个打印任务同时到达，我们希望它们按照先来先服务的原则依次完成打印。使用队列可以轻松实现这一需求。

1
2
3
4
5
6
7
8
9
10
11
12
# 创建一个打印任务队列
print_queue = Queue()

# 入队打印任务
print_queue.enqueue("Print Document 1")
print_queue.enqueue("Print Document 2")
print_queue.enqueue("Print Document 3")

# 出队并执行打印
while not print_queue.is_empty():
    current_task = print_queue.dequeue()
    print("Printing:", current_task)

这个示例展示了队列在处理按顺序到达的任务时的便利性。

3. 环形队列

循环队列是队列的一种变体，它通过循环使用数组或链表的空间，使得队列可以在队尾和队头之间形成环形结构。在这篇文章中，我们将深入研究循环队列的基本概念、实现方式以及在实际应用中的优势。

实现思路：

  1. front指向队列的第一个元素，初始值默认为0
  2. rear指向队列最后一个元素的后一个位置，初始值为0。空出空间作为约定。
  3. 当队列满时，（rear+1）% maxSize == front
  4. 当队列空时，rear == front
  5. 队列中有效的数据个数，（rear+maxSize-front）% maxSize

3.1 循环队列的基本概念

与普通队列不同，循环队列在队尾和队头之间建立了连接，形成了一个环。这意味着当队尾指针到达数组的末尾时，它可以循环回到数组的开头，从而更好地利用存储空间。

3.2 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
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
package org.example;  
  
import java.util.Scanner;  
  
public class CircleArrayQueue {  
    private int maxSize;  
    private int front;  
    private int rear;  
    private int[] arr;//该数组用于存放数据，模拟队列  
  
    //创建队列的构造器  
    public CircleArrayQueue(int arrMaxSize) {  
        maxSize = arrMaxSize;  
        arr = new int[maxSize];  
        front = 0;//指向队列头部，分析出front是指向队列头的前一个位置  
        rear = 0;//指向队列尾部，指向队列尾的数据（即就是队列最后一个数据）  
    }  
  
    //判断队列是否满  
    public boolean isFull() {  
        return (rear + 1) % maxSize == front;  
    }  
  
    //判断队列是否为空  
    public boolean isEmpty() {  
        return rear == front;  
    }  
  
    //添加数据到队列  
    public void addQueue(int n) {  
        //判断队列是否满  
        if (isFull()) {  
            System.out.println("队列满，不能加入数据");  
            return;  
        }  
        arr[rear] = n;  
        rear = (rear + 1) % maxSize;  
    }  
  
    //获取队列的数据，出队列  
    public int getQueue() {  
        //判断队列是否为空  
        if (isEmpty()) {  
            //通过抛出异常  
            throw new RuntimeException("队列空，不能取数据");  
        }  
        int value = arr[front];  
        front = (front + 1) % maxSize;  
        return value;  
    }  
  
    //显示队列的所有数据  
    public void showQueue() {  
        //遍历  
        if (isEmpty()) {  
            System.out.println("队列空的，没有数据");  
            return;  
        }  
        for (int i = front; i < front + size(); i++) {  
            System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]);  
        }  
    }  
  
    //当前队列的有效数据  
    public int size() {  
        return (rear + maxSize - front) % maxSize;  
    }  
}

3.3 Python实现环形队列的基本结构

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
class CircularQueue:
    def __init__(self, capacity):
        self.capacity = capacity
        self.queue = [None] * capacity
        self.front = self.rear = -1

    def is_empty(self):
        return self.front == -1

    def is_full(self):
        return (self.rear + 1) % self.capacity == self.front

    def enqueue(self, item):
        if self.is_full():
            print("Queue is full. Cannot enqueue.")
        else:
            if self.is_empty():
                self.front = self.rear = 0
            else:
                self.rear = (self.rear + 1) % self.capacity
            self.queue[self.rear] = item

    def dequeue(self):
        if self.is_empty():
            print("Queue is empty. Cannot dequeue.")
        else:
            removed_item = self.queue[self.front]
            if self.front == self.rear:
                self.front = self.rear = -1
            else:
                self.front = (self.front + 1) % self.capacity
            return removed_item

3.4 示例：使用循环队列解决问题

场景：循环缓冲区

考虑一个循环缓冲区的场景，其中数据按顺序写入循环队列，当队列满时，新的数据会覆盖最早的数据。

1
2
3
4
5
6
7
8
9
10
# 创建一个容量为 5 的循环队列
circular_queue = CircularQueue(5)

# 入队数据
for i in range(1, 8):
    circular_queue.enqueue(f"Data {i}")

# 出队并显示队列内容
while not circular_queue.is_empty():
    print("Dequeue:", circular_queue.dequeue())

3.5 循环队列的优势

3.5.1 更高的空间利用率

由于循环队列的环形结构，它能够更好地利用存储空间，减少了不必要的内存浪费。

3.5.2 简化指针操作

循环队列通过使用取余运算简化了指针的操作，使得队头和队尾的指针移动更加高效。

3.6 循环队列的应用场景

3.6.1 缓存

循环队列常用于缓存系统中，用于处理数据的轮转和更新。

3.6.2 实时数据处理

在需要按时间顺序处理数据的场景中，循环队列能够提供高效的数据流管理。

  • 标题: 02. 队列
  • 作者: moye
  • 创建于 : 2024-07-18 14:19:37
  • 更新于 : 2025-12-11 14:39:48
  • 链接: https://www.kanes.top/2024/07/18/02. 队列/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
目录
02. 队列
  1. 1. 队列：优雅的数据结构
    1. 1.1. 1. 队列的基本概念
    2. 1.2. 2. 队列的实现
      1. 1.2.1. 2.1 队列的实现思路
      2. 1.2.2. 2.2 Java实现队列的基本结构
      3. 1.2.3. 2.3 Python实现队列的基本结构
      4. 1.2.4. 2.4示例：使用队列解决问题
    3. 1.3. 3. 环形队列
      1. 1.3.1. 实现思路：
      2. 1.3.2. 3.1 循环队列的基本概念
      3. 1.3.3. 3.2 Java实现环形队列的基本结构
      4. 1.3.4. 3.3 Python实现环形队列的基本结构
      5. 1.3.5. 3.4 示例：使用循环队列解决问题
      6. 1.3.6. 3.5 循环队列的优势
      7. 1.3.7. 3.6 循环队列的应用场景