c++ - 为什么要分配一个比请求大小大 1 的数组？

Question

这真的很有趣，因为我们的老师昨天教我们这个，他自己也搞不懂。因此，我们有点悬而未决，不知道真正的原因。

下面是一本名著中的Queue的数组实现(我没有，但我的导师是这么说的，作者很有名气):

class QUEUE {
private:
    int* q;
    int N;
    int head;
    int tail;
public:
    QUEUE(int maxN) {
        q = new int[maxN + 1];
        N = maxN + 1; head = N; tail = 0;
    }
    int empty() const {
        return head % N == tail;
    }
    void put(int item) {
        q[tail++] = item; tail = tail % N;
    }
    int get() {
        head = head % N; return q[head++];
    }
};

在构造函数中，您会看到 q = new int[maxN + 1];。但为什么是 '+ 1' ？他为什么要分配一个额外的 int 内存块？

Answer 1

maxN加1解决的问题是，如果你恰好分配了maxN项，你将无法区分这两种情况:

• 队列为空，并且
• 队列正好有 maxN 个项目。

在这两种情况下，head 和 tail 将彼此相等，取模 N。

注意:实现并不理想，因为插入第 maxN+1 个元素将队列环绕起来，所以它又变空了。这个缺点可以通过三种方式解决:

• 队列溢出时抛出异常，
• 将返回类型更改为bool，忽略溢出队列的插入，如果插入被忽略则返回false，或者
• 默默地忽略溢出队列的插入(不推荐)。