Estructuras de datos | Lista vinculada | Pregunta 12

Se utiliza una lista enlazada circularmente para representar una cola. Se utiliza una única variable p para acceder a la cola. ¿A qué Node debe apuntar p para que las operaciones enQueue y deQueue puedan realizarse en tiempo constante? (PUERTA 2004)
circularLinkedList

(A) Node posterior
(B) Node frontal
(C) no es posible con un solo puntero
(D) Node junto al Node frontal

Respuesta: (A)
Explicación: la respuesta no es «(b) Node frontal», ya que no podemos obtener la parte trasera desde adelante en O(1), pero si p está atrás podemos implementar tanto enQueue como deQueue en O(1) porque desde atrás podemos llegar al frente en O(1). A continuación se muestran funciones de muestra. Tenga en cuenta que estas funciones son solo una muestra y no funcionan. Falta el código para manejar los casos base.

/* p is pointer to address of rear (double pointer).  This function adds new 
   node after rear and updates rear which is *p to point to new node  */
void  enQueue(struct node **p, struct node *new_node)
{
    /* Missing code to handle base cases like *p is NULL */
       
     new_node->next = (*p)->next;
     (*p)->next = new_node;
     (*p) = new_node /* new is now rear */
     /* Note that p->next is again front and  p is rear */
  
 }
  
/* p is pointer to rear. This function removes the front element and 
    returns the dequeued element from the queue */
struct node *deQueue(struct node *p)
{
    /* Missing code to handle base cases like p is NULL,
        p->next is NULL,...  etc */
  
    struct node *temp = p->next;
    p->next = p->next->next;
    return temp;
    /* Note that p->next is again front and  p is rear */
}

Prueba de esta pregunta
Prueba 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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *