You are here:

C++/FIFO queue array implementation


I have an assignment to modify a code from my text. This is probably painfully simple, but I'm too overtired to grasp the concept.

Provided code:

template <class Item>
class QUEUE
  Item *q; int N; head, tail;
  QUEUE(int maxN){
     q = new Item[maxN +1];
     N = maxN+1; head = N; tail = 0;}

  int empty() const {
     return head % N == tail;}

  void put(Item item) {
     q[tail++] = item; tail = tail % N;}

  Item get() {
     {head = head % N; return q[head++];}

I need to change the get() to do nothing if the queue is empty [head == tail] and do nothing with the put() if the queue is full [if put() makes head == tail].

The part I don't understand is the significance of the % operator. 170 pages into the book and it suddenly shows up with no explanation. I'm using Algorithms in C++ 3rd ed by Sedgewick.
Why is testing if the remainder == tail important?

Thanks... I'm truly stumped.

Hello Beth.  

That's a great question. You have a FIFO queue, meaning that items are always added onto the tail and removed from the head. In the model, the head and tail keep moving forward, but that would not work in implementation. In the implementation the head and tail are indexes into an array, and the indexes must be kept within the array bounds which are 0 up to and including N-1. They need to rollover back to 0 when they reach N.

You probably already knew that, especially if you're reading Sedgewick. When head reaches N, then head % N will be 0. While head is less than N, head % N will be just the value of head.

The line
head = head % N
can be written as
if (head == N) head = 0;

Because of the way he has implemented the get, with the modulo done first, and the increment done second
{ head = head % N; return q[head++]; }
it is actually possible for head to be equal to N after the get is done. For that reason, and because head is set to N, during initialization he does the head % N in the empty function before comparing against tail. He needs to get head back into the valid range before he can compare it with tail.

I think you should make a full function similar to the empty function to determine if the queue is full. That will show you that using the modulo operator is much more compact than using "if" statements. I believe you already understand how to detect if the queue is full. If adding one element to the tail would make the tail equal to the head, then the queue is already full.

It's easy to do nothing in the put when the queue is full, but the get is designed to return an element so doing nothing is not an option in the C++ syntax. A proper implementation would throw an exception if the queue is empty, or return a success/failure flag while returning the actual Item data through a reference parameter.

I hope that helps you out.
Best regards


All Answers

Answers by Expert:

Ask Experts




No longer taking questions.


No longer taking questions.

No longer taking questions.

©2017 All rights reserved.