【CPP】双端队列简介(deque)

简介：双端队列(deque)

1.概述

双端队列：是一种顺序表和顺序表的结合数据结构，不是队列。

它提供顺序表的[]下标访问和链表的中间头部的较高效率插入删除操作。

2.特点

顺序表的优缺点：

优点：支持下标随机访问

缺点：头部或者中间插入删除效率低 + 扩容有消耗

链表的优缺点：

优点：任意位置插入删除效率都不错

缺点：不支持下表随机访问

双端队列优缺点：顺序表链表都沾点边，但都不够极致。

优点：

• 既有着顺序表支持下表随机访问的功能，又有链表任意位置插入删除效率都还可以。
• 而且头插尾插效率很好。

缺点：

• 双端队列支持的下标随机访问性能上不如顺序表，双端队列的任意位置插入删除效率不如链表

3.底层原理

简化抽象图：

迭代器图：

因为deque优点是头尾插入删除效率很好，刚好与栈和队列相一致，因而常被用做栈和队列的默认容器。

EOF