c++deque底层实现：用类来模拟实现stack/queue

Deque（双端队列）是C++标准库中的一种容器，它允许在两端进行高效的插入和删除操作。Deque的底层实现通常是通过一个动态数组，被分割成多个块（chunks）来实现的。

下面是一个简化的示例，用类来模拟实现一个基本的双端队列，同时展示如何用这个类来实现栈和队列。

#include <iostream>
#include <vector>

template <typename T>
class MyDeque {
private:
    std::vector<std::vector<T>> chunks;  // 用于存储数据的块
    size_t chunkSize;                    // 每个块的大小

public:
    MyDeque(size_t chunkSize) : chunkSize(chunkSize) {}

    // 在队列头部插入元素
    void pushFront(const T& value) {
        if (chunks.empty() || chunks.front().size() == chunkSize) {
            chunks.insert(chunks.begin(), std::vector<T>());
        }
        chunks.front().insert(chunks.front().begin(), value);
    }

    // 在队列尾部插入元素
    void pushBack(const T& value) {
        if (chunks.empty() || chunks.back().size() == chunkSize) {
            chunks.push_back(std::vector<T>());
        }
        chunks.back().push_back(value);
    }

    // 从队列头部弹出元素
    T popFront() {
        if (chunks.empty() || chunks.front().empty()) {
            throw std::out_of_range("Deque is empty");
        }
        T value = chunks.front().front();
        chunks.front().erase(chunks.front().begin());
        if (chunks.front().empty()) {
            chunks.erase(chunks.begin());
        }
        return value;
    }

    // 从队列尾部弹出元素
    T popBack() {
        if (chunks.empty() || chunks.back().empty()) {
            throw std::out_of_range("Deque is empty");
        }
        T value = chunks.back().back();
        chunks.back().pop_back();
        if (chunks.back().empty()) {
            chunks.pop_back();
        }
        return value;
    }

    // 获取队列头部元素
    T front() const {
        if (chunks.empty() || chunks.front().empty()) {
            throw std::out_of_range("Deque is empty");
        }
        return chunks.front().front();
    }

    // 获取队列尾部元素
    T back() const {
        if (chunks.empty() || chunks.back().empty()) {
            throw std::out_of_range("Deque is empty");
        }
        return chunks.back().back();
    }

    // 检查队列是否为空
    bool empty() const {
        return chunks.empty() || (chunks.size() == 1 && chunks.front().empty());
    }

    // 获取队列的大小
    size_t size() const {
        size_t totalSize = 0;
        for (const auto& chunk : chunks) {
            totalSize += chunk.size();
        }
        return totalSize;
    }
};

// 使用MyDeque实现栈
template <typename T>
using MyStack = MyDeque<T>;

// 使用MyDeque实现队列
template <typename T>
using MyQueue = MyDeque<T>;

int main() {
    // 示例：使用MyStack
    MyStack<int> myStack(3);
    myStack.pushBack(1);
    myStack.pushBack(2);
    myStack.pushBack(3);
    std::cout << "Top element of MyStack: " << myStack.back() << std::endl;

    // 示例：使用MyQueue
    MyQueue<char> myQueue(2);
    myQueue.pushBack('A');
    myQueue.pushBack('B');
    myQueue.pushBack('C');
    std::cout << "Front element of MyQueue: " << myQueue.front() << std::endl;

    return 0;
}

这个示例中，MyDeque 类模拟了双端队列的基本功能，并通过使用不同的插入和删除操作实现了栈和队列的功能。使用 MyStack 和 MyQueue 类型别名，可以方便地创建基于 MyDeque 的栈和队列。