Why allocate an array of size 1 larger than the required size?

Question

This is really interesting, because our instructor taught us this yesterday, and he could not understand it himself. Thus, we seemed to be hanging over this, not knowing the actual reason.

Here is the implementation of the Queue array in the famous book (which I don’t have, but what my instructor said. The author is very famous):

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++]; } }; 

Inside the constructor, you see q = new int[maxN + 1]; . But why is "+ 1"? Why does it allocate one additional block of memory?

Answer 1

The problem that adding one to maxN solves is that if you maxN exactly maxN elements, you cannot distinguish between these two situations:

• The queue is empty and
• The queue has exactly maxN elements.

In both of these situations, head and tail will be equal to each other modulo N

Note: the implementation is not perfect, since inserting the maxN+1 -th element wraps the queue around, so it becomes empty again. This disadvantage can be solved in three ways:

• Throw an exception when the queue overflows,
• Change the return type to bool , ignore inserts that overflow the queue, and return false if the insert is ignored, or
• It is quieter to ignore inserts that overflow the queue (not recommended).