【2019统考真题】请设计一个队列，要求满足:①初始时队列为空;②入队时，允许增加队列占用空间;③出队后，出队元素所占用的空间可重复使用，即整个队列所占用的空间只增不减;④入队操作和出队操作的时间复杂度始终保持为 O ( 1 ) 用C++写这个程序

要设计一个满足上述条件的队列，我们可以使用一种称为“动态数组”或“数组池”的数据结构。这种队列通过预先分配一段大内存，每次出队时将元素从当前数组移到下一个可用位置，而不是销毁元素。这样可以保持空间大小不变或者稍有增长，同时保证插入和删除操作的时间复杂度都是O(1)。

下面是一个简单的C++实现：

#include <vector>

template<typename T>
class DynamicQueue {
private:
    std::vector<T> pool;
    size_t head = 0;
    size_t tail = 0;

public:
    // 初始化队列为0长度
    DynamicQueue() {}

    // 入队操作
    void enqueue(T value) {
        if (head == tail) {
            // 扩容一倍
            pool.resize(pool.size() * 2);
        }
        pool[tail++] = value;
    }

    // 出队操作
    T dequeue() {
        if (head == tail) {
            throw std::out_of_range("Queue is empty");
        }
        T result = pool[head];
        pool[head++] = T(); // 将空值放回队尾，准备下次复用
        return result;
    }

    // 检查队列是否为空
    bool isEmpty() const {
        return head == tail;
    }
};

在这个实现中，`enqueue`方法检查队列尾部是否已满，如果满则扩容；然后直接将新元素添加到尾部。`dequeue`方法返回并移除头部元素，并将一个空值放入原头的位置以便下一次复用。队列为空时，尝试出队会抛出异常。