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

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.

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.

Wrap around feature of queue:

You need to understand the fact that location 1 in the array immediately follows location n in circular order. For example

Predecessor of element g at index 1 is f at index 11. Tail pointer always points to the next empty location where new element will be inserted, in enqueue operation, before inserting element we check for overflow condition, if Q.tail +1 = Q.head, it means tail is reached at head location, means no free space, means queue is full.

NOTE: (n-1) length queue can be created with the array of length n.

I don't have your book, but from how I would implement a cyclic buffer: The condition head = tail + 1 means that if an element is inserted then tail is increased by one and then tail = head. But if head is equal to tail the queue is considered empty.