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


i reading elementary data structures clrs , while reading queue adt came across this:

when q.head = q.tail + 1 , queue full, , if attempt enqueue element, queue overflows.

is true? because if q.tail equals q.length set q.tail = 1 according text. therefore if fill queue q.tail , q.head pointing same position (index 1) , above condition shall not hold. missing here? please point out misinterpreting text. in advance.

here attribute q.head indexes, or points to, queue's head. attribute q.tail indexes next location @ newly arriving element inserted queue.

wrap around feature of queue:

you need understand fact location 1 in array follows location n in circular order. example enter image description here

predecessor of element g @ index 1 f @ index 11. tail pointer points next empty location new element inserted, in enqueue operation, before inserting element check overflow condition, if q.tail +1 = q.head, means tail reached @ head location, means no free space, means queue full.

note: (n-1) length queue can created array of length n.


Comments