C++基础：STL之双向队列deque

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

双向队列deque

双向队列也是队列，是最为常见的一种数据结构，双向队列在STL中有deque的实现。包含双向队列在内，队列中的元素满足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) begin() 查询遍历 获取指向第一个元素的迭代器 O(1) end() 查询遍历 获取指向最后一个元素的迭代器 O(1) front() 查询遍历 获取指向第一个元素的迭代器 O(1) back() 查询遍历 获取指向最后已给元素的迭代器 O(1) push_back 插入 在末尾插入数据x O(1) pop_back 删除 删除最后一个元素 O(1) push_front 插入 在末尾插入数据x O(1) pop_front 删除 删除最后一个元素 O(1) empty 删除 删除所有元素 O(n)

注：deque的成员函数主要包括插入和删除，实际对应着队列操作的入队和出队两个操作，然后就是获取元素个数和对头元素的操作，都是负载度为O (1)的操作。和stack相比，上述5个函数的函数名只是front和top有区别，其他函数名一致。

代码使用示例

#include#includeusing namespace std;

void print_element(dequeq) {
    if (!q.empty()) {
        cout << "Size:" << q.size() << " Queue Top Element : " << q.back()  << " Queue:";
    } else {
        cout << "Size:" << q.size() << endl;
    }

    deque::iterator it = q.begin();
    while(it != q.end()) cout << *it++;
    cout << endl;
}

int main() {
    dequeq;

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

    cout << endl << "Queue Element Out " << endl;
    q.pop_back();
    print_element(q);
    q.pop_back();
    print_element(q);
    q.clear();
    print_element(q);

    q.push_back('i');
    print_element(q);
    q.push_front('L');
    print_element(q);
    q.push_back('u');
    print_element(q);
    q.pop_back();
    print_element(q);
    q.pop_front();
    print_element(q);
    q.pop_front();
    print_element(q);
}

示例执行结果

Queue Element In 
Size:0

Size:1 Queue Top Element : L Queue:L
Size:2 Queue Top Element : i Queue:Li
Size:3 Queue Top Element : u Queue:Liu

Queue Element Out 
Size:2 Queue Top Element : i Queue:Li
Size:1 Queue Top Element : L Queue:L
Size:0

Size:1 Queue Top Element : i Queue:i
Size:2 Queue Top Element : i Queue:Li
Size:3 Queue Top Element : u Queue:Liu
Size:2 Queue Top Element : i Queue:Li
Size:1 Queue Top Element : i Queue:i
Size:0

总结

变长支持、泛化类型、常用功能函数内嵌、可以使用其他多种STL的函数、使用简单，而且也支持迭代器等，都是deque被使用的原因。