如何在C++中迭代STL队列

队列是一种遵循特定顺序执行操作的线性结构。该顺序是先进先出（FIFO）。

语法：

queue<datatype> queuename;

数据类型： 队列可以根据值接受任何数据类型，例如int、char、float等。

std: :queue 容器没有提供从中我们可以使用迭代器在队列上迭代的 std: :begin 函数和 std: :end 函数。简单地说，不能迭代 std: :queue 。

有3种方法可以迭代队列，即：

1. 使用标准 std: :front 和 std: :pop 方法
2. 创建给定std: :queue的副本
3. 使用std: :deque

1. 使用标准 std : : front 和 std : : pop 方法

我们可以使用 std: :front 进行队列迭代，它将返回队列的前一个元素，而 std: :pop 将删除队列的前一个元素。但是，使用此方法迭代队列后，队列将消失，因为我们在迭代过程中删除队列元素。

例如：

// C++ program to iterate a STL Queue
// using standard std : : front and
// std : : pop method
#include <iostream>
#include <queue>
using namespace std;
int main()
{
    // creating std :: queue in c++
    queue<int> q;
   
    // inserting elements in queue
    // using std :: push method
    q.push(1);
    q.push(2);
    q.push(3);
    q.push(4);
    q.push(5);
 
    cout << "Elements of queue are : \n";
    while (!q.empty()) {
       
        // getting front element of queue
        cout << q.front() << " ";
       
        // removing front element of queue
        q.pop();
    }
 
    return 0;
}  

输出

Elements of queue are : 
1 2 3 4 5 

2. 创建给定std : : queue的副本

如果我们想在 std: :queue 上进行迭代，那么可以创建一个临时副本队列，并将队列的所有元素复制到副本队列中，然后可以轻松遍历复制队列并使用 std: :front() 函数查找队列的元素并使用 std: :pop 函数从队列中删除元素。

例如：

// C++ program to iterate a STL Queue
// by Creating copy of given
// std : : queue
#include <iostream>
#include <queue>
using namespace std;
int main()
{
    // creating std :: queue in c++
    queue<int> q;

    // pushing elements using std :: push()
    q.push(1);
    q.push(2);
    q.push(3);
    q.push(4);
    q.push(5);
 
    // creating copy queue to
    // copy all elements of queue
    queue<int> copy_queue = q;
 
    cout << "Elements of queue are :\n";
 
    // traversing on copyqueue
    // until it becomes empty
    while (!copy_queue.empty()) {
 
        // printing front element of queue
        cout << copy_queue.front() << " ";
 
        // deleting element from
        // queue using std :: pop()
        // function
        copy_queue.pop();
    }
 
    return 0;
}  

输出

Elements of queue are :
1 2 3 4 5 

3. 使用std : : deque

在上述方法中，需要额外的复制队列以先复制队列的所有元素，这种方法不是空间高效的方法。使用std::：dequeue，我们可以使用高效的空间迭代，这提供了所有的标准操作，其中包括 std: :queue 。我们可以使用for循环遍历dequeue。

我们可以使用 dequeue: :cbegin() 和 dequeue: :cend() 按正向顺序打印dequeue， dequeue: :crbegin() 和 dequeue: :crend() 按反向顺序打印dequeue。

示例:

//使用std：：dequeue迭代STL队列的C++程序
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int main()
{
    deque<int> dq;
    dq.push_back(1);
    dq.push_back(2);
    dq.push_back(3);
    dq.push_back(4);
    dq.push_back(5);

    cout << "正向打印dequeue：\n";
    for(auto it = dq.cbegin();it!=dq.cend();it++)
    {
        cout << *it << " ";
    }

    cout << "\n";

    cout << "反向打印dequeue：\n";
    for(auto it = dq.crbegin();it!=dq.crend();it++)
    {
        cout << *it << " ";
    } 
    return 0;
}  

输出结果

正向打印dequeue：
1 2 3 4 5
反向打印dequeue：
5 4 3 2 1

时间复杂度： O(n) // n为队列的大小。

辅助空间： O(n)。