Queue – 队列

OHPJR • 2025-01-16 15:46 • 编程

一、队列的概述

队列(queue)是一种常见的, 先进先出 (FIFO, First-In-First-Out)的数据结构, 在队尾插入元素，在队头删除元素。

队列可以应用于: 线程任务调度、广度优先搜索、消息队列等场景，是一种非常重要的数据结构。

二、队列的实现

队列的实现可以基于链表(linked list)或数组(array)来实现，链表实现队列更加灵活方便，数组实现的队列有着更好的性能表现。

三、队列的操作

1、队列的初始化

    
        #include
        #include

        using namespace std;

        int main(){
            queue q; // 初始化一个空队列
            return 0;
        }

2、队列的插入操作

1) push()

在队列的末尾插入一个元素，时间复杂度为O(1)。

    
        queue q;
        q.push(1);    // 像队尾插入元素
        q.push(2);
        q.push(3);

2) emplace()

emplace()函数根据传入的参数构造一个新元素，将其插入队列的末尾。但emplace()与push()不同的是，emplace()避免了额外的构造函数和复制操作。

    
        struct Person{
            string name;
            int age;

            Person(string n, int a):name(n),age(a){}
        };

        queue q;
        q.emplace("Tom", 18);    // 在队列末尾插入一个Person类型的对象

3、队列的删除操作

1) pop()

队列的头部元素出队，时间复杂度为O(1)。

    
        queue q;
        q.push(1);
        q.push(2);
        q.push(3);
        q.pop();    // 弹出队头元素

4、队列的查询操作

1) front()

获取队列的头部元素，时间复杂度为O(1)。

    
        queue q;
        q.push(1);
        q.push(2);
        q.push(3);
        int x = q.front();    // 获取队头元素

2) empty()

判断队列是否为空，时间复杂度为O(1)。

    
        queue q;
        if(q.empty()){    // 判断队列是否为空
            cout << "Queue is empty." << endl;
        }

3) size()

返回队列中元素的个数，时间复杂度为O(1)。

    
        queue q;
        q.push(1);
        q.push(2);
        q.push(3);
        int n = q.size();    // 获取队列中元素个数

四、队列的应用场景

1、线程任务调度

在多线程编程中，通过队列来存储任务，从而实现任务的先进先出调度。

2、广度优先搜索

在图论算法中，广度优先搜索(Breadth First Search, BFS)就是通过队列实现的。

3、消息队列

在计算机网络中，消息队列(Message Queue)是一种异步通信机制，通过队列将消息从一个应用传递到另一个应用。

原创文章，作者：OHPJR，如若转载，请注明出处：https://www.506064.com/n/330622.html