Supongamos que se implementa una cola circular de elementos de capacidad (n – 1) con una array de n elementos. Suponga que la operación de inserción y eliminación se lleva a cabo utilizando REAR y FRONT como variables de índice de array, respectivamente. Inicialmente, REAR = FRONT = 0. Las condiciones para detectar cola llena y cola vacía son
(A) Full: (REAR+1) mod n == FRONT, empty: REAR == FRONT
(B) Full: (REAR+1) mod n == DELANTERO, vacío: (FRONTAL+1) mod n == TRASERO
(C) Completo: TRASERO == DELANTERO, vacío: (TRASERO+1) mod n == DELANTERO
(D) Completo: (FRONTAL+1) mod n == TRASERO, vacío: TRASERO == DELANTERO
Respuesta: (A)
Explicación:
Implementación de Circular Queue:
Cabeza : siempre apunta a la ubicación desde donde se realiza la próxima eliminación de la cola.
Cola : siempre apunta a la siguiente ubicación vacía en la que se realizará la próxima inserción en la cola.
Usaremos la función de ajuste ya que es una cola circular que es cuando la cola o la cabeza están en el índice n-1, la próxima operación los llevará al índice 0. A pesar de tener una capacidad de n dentro de la array, reservaremos un lugar vacío para detectar las condiciones de desbordamiento (Cola llena) y subdesbordamiento (Cola vacía). Los elementos de la cola residen en las ubicaciones Q.head, Q.head + 1, . . . , Q.tail + 1, donde «envolvemos» en el sentido de que la ubicación 0 sigue inmediatamente a la ubicación n-1 en un orden circular.
Algoritmo:
ENQUEUE(Q, x) { if Q.head == Q.tail + 1 error "Queue overflow" Q[Q.tail] = x if Q.tail == Q.length - 1 Q.tail = 0 else Q.tail = Q.tail + 1 } DEQUEUE(Q) { if Q.head == Q.tail error "Queue underflow" x = Q[Q.head] if Q.head == Q.length - 1 Q.head = 0 else Q.head = Q.head + 1 return x }
Ver http://en.wikipedia.org/wiki/Circular_buffer#Always_Keep_One_Slot_Open
Esta solución es aportada por Pranjul Ahuja
Cuestionario de esta pregunta
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA