You are here:

C++/FIFO queue array implementation

Advertisement


Question
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
{
private:
  Item *q; int N; head, tail;
public:
  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.

Answer
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
Zlatko

C++

All Answers


Answers by Expert:


Ask Experts

Volunteer


Zlatko

Expertise

No longer taking questions.

Experience

No longer taking questions.

Education/Credentials
No longer taking questions.

©2016 About.com. All rights reserved.