Queue

STL queue 简介

STL 的 queue 是一种容器适配器。这意味着 它本身并不是一个全新的数据结构，而是在现有容器的基础上，通过限制其接口，使其表现出队列（Queue）这种特定的行为。

queue 的核心特性是先进先出（FIFO，First-In, First-Out）。这意味着元素从队列的**尾部（back）加入（入队，enqueue），然后从队列的头部（front）**移除（出队，dequeue）。就像排队一样，先来的人先离开。

关于 queue 的实现方式：

• 默认情况下，STL 的 queue 是基于 deque（双端队列）容器来实现的。deque 是一种允许在两端进行高效插入和删除操作的数据结构，这非常适合实现队列的 FIFO 特性。
• 用户也可以选择使用 list（链表）作为 queue 的底层实现容器。您可以通过在声明 queue 时指定第二个模板参数来做到这一点，例如 std::queue<int, std::list<int>> q2;。
• 值得注意的是，尝试使用 vector 作为 queue 的底层容器会导致编译错误。这是因为 queue 的 pop() 操作在默认情况下会调用底层容器的 pop_front() 方法，而 std::vector 并没有提供 pop_front() 成员函数。

简单来说，STL 的 queue 提供了一种方便使用队列数据结构的接口。它默认使用 deque 来高效地实现队列的操作（在尾部插入，在头部移除），同时也允许用户根据需要选择使用 list 作为底层实现。

queue 的操作 push（入队）在 STL 中对应 push() 函数，将元素插入到队列的尾部。出队操作（dequeue）则通过先调用 front() 函数获取队首元素，然后再调用 pop() 函数移除队首元素来实现。queue 还提供了一些其他的常用函数，例如 empty()（检查队列是否为空）和 size()（获取队列中元素的个数）。

STL queue 常用成员函数

queue 演示程序 (使用 list作为容器)

#include <iostream>
#include <queue>
#include <list>

using namespace std;

int main() {
    queue<int> q1;
    queue<int, list<int> > q2; // 注意 >> 之间留有空格

    q1.push(1);
    q1.push(2);
    q1.push(3);

    q2.push(4);
    q2.push(5);
    q2.push(6);

    q1.push(q2.back());

    cout << "q1 的元素: ";
    while (!q1.empty()) {
        cout << q1.front() << ' '; // 输出队首元素
        q1.pop();                  // 移除队首元素
    }
    cout << endl; // 输出: q1 的元素: 1 2 3 6

    cout << "q2 的元素: ";
    while (!q2.empty()) {
        cout << q2.front() << ' '; // 输出队首元素
        q2.pop();                  // 移除队首元素
    }
    cout << endl; // 输出: q2 的元素: 4 5 6

    return 0;
}

程序说明:

• 程序首先包含了必要的头文件 <iostream>，<queue> 和 <list>。
• 创建了两个 queue 对象 q1 和 q2。q1 使用默认的底层容器（deque），q2 则显式地指定使用 list 作为底层容器。
• 使用 push() 函数向 q1 依次插入了整数 1、2 和 3。
• 使用 push() 函数向 q2 依次插入了整数 4、5 和 6。
• 通过 q2.back() 获取 q2 的队尾元素 (6)，并使用 push() 将其插入到 q1 的队尾。
• 两个 while 循环分别遍历 q1 和 q2。在循环中，!q1.empty() 和 !q2.empty() 用于检查队列是否为空。
• q1.front() 和 q2.front() 用于获取当前队首元素并输出。
• q1.pop() 和 q2.pop() 用于移除当前队首元素。

这段代码演示了 push（入队）、front（获取队首）、back（获取队尾）、pop（出队）和 empty（判空）等 queue 的常用成员函数的使用。同时也展示了如何指定 queue 的底层容器。

queue 演示程序 (使用默认的 deque作为默认容器)

这里有一个使用默认的 deque 作为默认容器的 std::queue 的演示程序。这个程序与下面的示例非常相似，但重点在于第一个 queue 对象的声明方式，它没有显式指定底层容器，因此会使用默认的 deque。

#include <iostream>
#include <queue>

using namespace std;

int main() {
    // 声明一个 queue 对象 q1，它将默认使用 deque 作为底层容器
    queue<int> q1;

    q1.push(10);
    q1.push(20);
    q1.push(30);

    cout << "q1 的元素 (默认 deque): ";
    while (!q1.empty()) {
        cout << q1.front() << ' ';
        q1.pop();
    }
    cout << endl;

    // 你也可以显式地声明使用 deque，效果是一样的
    queue<string, deque<string>> q2;
    q2.push("apple");
    q2.push("banana");

    cout << "q2 的元素 (显式 deque): ";
    while (!q2.empty()) {
        cout << q2.front() << ' ';
        q2.pop();
    }
    cout << endl;

    return 0;
}

程序说明:

• 第一个 queue 对象 q1 被声明为 queue<int> q1;。在这种声明方式中，我们没有指定 queue 的第二个模板参数，即底层容器的类型。根据 STL 的定义和源文件 的说明，std::queue 在这种情况下会默认使用 std::deque 作为其底层实现。
• 我们向 q1 中压入了一些整数，然后通过循环和 front() 及 pop() 成员函数遍历并输出了队列中的元素，这展示了标准的 FIFO 行为。
• 第二个 queue 对象 q2 被声明为 queue<string, deque<string>> q2;。这里我们显式地指定了 deque<string> 作为 q2 的底层容器。虽然这里是显式指定，但它与第一个 q1 的默认行为是相同的。
• 我们对 q2 进行了类似的操作，证明了即使显式指定，deque 也能很好地支持 queue 的操作。

总结:

这个程序清晰地展示了：

• 当声明 std::queue 时不指定第二个模板参数时（例如 queue<int> q1;），STL 会自动使用 std::deque 作为其默认的底层容器。
• 使用默认 deque 的 queue 对象 (q1) 和显式使用 deque 的 queue 对象 (q2) 在功能上是相同的，都遵循队列的 FIFO 原则。

因此，如果您只是声明 std::queue 而不指定底层容器，您就已经在使用以默认 deque 实现的队列了。