深入掌握STL Queue

一、基本概念

Queue是一种受限的线性结构，遵循先进先出(FIFO)原则。主要有两个关键方法：push()向队尾插入元素、pop()弹出队头元素。

在STL中，queue是一个模板类，包含在头文件 中。声明一个queue对象可以使用如下方式：

queue q; //创建一个空的int类型队列

  

queue默认使用deque作为底层容器进行实现，也可以通过指定另一种STL容器作为底层实现：

queue> q; //使用vector作为底层容器实现队列

  

二、基本操作与属性

1. push()和pop()

队列的最基本操作是push()和pop()，分别是在队列末尾添加一个元素和弹出队头元素。这两个操作都能够在常量时间完成。

queue q;
q.push(1); //队列中添加元素1
q.push(2); //队列中添加元素2
q.pop(); //弹出队列头元素1

  

2. front()和back()

除了基本操作外，队列还有两个辅助操作。front()返回队列的头元素，back()返回队列的尾元素。它们都在常量时间完成。但需要注意的是，在队列为空的时候使用front()和back()会导致一场，因此使用之前需要先通过empty()方法判断队列是否为空。

queue q;
q.push(1); //在队列末尾插入元素
q.push(2);
cout << q.front() << endl; //输出队列头元素1
cout << q.back() << endl; //输出队列尾元素2

  

3. empty()和size()

empty()方法用于检查队列是否为空，返回true表示队列为空，false表示队列不为空。size()方法用于返回队列中元素的个数。

queue q;
q.push(1);
q.push(2);
cout << q.empty() << endl; //输出0，队列不为空
cout << q.size() << endl; //输出2，队列中共有两个元素

  

三、应用场景

1. BFS搜索算法

队列在BFS搜索算法中扮演重要的角色。在BFS算法中，我们从起点开始搜索，遇到规定条件的节点就将其加入队列中，然后依次从队列中弹出节点，扩展其所有可到达的子节点并加入到队列中。如此迭代直到搜索到目标节点或者队列为空。

vector
   > graph; //图的邻接矩阵，0表示不联通
vector
     visited(n, false); //节点的访问标记
queue
      q;
q.push(start);
visited[start] = true;
while(!q.empty()) {
    int cur = q.front();
    q.pop();
    //处理当前节点cur的操作
    for(int i = 0; i < n; i++) {
        if(graph[cur][i] == 1 && !visited[i]) {
            q.push(i);
            visited[i] = true;
        }
    }
}

     
    
   
  

2. 多线程

在多线程编程过程中，队列可以被用于缓存数据，在多个线程之间进行数据交换和协同工作。例如，一个生产者线程将数据推入到队列中，一个或多个消费者线程则从队列中取出数据并进行处理。

queue q;
mutex m;
condition_variable cv;
//生产者线程
void push(int data) {
    unique_lock
    lock(m);
    q.push(data); //将数据压入队列中
    cv.notify_one(); //唤醒一个消费者线程
}
//消费者线程
void pop() {
    unique_lock
     lock(m);
    while(q.empty()) {
        cv.wait(lock); //等待唤醒，防止死锁
    }
    int data = q.front(); //从队列中取出数据
    q.pop(); //弹出队列头元素
    //进行对data的处理
}

    
   
  

3. 最近的K个元素

在某些场合，我们需要求解一个序列中最近的K个元素，这时我们可以使用队列来维护一个大小为K的滑动窗口，每当有新的元素到来时，判断是否可以加入队列，如果可以就将其加入队列尾部并弹出队头的元素。

vector nums; //原始数组
queue
    q; //维护窗口的队列
int k = 3; //窗口大小为3
for(int i = 0; i < nums.size(); i++) {
    if(q.size() >= k) { //队列已满
        q.pop(); //弹出队头的元素
    }
    q.push(nums[i]); //将新元素压入队列
    if(q.size() == k) { //队列满足窗口大小
        //进行对q中元素的处理
    }
}

   
  

总结

本篇文章从基本概念、基本操作与属性和应用场景三个方面介绍了STL queue的相关知识。熟练掌握STL queue，可以提高程序员编写代码的效率并提高代码可读性。