1
$\begingroup$

I've come across a way of implementing a circular array that represents a double ended queue.

Let the circular array have the following instance variables:

int[] array;
int front = 0;
int rear = -1;
int size = 0;
int capacity = x;  // where x is a parameter in the constructor

The operations of the queue are:

dequeue - return array[front], increment front by 1,

enqueue - increment rear by 1, set array[rear] = value.

I have come to the conclusion that it is not possible to get the size of this queue by using the formula (front - rear + 1) % capacity. However, it is said that it's possible to get the size of the array using the same formula if we let the constructor set the capacity by:

BoundedQueue(int capacity) {
    this.capacity = capacity + 1;
}

With this technique the array will never actually get full and the formula for giving the size of the queue should work (it is said).

However I can't figure out how these modifications to the queue would result in the formula returning the correct size of the queue? We're only making the array one size bigger than it actually is, and we're always leaving at least one element unused. Could someone with a better insight explain to me why these modifications will lead to (rear - front + 1) % capacity giving the correct size of the queue?

Thanks in advance!

$\endgroup$
  • $\begingroup$ Try working through some small examples. That's usually a good way to get a feeling for this. $\endgroup$ – D.W. Jun 4 '15 at 15:04
1
$\begingroup$

I've not checked if your formula is correct but the point appears to be that $x\%y$ can only give answers in the range $\{0, \dots, y-1\}$, whereas you're performing a calculation where the answer could be anything in the range $\{0, \dots, y\}$, including $y$. This means that any formula of the form blah%capacity is necessarily wrong.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.