Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why Q.head = Q.tail + 1 represents the queue is full in CLRS

I was reading Elementary Data Structures from CLRS and while reading Queue ADT I came across this:

When Q.head = Q.tail + 1 , the queue is full, and if we attempt to enqueue an element, then the queue overflows.

Is it always true? because if Q.tail equals Q.length then we set Q.tail = 1 according to the text. Therefore if we completely fill the Queue then Q.tail and Q.head will be pointing to the same position (index 1) and the above condition shall not hold. What am I missing here? Please point out where am I misinterpreting the text. Thanks in advance.

Here Attribute Q.head indexes, or points to, queue's head. The attribute Q.tail indexes the next location at which a newly arriving element will be inserted into the queue.

like image 385
Rishabh Avatar asked May 06 '13 09:05

Rishabh


2 Answers

It's been been six years but none of these answers point out the fact that in circular buffers, there is no clean way to differentiate the case where the buffer full vs empty cases. In both cases head = tail.

Most workarounds hinder readability and introduce complexities, so when implementing circular buffers, we make a few assumptions that solve this problem and maintain simplicity.

  • We deliberately use only N-1 elements in the N element buffer.
  • When head = tail it means the buffer empty.
  • tail + 1 = head means the buffer full.

Here is a good read on implementing circular buffers.

like image 166
rahul agarwal Avatar answered Nov 15 '22 23:11

rahul agarwal


As mentioned in the same paragraph in CLRS,

to implement a queue of at most n-1 elements using an array Q[1...n].

which means one position is left. It's for checking if the queue is full. If we use all the array positions, the empty queue condition and full queue condition would be the same, which is Q.head=Q.tail. @siddstuff has explained the wrap around feature, Q.head = Q.tail+1 means there is only one empty position left, so the queue is full.

like image 29
Ce7 Avatar answered Nov 16 '22 01:11

Ce7