6

This is really interesting because our instructor was teaching this to us yesterday and he couldn't figure it out himself. So, we're kinda left hanging on this without knowing the actual reason why.

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

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 the '+ 1' ? Why is he allocating one extra int block of memory?

Kane Williamson
  • 127
  • 4

1 Answers1

6

The problem that adding one to maxN solves is that if you allocate exactly maxN items, you would not be able to distinguish these two situations:

  • The queue is empty, and
  • The queue has exactly maxN items.

In both these situations head and tail would be equal to each other modulo N.

Note: the implementation is not ideal, because inserting maxN+1-th element wraps the queue around, so it becomes empty again. This shortcoming can be addressed in three ways:

  • Throw an exception when queue overflows,
  • Change return type to bool, ignore insertions that overflow the queue, and return false if an insertion is ignored, or
  • Silently ignore insertions that overflow the queue (not recommended).
Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523
  • can be done this way, is however not what above implementation does imo: http://ideone.com/LWsmZi After x: (x%n+1==0) inserts, empty() will return true. The insertion policy is also very strange because it will overwrite from the front without adjusting head if more than N elements are inserted. So its drop-strategy is kind of random. – midor Mar 27 '15 at 16:47
  • Ok, so if you follow this author's implementation, how would you check if the queue is full? I know how on my implementation but here, I'm not too sure. – Kane Williamson Mar 27 '15 at 16:54
  • @KaneWilliamson Like this: `bool full() const { return ((head+1) % N == tail);}` – Sergey Kalinichenko Mar 27 '15 at 16:56
  • If you don't mind, can you please give a very brief description of what the code is doing please? I want to check if my understanding is correct. I personally think he's setting head to the very last element initially and tail to zero. If there is a put(), he adds to the tail and increments it for the next put to be placed. **However, when he uses get(), instead of decrementing the head, he once again increments it, this is what puzzles me...** – Kane Williamson Mar 27 '15 at 17:00
  • @dasblinkenlight: Sure, but there is still this one little doubt that I posed in my comment above. – Kane Williamson Mar 27 '15 at 17:01
  • If I were to print the queue in order of insertion, it would be starting from tail to head, correct? So, if there is a put(), we add an item, so he increments the tail index, i get that. **But, when there is a pop(), I mean get(), the last element is removed and therefore the index that marks the last element, which is head here needs to be decremented. But the author increments it again. Why?** – Kane Williamson Mar 27 '15 at 17:04
  • @KaneWilliamson The author is setting the tail to one past the end of the array so that `head % N == tail` be `true` after initialization. All index operations are increments, not decrements, because both indexes in a queue need to advance in the same direction. Decrementing on `get` would make your class a stack (and `get` would indeed become `pop`). Printing in insertion order would require iterating from `head` to `tail`, with a "wrap around" at index `N` (i.e. with a `% N` after incrementing). – Sergey Kalinichenko Mar 27 '15 at 17:10
  • My concern is about the get() method. Consider the size to be 10; According to the code, initially, the index of head = 11 and index of tail = 0. Now, add an element, say 1. So, 1 is placed in the index position 0 and the tail position is incremented to 1. Now add another say 5. 5 is at index pos 1 and the tail now is index 2. Now use the get() function, which does: return q[head++]; which is to return the element at head and then increment the head but BOOOOOM!!!!! The head is index no 11 as we have just seen and it has no value stored in it and this must be a huge error. – Kane Williamson Mar 27 '15 at 17:58
  • @KaneWilliamson `get()` does not return `q[head++]` right away. Before returning, it adjusts the head by assigning `head = head % N` to ensure that the `head` is between 0 and 10, inclusive. – Sergey Kalinichenko Mar 27 '15 at 18:39