3
$\begingroup$

CLRS gives the following implementation for a queue's enqueue and dequeue operations

head = 1
tail = 1

ENQUEUE(Q, x)
Q[Q.tail] = x
if Q.tail == Q.length
    Q.tail = 1
else Q.tail = Q.tail + 1

DEQUEUE(Q)
x = Q[Q.head]
if Q.head == Q.length
    Q.head = 1
else Q.head = Q.head + 1
return x

but I'm having trouble understanding why both

if Q.tail == Q.length
    Q.tail = 1

and

if Q.head == Q.length
    Q.head = 1

are needed. What would be a conceptual (or possibly visual) explanation of these two if-statements?

$\endgroup$
3
  • 1
    $\begingroup$ I think it's so because we "wrap" around when we are at the end of the queue. When we can't insert or delete at the last position, we move to the first position. $\endgroup$
    – Gokul
    Nov 4, 2018 at 16:12
  • $\begingroup$ Check this too. $\endgroup$
    – Gokul
    Nov 4, 2018 at 16:28
  • $\begingroup$ @Gokul Make an answer? (Buzzword: circular array/buffer) $\endgroup$
    – Raphael
    Nov 4, 2018 at 18:36

1 Answer 1

3
$\begingroup$

CLRS defines a queue using an array which wraps around i.e when we no longer can insert/delete in the last position, we move to the first position.

From the book,

The elements in the queue are in locations head[Q], head [Q] + 1, . . . , tail [Q] - 1, where we "wrap around" in the sense that location 1 immediately follows location n in a circular order.

Thus,

if Q.tail == Q.length

This is for the condition when the tail points to the last element.

if Q.head == Q.length

This is for the condition when the head points to the last element.

In both cases, we move to the first element due to circular nature.

An example would be this:

Check this out.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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