Comment faire pour que cette file d'attente liée soit circulaire en utilisant uniquement le pointeur externe arrière?

Question

public void enqueue(Object element) 
// Adds element to the rear of this queue. 
{ 
    LLObjectNode newNode = new LLObjectNode(element); 
if (rear == null) 
    front = newNode; 
else 
    rear.setLink(newNode); 
rear = newNode; 
} 

public Object dequeue() 
// Throws QueueUnderflowException if this queue is empty; 
// otherwise, removes front element from this queue and returns it. 
{ 
if (isEmpty()) 
    throw new QueueUnderflowException("Dequeue attempted on empty queue."); 
else 
{ 
    Object element; 
    element = front.getInfo(); 
    front = front.getLink(); 
    if (front == null) 
    rear = null; 

    return element; 
} 
} 

public boolean isEmpty() 
// Returns true if this queue is empty; otherwise, returns false. 
{ 
if (front == null) 
    return true; 
else 
    return false; 
} 

Answer 1

Eh bien, vous devez au moins effectuer les opérations suivantes dans equeue:

newNode.setLink(front); 

En fait, je ne crois pas que vous avez besoin à la fois front et rear depuis front sera toujours accessible throug rear.getLink().

Voici une suggestion:

public class CircularLinkedList { 

    LLObjectNode rear; 

    // Adds element to the rear of this queue. 
    public void enqueue(Object element) { 
     LLObjectNode newNode = new LLObjectNode(element); 

     if (!isEmpty()) 
      rear.setLink(newNode); 

     LLObjectNode front = front(); 
     rear = newNode; 

     // Set new nodes successor to front 
     newNode.setLink(front); 
    } 


    private LLObjectNode front() { 
     return rear.getLink(); 
    } 


    // Throws QueueUnderflowException if this queue is empty; 
    // otherwise, removes front element from this queue and returns it. 
    public Object dequeue() { 

     if (isEmpty()) 
      throw new QueueUnderflowException(
        "Dequeue attempted on empty queue."); 

     Object element = front().getInfo(); 

     // Exclude front from list 
     if (onlyOneLeft()) 
      rear = null; 
     else 
      rear.setLink(front().getLink()); 

     return element; 
    } 


    private boolean onlyOneLeft() { 
     return front() == rear; 
    } 


    public boolean isEmpty() { 
     // Returns true if this queue is empty; otherwise, returns false. 
     return rear == null; 
    } 
} 

Answer 2

public class CircLinkedUnbndQueue<T> implements UnboundedQueueInterface<T> 
{ 
    protected LLNode<T> rear; // reference to the rear of this queue 

    public CircLinkedUnbndQueue() 
    { 
    rear = null; 
    } 

    public void enqueue(T element) 
    // Adds element to the rear of this queue. 
    { 
    LLNode<T> newNode = new LLNode<T>(element); 

    if (rear == null) 
    { 
     rear = newNode; 
    } 
    else 
    { 
     //links the newNode to the rear node's pointer and then 're'points the 
     //rear node to the newNode. 
     if(rear.getLink() == null) 
     { 
     rear.setLink(newNode); 
     newNode.setLink(rear); 
     } 
     else 
     { 
     newNode.setLink(rear.getLink()); 
     rear.setLink(newNode); 
     } 
    } 
     //'repositions' the reat node at the end of the queue. 
     rear = newNode; 
    } 

    public T dequeue() 
    // Throws QueueUnderflowException if this queue is empty; 
    // otherwise, removes front element from this queue and returns it. 
    { 
    if (isEmpty()) 
     throw new QueueUnderflowException("Dequeue attempted on empty queue."); 
    else 
    { 
     T element; 

     rear = rear.getLink(); 
     element = rear.getInfo(); 

     if (rear.getLink() == null) 
     rear = null; 

     return element; 
    } 
    } 

    public boolean isEmpty() 
    // Returns true if this queue is empty; otherwise, returns false. 
    {    
    if (rear == null) 
     return true; 
    else 
     return false; 
    } 
} 

Je sais que c'est un ancien poste mais j'eu du mal à ce problème récemment et je crois que cela est plus conforme à la question posée, car il utilise seulement utilise un noeud arrière.