Warum ein Array der Größe 1 mehr als die angeforderte Größe zuweisen?

Question

Das ist wirklich interessant, weil unser Lehrer uns das gestern beigebracht hat und er es selbst nicht herausfinden konnte. Also hängen wir irgendwie daran, ohne den tatsächlichen Grund zu kennen. Hier

ist die Array-Implementierung einer Queue in einem berühmten Buch (was ich nicht habe, aber das ist, was mein Lehrer sagte der Autor ist sehr renommiert.):

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

Innerhalb des Konstruktor , sehen Sie q = new int[maxN + 1];. Aber warum die '+ 1'? Warum reserviert er einen zusätzlichen int-Speicherblock?

Answer 1

Das Problem, das man maxN löst das Hinzufügen ist, dass, wenn Sie genau maxN Elemente zuweisen, würden Sie nicht in der Lage sein, diese zwei Situationen zu unterscheiden:

• Die Warteschlange leer ist, und
• Die Warteschlange hat genau maxN Artikel.

In diesen beiden Situationen head und tail würde zueinander Modulo N gleich sein.

Hinweis: Die Implementierung ist nicht ideal, da das Einfügen von maxN+1 -ten Element die Warteschlange umschließt, so dass es wieder leer wird. Dieser Mangel kann auf drei Arten behandelt:

• Wurf eine Ausnahme, wenn Warteschlange überläuft,
• Wechsel Rückgabe Typ bool, -insertionen ignorieren, dass die Warteschlange überläuft, und das Rück false wenn eine Insertion ignoriert wird, oder
• Insertionen ignorieren, die die Warteschlange überlaufen lassen (nicht empfohlen).