Deque(二级动态数组)

#include <iostream>
#include <stdexcept>
#include <memory>
#include <algorithm>

namespace XD {

    template <typename T>
    class Deque {
    private:
        static const size_t BLOCK_SIZE = 4;  // 每个块的大小，可以根据需要调整
        size_t frontIndex, backIndex;        // 队列的前后指针
        size_t blockCount;                   // 块的数量
        T** blocks;                          // 存储指向块的指针数组
        size_t size;                         // 队列中元素的数量

        void allocateBlock() {
            T** newBlocks = new T * [blockCount + 1];
            for (size_t i = 0; i < blockCount; ++i) {
                newBlocks[i] = blocks[i];
            }
            newBlocks[blockCount] = new T[BLOCK_SIZE];  // 新分配一个块
            blocks = newBlocks;
            ++blockCount;
        }

    public:
        Deque() : frontIndex(BLOCK_SIZE / 2), backIndex(BLOCK_SIZE / 2), blockCount(1), size(0) {
            blocks = new T * [blockCount];
            blocks[0] = new T[BLOCK_SIZE];  // 初始化第一个块
        }

        ~Deque() {
            for (size_t i = 0; i < blockCount; ++i) {
                delete[] blocks[i];
            }
            delete[] blocks;
        }

        size_t getSize() const {
            return size;
        }

        bool isEmpty() const {
            return size == 0;
        }

        void pushFront(const T& value) {
            if (frontIndex == 0) {
                allocateBlock();  // 如果头部已经没有空间，则分配新块
                frontIndex = BLOCK_SIZE - 1;
            }
            else {
                --frontIndex;
            }
            blocks[frontIndex / BLOCK_SIZE][frontIndex % BLOCK_SIZE] = value;
            ++size;
        }

        void pushBack(const T& value) {
            if (backIndex == BLOCK_SIZE) {
                allocateBlock();  // 如果尾部已经没有空间，则分配新块
                backIndex = 0;
            }
            blocks[backIndex / BLOCK_SIZE][backIndex % BLOCK_SIZE] = value;
            ++backIndex;
            ++size;
        }

        void popFront() {
            if (isEmpty()) {
                throw std::out_of_range("Deque is empty");
            }
            if (frontIndex == BLOCK_SIZE - 1) {
                frontIndex = 0;
            }
            else {
                ++frontIndex;
            }
            --size;
        }

        void popBack() {
            if (isEmpty()) {
                throw std::out_of_range("Deque is empty");
            }
            if (backIndex == 0) {
                backIndex = BLOCK_SIZE - 1;
            }
            else {
                --backIndex;
            }
            --size;
        }

        T& front() {
            if (isEmpty()) {
                throw std::out_of_range("Deque is empty");
            }
            return blocks[frontIndex / BLOCK_SIZE][frontIndex % BLOCK_SIZE];
        }

        T& back() {
            if (isEmpty()) {
                throw std::out_of_range("Deque is empty");
            }
            size_t index = (backIndex == 0) ? BLOCK_SIZE - 1 : backIndex - 1;
            return blocks[index / BLOCK_SIZE][index % BLOCK_SIZE];
        }

        T& operator[](size_t index) {
            if (index >= size) {
                throw std::out_of_range("Index out of range");
            }
            size_t blockIndex = (frontIndex + index) / BLOCK_SIZE;
            size_t elementIndex = (frontIndex + index) % BLOCK_SIZE;
            return blocks[blockIndex][elementIndex];
        }
    };

}

实现了简易的deque, 如果为了访问更快, 应该记录数组相应的属性