常用C++队列（Queue）详解与应用

C++队列（Queue）详解与应用

为了一位同学作此篇

一、引言

在数据结构和算法中，队列（Queue）是一种非常重要的数据结构。它遵循“先进先出”（FIFO，First In First Out）的原则，即最先进入队列的元素将最先被移除。队列在计算机科学中有广泛的应用，如任务调度、打印任务管理、数据包处理等。

举个简单的例子，日常生活中排队就是一种队列。先进入队列的人将先进行操作然后离开队列。

在C++标准库中，头文件为我们提供了队列的实现。本文将详细介绍C++标准库中的队列，并通过示例来演示其使用方法。

二、C++标准库中的队列

C++标准库中的std::queue是一个容器适配器，它提供了一个队列的数据结构。std::queue的成员函数主要包括：

push(const value_type& val): 在队尾插入一个元素。
pop(): 移除队头的元素。
front(): 返回队头的元素（但不会移除）。
back(): 返回队尾的元素（但不会移除）。
size(): 返回队列中的元素个数。
empty(): 检查队列是否为空。
三、队列的基本操作示例
下面是一个简单的C++程序，演示了如何使用std::queue进行基本操作：

#include <iostream>  
#include <queue>  
  
int main() {  
    // 创建一个int类型的队列  
    std::queue<int> q;  
    //也可以写queue<int> q;
    // 向队列中添加元素  
    q.push(1);  
    q.push(2);  
    q.push(3);  
  
    // 输出队列的大小  
    std::cout << "Size of queue: " << q.size() << std::endl;  
  
    // 检查队列是否为空  
    std::cout << "Is queue empty? " << (q.empty() ? "Yes" : "No") << std::endl;  
  
    // 访问队头和队尾的元素  
    std::cout << "Front element: " << q.front() << std::endl;  
    std::cout << "Back element: " << q.back() << std::endl;  
  
    // 移除队头的元素  
    q.pop();  
  
    // 再次访问队头的元素  
    std::cout << "Front element after pop: " << q.front() << std::endl;  
  
    return 0;  
}
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

三、手动模拟队列

#include <iostream>  
  
using namespace std;  
  
// 定义队列节点  
struct Node {  
    int data;  
    Node* next;  
};  
  
// 定义队列  
class Queue {  
private:  
    Node* front;  
    Node* rear;  
  
public:  
    // 构造函数  
    Queue() {  
        front = rear = nullptr;  
    }  
  
    // 判断队列是否为空  
    bool isEmpty() {  
        return front == nullptr;  
    }  
  
    // 入队操作  
    void enqueue(int value) {  
        Node* newNode = new Node;  
        newNode->data = value;  
        newNode->next = nullptr;  
  
        if (isEmpty()) {  
            front = rear = newNode;  
            return;  
        }  
  
        rear->next = newNode;  
        rear = newNode;  
    }  
  
    // 出队操作  
    int dequeue() {  
        if (isEmpty()) {  
            cout << "Queue is empty!" << endl;  
            return -1;  
        }  
  
        Node* temp = front;  
        int value = front->data;  
        front = front->next;  
  
        if (front == nullptr) {  
            rear = nullptr;  
        }  
  
        delete temp;  
  
        return value;  
    }  
  
    // 显示队列元素  
    void display() {  
        Node* temp = front;  
  
        cout << "Queue elements: ";  
        while (temp != nullptr) {  
            cout << temp->data << " ";  
            temp = temp->next;  
        }  
  
        cout << endl;  
    }  
};  
  
int main() {  
    Queue q;  
  
    q.enqueue(10);  
    q.enqueue(20);  
    q.enqueue(30);  
  
    q.display();  
  
    cout << "Dequeue element: " << q.dequeue() << endl;  
  
    q.display();  
  
    return 0;  
}
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

四、指针实现队列

#include <iostream>  
  
using namespace std;  
  
// 定义队列节点  
struct Node {  
    int data;  
    Node* next;  
};  
  
// 定义队列  
class Queue {  
private:  
    Node* front;  
    Node* rear;  
  
public:  
    // 构造函数  
    Queue() {  
        front = rear = nullptr;  
    }  
  
    // 判断队列是否为空  
    bool isEmpty() {  
        return front == nullptr;  
    }  
  
    // 入队操作  
    void enqueue(int value) {  
        Node* newNode = new Node;  
        newNode->data = value;  
        newNode->next = nullptr;  
  
        if (isEmpty()) {  
            front = rear = newNode;  
            return;  
        }  
  
        rear->next = newNode;  
        rear = newNode;  
    }  
  
    // 出队操作  
    int dequeue() {  
        if (isEmpty()) {  
            cout << "Queue is empty!" << endl;  
            return -1;  
        }  
  
        Node* temp = front;  
        int value = front->data;  
        front = front->next;  
  
        if (front == nullptr) {  
            rear = nullptr;  
        }  
  
        delete temp;  
  
        return value;  
    }  
  
    // 显示队列元素  
    void display() {  
        Node* temp = front;  
  
        cout << "Queue elements: ";  
        while (temp != nullptr) {  
            cout << temp->data << " ";  
            temp = temp->next;  
        }  
  
        cout << endl;  
    }  
};  
  
int main() {  
    Queue q;  
  
    q.enqueue(10);  
    q.enqueue(20);  
    q.enqueue(30);  
  
    q.display();  
  
    cout << "Dequeue element: " << q.dequeue() << endl;  
  
    q.display();  
  
    return 0;  
}
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

五、队列的应用

1. 任务调度：在多线程或多任务环境中，std::queue 可以用来存储待处理的任务。当一个线程或任务处理器空闲时，它可以从队列的头部取出一个任务来处理。
2. 打印任务：在打印服务器或打印池中，打印任务可以按照它们被添加到队列中的顺序进行处理。这确保了公平性，并且防止了先到的任务被后到的任务阻塞。
3. 事件处理：在图形用户界面（GUI）编程中，事件（如鼠标点击、键盘按键等）通常被放入一个事件队列中。然后，一个事件循环会不断从队列中取出事件，并调用相应的处理程序。
4. 网络请求：在网络编程中，客户端发送的请求可以被放入一个请求队列中，等待服务器处理。服务器可以逐个处理这些请求，并按照它们被添加到队列中的顺序返回响应。
5. 数据流处理：在处理大量数据流（如实时视频流、音频流或网络数据流）时，std::queue 可以用来存储尚未处理的数据块。一旦有资源可用（如 CPU 时间片、内存空间等），就可以从队列中取出一个数据块进行处理。
6. 游戏循环：在游戏编程中，std::queue 可以用来存储玩家的输入命令（如移动、攻击等）。游戏循环可以不断从队列中取出这些命令，并更新游戏状态。
7. 广度优先搜索（BFS）：在图论算法中，广度优先搜索（BFS）经常使用队列来存储待访问的节点。当一个节点被访问时，它的所有未被访问的邻居节点都会被添加到队列中。
8. 模拟系统：在模拟系统（如交通模拟、物流模拟等）中，std::queue 可以用来模拟各种资源的等待队列。例如，在交通模拟中，车辆可能会在一个交叉口的等待队列中等待通过。

写作不易 留个赞呗