C++ 容器适配器详解：Stack、Queue 与 Deque 原理

（三）deque 的内存管理方式

deqe 的内存管理方式与 vector 有所不同。它内部通常由多个连续的内存块组成，每个内存块可以存储一定数量的元素。当在 deque 的两端插入元素时，如果当前内存块已满，deque 会自动分配一个新的内存块。这种内存管理方式使得 deque 在频繁插入和删除元素时，不需要像 vector 那样频繁地重新分配整个内存空间，从而提高了性能。

五、双队列（deque）的原理介绍

（一）deque 的数据结构设计

deqe 的数据结构设计旨在实现高效的两端插入和删除操作，同时兼顾一定的随机访问性能。它通常由一个中控器（map）和多个缓冲区（buffer）组成。中控器用于管理各个缓冲区的地址，每个缓冲区则存储实际的数据元素。

（二）元素的存储与访问

当向 deque 中插入元素时，根据插入位置的不同（头部或尾部），deque 会选择合适的缓冲区进行插入操作。如果当前缓冲区已满，deque 会自动分配新的缓冲区，并更新中控器的信息。在访问元素时，deque 通过中控器找到对应的缓冲区，然后在缓冲区内进行偏移计算，以获取指定位置的元素。

（三）deque 的迭代器实现

deqe 的迭代器是一个相对复杂但功能强大的组件。它需要能够遍历 deque 中的所有元素，无论这些元素分布在哪个缓冲区中。迭代器内部维护了当前元素所在缓冲区的指针、在缓冲区中的偏移量以及中控器的相关信息。通过这些信息，迭代器可以在遍历过程中准确地在不同缓冲区之间切换。

六、deque 的缺陷

（一）内存碎片化问题

由于 deque 在内存管理上的灵活性，它可能会导致内存碎片化问题。当不断地在两端插入和删除元素时，deque 会频繁地分配和释放内存块，这些小块的内存可能会散布在内存中，形成碎片化。在一些对内存连续性要求较高的场景下，内存碎片化可能会影响程序的性能。

（二）随机访问性能相对较低

尽管 deque 支持随机访问元素，但与 vector 相比，其随机访问性能相对较低。这是因为 deque 的元素可能分布在多个不连续的缓冲区中，在进行随机访问时，需要通过中控器计算元素所在的缓冲区，然后在缓冲区内进行偏移计算。

（三）迭代器失效问题

deqe 的迭代器在某些操作后容易失效。例如，当在 deque 的中间插入或删除元素时，可能会导致部分迭代器失效，因为这些操作可能会改变缓冲区的布局和元素的存储位置。这就要求在使用 deque 的迭代器时，需要格外小心。

七、deque 为什么选择作为堆栈和队列的底层默认容器

（一）两端操作的高效性

堆栈和队列的主要操作分别是在一端进行插入和删除（堆栈在顶部，队列在一端插入，另一端删除），deque 在两端的插入和删除操作效率很高，非常符合堆栈和队列的操作特性。

（二）内存管理的优势

deqe 的内存管理方式在一定程度上平衡了内存分配和性能之间的关系。与 vector 相比，它在频繁插入和删除元素时不需要频繁地重新分配整个内存空间；与 list 相比，它在随机访问元素时虽然性能略低，但仍然具有一定的优势，并且在内存使用上相对更加紧凑。

（三）通用性和灵活性

deqe 具有较高的通用性和灵活性，它可以适应不同规模和操作频率的堆栈和队列需求。无论是处理少量元素还是大量元素，deque 都能够提供相对稳定的性能表现。

八、STL 标准库中对于堆栈和队列的模拟实现

（一）堆栈的模拟实现

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

// 模拟堆栈类
class MyStack {
private:
    vector<int> data;
public:
    // 入栈操作
    void push(int value) {
        data.push_back(value);
    }
    
    // 出栈操作
    void pop() {
        if (!empty()) {
            data.pop_back();
        } else {
            cerr << "堆栈为空，无法出栈！" << endl;
        }
    }
    
    // 获取栈顶元素
    int top() const {
        if (!empty()) {
            return data.back();
        } else {
            cerr << "堆栈为空，无法获取栈顶元素！" << endl;
            return -1;
        }
    }
    
    // 判断堆栈是否为空
    bool empty() const {
        return data.empty();
    }
};

int main() {
    MyStack stack;
    stack.push(1);
    stack.push(2);
    stack.push(3);
    cout << "栈顶元素：" << stack.top() << endl;
    stack.pop();
    cout << "栈顶元素：" << stack.top() << endl;
    return 0;
}

（二）队列的模拟实现

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

// 模拟队列类
class MyQueue {
private:
    list<int> data;
public:
    // 入队操作
    void push(int value) {
        data.push_back(value);
    }
    
    // 出队操作
    void pop() {
        if (!empty()) {
            data.pop_front();
        } else {
            cerr << "队列为空，无法出队！" << endl;
        }
    }
    
    // 获取队首元素
    int front() const {
        if (!empty()) {
            return data.front();
        } else {
            cerr << "队列为空，无法获取队首元素！" << endl;
            return -1;
        }
    }
    
    // 判断队列是否为空
    bool empty() const {
        return data.empty();
    }
};

int main() {
    MyQueue queue;
    queue.push(1);
    queue.push(2);
    queue.push(3);
    cout << "队首元素：" << queue.front() << endl;
    queue.pop();
    cout << "队首元素：" << queue.front() << endl;
    return 0;
}

九、总结

容器适配器在 C++ 编程中是非常重要的概念，理解它们的原理、底层结构以及模拟实现方式，有助于我们更好地运用 STL 中的堆栈和队列等数据结构，提高程序的效率和质量。