队列与C++中的queue详解

2023-05-25 本文已影响0人艰默

队列（Queue）

什么是队列

队列就是一种线性的数据结构，它与日常生活中排队的队列相似，即先进先出（LIFO, First In First Out)，这点也是它与栈（Stack）的最大不同之处。它的结构类似于下面的容器：

队列

如上图所示，队列的结构就像一个两端都是开口的容器，一端只负责小球（对应队列中的元素）进入，一个端只负责小球弹出，容器内部的小球无法跳过前面的小球提前弹出。我们将队列的出口端（即队列的头部）叫做队头（front），入口端（即队列的末尾）称为队尾（rear）。

与栈类似，队列的底层数据结构也可以使用数组和链表来实现，具体如下图所示：

队列的实现

队列的基本操作和应用

队列的基本操作与栈类似，主要是分为入队（enqueue）和出队（dequeue），我们以数组为例，简单描述一下具体过程。

1. 入队

入队就是把新元素放入队列中去，由于队列的数据结构的限制，只允许将新入队元素放入队尾的位置，然后更新队尾的位置，具体过程如下图所示。

入队

2. 出队

出队就是把队列中的元素移出来，同样的，队列只允许在队列的队头这一侧移出元素，即每次移出的元素就是队头对应的元素，元素移出后，原对头元素的后面一个元素变为新的队头，具体过程如下所示：

出队

3. 入队出队的复杂度和应用

与栈类似，队列的入队与出队只与队头和队尾的元素相关，不涉及其他元素的移动，因此队列的入队和出队的时间复杂度都是 $O(1)$ 。

队列先进先出的特性使得其常用于一下场景中：

消息队列：在分布式系统或异步任务处理场景中，消息队列可以用于解耦任务的发布与消费，确保任务能够稳定地进行下去。
程序调度：操作系统、多线程程序、并发网络程序等需要协调多个任务的程序中，通常会使用队列来维护任务的执行顺序，以保证每个任务都能够得到执行。
广度优先搜索：在图论、路径查找等问题中，广度优先搜索算法通常会使用队列来存储待搜索的节点，以确保每一层的所有节点都可以被访问到。
缓存：在许多应用中，缓存通常使用队列来管理缓存项的过期时间和更替策略，使得缓存可以高效地使用有限的内存资源。

类模板std::queue

std::queue类是C++提供的容器适配器，它提供了特定的函数集合，实现了队列的基本功能：FIFO的数据结构，即在容器的尾端推入元素，在首段弹出元素。std::queue类在头文件<queue>中定义，其函数声明如下：

template<
    class T,
    class Container = std::deque<T>
> class queue;

形参T和Container

T：存储的元素类型。
Container：用于存储元素的底层容器。容器类型必须是序列容器，同时，该容器类型需提供通常语义下的back()、front()、push_back()和pop_front()函数，满足该要求的标准容器有std::deque和std::list，其中默认使用的容器是std::deque。

成员函数

1. 元素访问

front：访问队列第一个元素。其函数声明如下：
```
reference front();
const_reference front() const;
```
该函数返回队列中首个元素的引用，实际上该函数等效的调用的就是存储元素的底层容器（Container）的front()函数。
back：访问队列最后一个元素。其函数声明如下：
```
reference back();
const_reference back() const;
```
该函数返回的是队列末尾元素的引用，实际上该函数等效的调用的就是Container的back()函数。

2. 容量

empty：检查队列是否为空。其函数声明如下：
```
bool empty() const; // C++20 前
[[nodiscard]] bool empty() const; //C++20 起
```
其本质上就是检查Container是否为空，即Container的empty()。如果为空返回true，否则为false。
size：返回队列中的元素个数。其函数声明如如下：
```
size_type size() const;
```
同样的，其本质还是返回的是Container的元素个数，即Container的size()。

3. 队列的修改

push：向队列的尾部插入元素，对应的就是入队操作。其函数声明如下：
```
void push( const value_type& value );
void push( value_type&& value ); //C++11 起
```
emplace：在队列的尾部构造元素，对应的也是入队的操作。其函数声明如下：
```
template< class... Args >
void emplace( Args&&... args );// C++11 起  C++17 前
template< class... Args >
decltype(auto) emplace( Args&&... args );// C++17 起
```
该函数就是将新元素推到队列的尾部，其与push不同的是：该函数是原地构造元素，即不进行移动或复制操作，使用参数直接原地调用元素的构造函数，使得其效率高于push。
pop：删除队列首个元素，对应的就是出队操作。其函数声明如下：
```
void pop();
```
该函数移除队列前端的元素，等效的调用了Container的pop_front()函数。
swap：交换两个容器的内容。其函数声明如下：
```
void swap( queue& other ) noexcept(); //C++11 起
```
其本质上是交换两个Container中的内容。

用法示例

#include <iostream>
#include <queue>
using namespace std;

void showQueue(string queueName, queue<int>& q) {
    cout << "队列" << queueName << "中元素的数量, 即size() = " << q.size()
        << endl;
    if (!q.empty()) {
        cout << "此时, 队列" << queueName << "不为空,即empty() = false" << endl;
        cout << "队列首位元素，即front() =  " << q.front() << endl;
        cout << "队列首位元素，即back() =  " << q.back() << endl;
    } else {
        cout << "此时, 队列" << queueName << "为空,即empty() = true" << endl;
    }
}

int main() {
    queue<int> q;

    // push()
    q.push(1);
    q.push(2);
    q.push(3);

    cout << "---按顺push元素1、2、3后:\n" << endl;
    showQueue("q", q);

    q.pop();  // 弹出队头元素
    cout << "\n---弹出队头元素3, 即pop()后:\n" << endl;
    showQueue("q", q);

    q.pop();
    cout << "\n---弹出队头元素2, 即pop()后:\n" << endl;
    showQueue("q", q);

    q.pop();
    cout << "\n---弹出队头元素1, 即pop()后:\n" << endl;
    showQueue("q", q);

    queue<int> q1;
    q1.emplace(1);
    q1.emplace(2);
    q1.emplace(3);

    cout << "\n-----------队列q和q1交换前----------" << endl;
    cout << "\nq的状态: " << endl;
    showQueue("q", q);

    cout << "\nq1的状态: " << endl;
    showQueue("q1", q1);

    q1.swap(q);  // s和s1进行交换

    cout << "\n-----------队列q和q1交换后----------\n" << endl;
    showQueue("q", q);

    cout << "\nq1的状态: " << endl;
    showQueue("q1", q1);

    return 0;
}

输出结果：

---按顺push元素1、2、3后:

队列q中元素的数量, 即size() = 3
此时, 队列q不为空,即empty() = false
队列首位元素，即front() =  1
队列首位元素，即back() =  3

---弹出队头元素3, 即pop()后:

队列q中元素的数量, 即size() = 2
此时, 队列q不为空,即empty() = false
队列首位元素，即front() =  2
队列首位元素，即back() =  3

---弹出队头元素2, 即pop()后:

队列q中元素的数量, 即size() = 1
此时, 队列q不为空,即empty() = false
队列首位元素，即front() =  3
队列首位元素，即back() =  3

---弹出队头元素1, 即pop()后:

队列q中元素的数量, 即size() = 0
此时, 队列q为空,即empty() = true

-----------队列q和q1交换前----------

q的状态: 
队列q中元素的数量, 即size() = 0
此时, 队列q为空,即empty() = true

q1的状态: 
队列q1中元素的数量, 即size() = 3
此时, 队列q1不为空,即empty() = false
队列首位元素，即front() =  1
队列首位元素，即back() =  3

-----------队列q和q1交换后----------

队列q中元素的数量, 即size() = 3
此时, 队列q不为空,即empty() = false
队列首位元素，即front() =  1
队列首位元素，即back() =  3

q1的状态: 
队列q1中元素的数量, 即size() = 0
此时, 队列q1为空,即empty() = true

原文来自：iDoitnow