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.
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.
N-1
elements in the N
element buffer.head = tail
it means the buffer empty.tail + 1 = head
means the buffer full.Here is a good read on implementing circular buffers.
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With