Как сделать эту связанную очередь круглой, используя только задний внешний указатель?

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

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;
  }
}

Я знаю, что это старый пост, но недавно у меня возникли проблемы с этой проблемой, и я считаю, что это больше соответствует заданному вопросу, поскольку он использует только задний узел.

Answer 2

Ну, по крайней мере, вам нужно сделать следующее в equeue:

newNode.setLink(front);

На самом деле, я не верю, что вам нужны и front, и rear, поскольку front всегда будет доступен через rear.getLink().

Вот предложение:

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;
    }
}