PUERTA | PUERTA CS 2012 | Pregunta 33

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