Queue - 队列

发布时间:2023-05-19

一、队列的概述

队列(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)是一种异步通信机制,通过队列将消息从一个应用传递到另一个应用。