C++中的Deque内部工作原理是什么

先决条件： C++中的Deque

Deque或双端队列是队列数据结构的通用版本，允许在两端插入和删除。它支持在O(1)时间复杂度内访问元素，从前面和后面插入和删除元素的时间复杂度都是O(1)。

Deque的实际应用

Deque的从两端插入和删除的能力使其成为STL中最有用的容器之一。以下是实际应用：

既可以作为堆栈又可以作为队列，因为它支持这两种操作。
存储网页浏览器的历史记录。
存储软件应用程序的撤消操作列表。
作业调度算法

C++ STL中的Deque内部工作原理

STL的deque是使用数据数组或指向内存块的指针数组而不是链接列表来实现的。根据存储要求，指针数组的块数和大小会动态波动。这些内存块包含相邻位置的项目。

当创建Deque对象时，会自动分配一块内存以便对象可以存储在相邻位置。

1. 当我们在其前面放置一个项时，Deque然后会分配一个新的内存块并将其与前一个内存块连接起来。现在，如果我们再次向前添加元素，它们将被存储在此新内存块中，直到该内存块完全填满。 
2. 将一个项插入Deque的末尾时，分配的内存块将其保持直到完全填满；如果发生这种情况，则新分配一个内存块并将其连接到上一个块的末尾。现在，将添加到Deque的后面的元素存储在该新的内存块中。

由于Deque不需要像数组一样在内存块中将一个元素向前移动一位以便腾出空间，因此可以把它看作是一个向量的链接列表。为了向它分配一个新的内存块，它首先确定是否在当前内存块的第一个元素的前面还有剩余空间。

时间复杂度：

访问元素- O(1)
插入或删除元素- O(N)
插入或删除元素在开始或结束时- O(1)

例子：

// C++代码演示deque的工作原理
#include <deque>
#include <iostream>
using namespace std;
  
// 驱动程序
int main()
{
    deque<int> d = { 1, 2, 3 };
  
    d.push_back(4);
    d.push_front(0);
  
    cout << "Deque中的元素：" << endl;
  
    for (int i : d)
        cout << i << " ";
    cout << endl;
  
    d.pop_back();
  
    cout << "\n"
         << "pop_back()后Deque中的元素：" << endl;
  
    for (int i : d)
        cout << i << " ";
    cout << endl;
  
    cout << "\n"
         << "pop_front()后Deque中的元素：" << endl;
  
    d.pop_front();
  
    for (int i : d)
        cout << i << " ";
    cout << endl;
  
    cout << "\n"
         << "Deque中的第一个元素：" << d.front()
         << endl;
    cout << "Deque中的最后一个元素：" << d.back()
         << endl;
  
    cout << "Deque中1号下标的元素：" << d.at(1) << endl;
  
    cout << "Deque的大小：" << d.size() << endl;
    cout << "Deque是否为空：" << d.empty() << endl;
  
    cout << "\n"
         << "删除了Deque中的所有元素后："
         << "\n\n";
  
    d.erase(d.begin(), d.end());
  
    cout << "Deque的大小：" << d.size() << endl;
    cout << "Deque是否为空：" << d.empty() << endl;
}

输出

Deque中的元素： 
0 1 2 3 4 

pop_back()后Deque中的元素： 
0 1 2 3 

pop_front()后Deque中的元素： 
1 2 3 

Deque中的第一个元素：1
Deque中的最后一个元素：3
Deque中1号下标的元素：2
Deque的大小：3
Deque是否为空：0

删除了Deque中的所有元素后：

Deque的大小：0
Deque是否为空：1