Question

3. A queue implementation is being done using a circular array. It has a front and a rear index for the array. Given that the queue length is q.length, give the following tests: How do you test if the queue is empty? How do you test if the queue is full? Assuming the queue is not empty, how do you remove an item from the queue? (How do you update the values for front and/or rear?) Assuming the queue is not full, how do you add an item to the queue?

Answer 1

a) Queue is empty:

Answer: if (front == -1 && rear == -1), then the queue is empty.

b) Queue is full

Answer: if (front == (rear + 1) % q.length), then the queue is full.

c) Deleting an item from the queue

Answer:

item = a[front];
if(front == rear) {
   front = -1;
   rear = -1;
}
else {
   front = (front+1) % q.length;
}
return item;

d) Adding an item to the queue

Answer:

if(front == -1) {   
   front = 0;
}
rear = (rear + 1) % q.length;
a[rear] = item;