C++基础-STL deque（双端队列）

deque 双端队列

1、特性：

在内存中不占有一块连续的空间，介于向量和列表之间，更接近向量，适用于从两端存取数据，可以使用[ ]直接存储数据。

2、适用情况：

可提供快速的元素存取，在序列中插入、删除速度较慢。

3、头文件

#include<deque>

4、复杂度

插入：push_front()，O(1)；push_back()，O(1)；insert()，O(N) 删除：pop_front()，O(1)；pop_back()，O(1)；erase()，O(N) 查找：O(1)

5、定义及初始化、常用函数

deque<int> d(10);
    d.push_front(1);//在容器前端添加元素
    d.push_back(2);//在后端添加元素
    d.pop_front();//前端删除
    d.pop_back();//后端删除
    d.insert(d.end(),3);//在尾部插入元素3
    d.erase(d.begin());//删除元素
    d.clear();//清除所有元素
    d.front();//返回前端元素的引用
    d.back();//返回末端元素的引用
    d.rbegin();//返回前端倒转迭代器
    d.max_size();//返回可存储的最大个数
    d.size();//返回当前元素个数
    d.empty();//为空返回true
    d.at(1);//返回第一个元素的引用
    deque<int> x;
    d.swap(x);//与容器x互换元素
    int m=d[1];//取出对应下标的元素

6、获取元素

[ 下标]获取 迭代器遍历

for(deque<int>:: iterator it=d.begin();it!=d.end();it++)
    {
          
   
        cout<<*it<<endl;
    }

7、例题

描述 请设计一个排队程序，用户有普通客人和 VIP 客人之分，VIP 客人不排队（即 VIP 客人在队列头部），请将已有的guest1和guest2放入队列中（guest1排在guest2前），并将VIP客人新增至队列头部。 输入描述： 无 输出描述： VIP客人姓名 guest1姓名 guest2姓名（每个客人的名字用空格隔开）

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

class Guest {
          
   
public:
    string name;
    bool vip;

    Guest(string name, bool vip) {
          
   
        this->name = name;
        this->vip = vip;
    }
};

int main() {
          
   

    Guest guest1("张三", false);
    Guest guest2("李四", false);
    Guest vipGuest("王五", true);
    deque<Guest> deque;

    // write your code here......
    deque.push_front(vipGuest);
    deque.push_back(guest1);
    deque.push_back(guest2);

    for (Guest g : deque) {
          
   
        cout << g.name << " ";
    }

    return 0;
}