admin管理员组

文章数量:1794759

数据结构之deque双端队列

一、概念：

众所周知，数据结构是用来存储数据，deque也不例外，他是集结了队列和栈的性质而成的结构，他几乎拥有所有数据结构能有的操作，看似已经大杀四方，可实际情况如何呢，那就带者这个疑问继续学习。

预备知识：

在学习deque这个容器之前，我们先要回顾以下vector和list这两大容器的优缺点：

vector优缺点：

优点：

  1. 下标随机访问
  2. 缓存命中率高（物理结构连续存储的优势）

缺点：

  1. 前面部分插入删除效率低
  2. 扩容有消耗

list优缺点:

优点：

  1. 任意位置插入删除效率高
  2. 按需申请释放

缺点：

  1. 不支持下标随机访问
  2. 缓存命中率低

deque的底层逻辑

在明白前面的知识后，接下来我们就来了解deque的底层实现。

下面这张图就是deque的基本实现方法

首先deque多了一个叫做中控数组的东西，本质上是存储一段一段空间的指针数组。

而在deque里面存储数据的并不是一长串连续的空间，而是一段一段的空间。

因此，我们在简单了解deque的基本实现后，我们不难发现deque有以下的优缺点。

优点：

头插、头删、尾插、尾删效率很不错。

不足：（自相矛盾）

如果随机访问，如何计算？

比如访问第i个值，在假设每个buff一样大的情况下（都是10），比较容易计算。

在第i/10个buff中；在这个buff的第i%10的位置。

我们又会遇到下面的实际场景：中间插入删除如何实现呢？

如果要保持每个buff一样大，只能挪动数据（效率低）

如果不需要保持每个buff一样大，可以对当前的buff直接扩容或者挪动数据（效率较低）

综述，在遇上前面两种不同的状况下，想要都实现效率低，是不可能的，即所谓鱼和熊掌不可兼得。 

总结：

  1. 下标随机访问，效率不错，但是跟vector有差距
  2. 中间插入删除，效率差
  3. 头插、头删、尾插、尾删效率很不错。

所以在容器适配的选择上，什么情况选择deque呢，在头插、头删、尾插、尾删比较多的情况下，可以选择deque。

如果有大量的下标访问，就用vector，如果有大量的中间位置的插入删除，就用list

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2024-08-02，如有侵权请联系 cloudcommunity@tencent 删除队列数据效率存储数据结构

本文标签： 数据结构之deque双端队列

版权声明：本文标题：数据结构之deque双端队列 内容由林淑君副主任自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.xiehuijuan.com/baike/1754808946a1706717.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。