C++基础：STL之队列queue

这篇文章介绍一下STL中队列queue的基本使用方法。

队列queue

队列也是最为常见的一种数据结构，队列中的元素满足FIFO（先进先出）。主要特点如下：

• 元素需满足FIFO：First In First Out

• 出口端称为队头（Front），入口端称为队尾（Rear）

• 可以使用数组或者链表来存储数据

• 操作主要有入队（Enqueue）和出队（Dequeue）

• 可以根据需要实现循环队列或者双向队列

• 只能在队尾插入数据，在队头删除数据

• 关于队列的说明内容可参看：https://blog.csdn.net/liumiaocn/article/details/108091698

头文件和命名空间

#include using namespace std;

常用的成员函数 queue函数名 用途 功能说明 时间复杂度 size() 查询遍历 获取元素个数 O(1) front() 查询遍历 获取指向第一个元素的迭代器 O(1) push 插入 在末尾插入数据x O(1) pop 删除 删除最后一个元素 O(1) empty 遍历 判断队列是否为空 O(1)

注：queue的成员函数主要包括插入和删除，实际对应着队列操作的入队和出队两个操作，然后就是获取元素个数和对头元素的操作，都是负载度为O (1)的操作。

代码使用示例

#include#includeusing namespace std;

void print_element(queueq) {
    if (!q.empty()) {
        cout << "Size:" << q.size() << " Queue Element : [" <<  q.front() << " - "
             << q.back()  << "]" << endl;
    } else {
        cout << "Size:" << q.size() << endl;
    }
}

int main() {
    queueq;

    cout << "Queue Element In " << endl;
    print_element(q);
    q.push('L');
    print_element(q);
    q.push('i');
    print_element(q);
    q.push('u');
    print_element(q);

    cout << endl << "Queue Element Out " << endl;
    q.pop();
    print_element(q);
    q.pop();
    print_element(q);
    q.pop();
    print_element(q);
}

示例执行结果

Queue Element In 
Size:0
Size:1 Queue Element : [L - L]
Size:2 Queue Element : [L - i]
Size:3 Queue Element : [L - u]

Queue Element Out 
Size:2 Queue Element : [i - u]
Size:1 Queue Element : [u - u]
Size:0

可以看到和栈相比，一个在入队的时候front不变。

总结

变长支持、泛化类型、常用功能函数内嵌、可以使用其他多种STL的函数、使用简单等，都是queue被使用的原因，但是队列本身是一种非常简单的数据结构，在STL的实现中也有很多限制，比如没有迭代器的支持等。