Suppose a circular queue of capacity \((n −1)\) elements is implemented with…
2012
Suppose a circular queue of capacity \((n −1)\) elements is implemented with an array of \(n\) elements. Assume that the insertion and deletion operations are carried out using REAR and FRONT as array index variables, respectively. Initially, REAR = FRONT = 0. The conditions to detect \(queue \ full\) and \(\text queue \ empty\) are
- A.
\(full\): (REAR+1) mod n == FRONT\(empty\): REAR == FRONT - B.
\(full\): (REAR+1) mod n == FRONT\(empty\): (FRONT+1) mod n == REAR - C.
\(full\): REAR == FRONT\(empty\): (REAR+1) mod n == FRONT - D.
\(full\): (FRONT+1) mod n == REAR\(empty\): REAR == FRONT
Attempted by 541 students.
Show answer & explanation
Correct answer: A
Answer: full: (REAR+1) mod n == FRONT; empty: REAR == FRONT
Explanation: The array has n slots but stores at most n−1 elements so one slot is reserved to distinguish full from empty. REAR points to the index where the next insertion will occur; FRONT points to the index of the next deletion.
Full condition: (REAR+1) mod n == FRONT
Reason: advancing REAR by one would make it equal to FRONT, which means there is no free slot to insert a new element.
Empty condition: REAR == FRONT
Reason: when both indices are the same, there are no elements between FRONT and REAR to dequeue.
Example: For n = 5, if REAR = 4 and FRONT = 0 then (REAR+1) mod n = 0 = FRONT, so the queue is full. If REAR = FRONT = 2 then the queue is empty.