Блог

Я пытаюсь реализовать очередь с циклическим связанным списком с одной ссылкой. Я полагаю, что это FIFO, основанный на тестах (rear обновляется, как и должно быть, каждый раз, когда элемент ставится в очередь), но он печатает в обратном порядке. Должен ли я ожидать этого, или я что-то упускаю? Я попытался изменить toString(). Вот мой класс circularlink queue:

 public class CircularLinkedQueue implements UnboundedQueueInterface

{

protected LLObjectNode rear;        

public CircularLinkedQueue()
{
    rear = null;
}


public void enqueue(Object element)
{
    LLObjectNode newNode = new LLObjectNode(element);

    if (rear == null)
        newNode.setLink(newNode);

    newNode.setLink(rear);      
    rear = newNode;     
}// end enqueue()


public Object dequeue() throws QueueUnderflowException
{
    if (isEmpty())
        throw new QueueUnderflowException("Dequeue attempted on an empty queue.");
    else
    {
        Object element;                 // create a reference to the Object to return
        element = rear.getLink();       // set the reference to the information in the front node
        rear = rear.getLink();          // set the rear reference to point at the next node

        return element;                 
    }// end else
}// end dequeue()


public boolean isEmpty()
{
    return (rear == null);              
}// end isEmpty()


// *** Exercise #25b        *** works
public Object front()
// returns a reference to the front element on the queue.
// precondition: queue is not empty.
{
    Object frontObj;
    frontObj = rear.getLink();  
    return frontObj;
}// end front()


public int size()
{
    LLObjectNode node;
    node = rear;
    int count = 0;

    while (node != null)
    {
        count  ;
        node = node.getLink();
    }
    return count;
}// end size()


public String toString()
{
    String circleQStr = "";
    LLObjectNode node;
    int count = 0;
    node = rear;

    while (node != null)
    {
        count  ;
        circleQStr = circleQStr   count   ". "   node.getInfo()   "n";
        node = node.getLink();
    }// end while
    return circleQStr;
    }// end toString()  
}// end class CircularLinkedQueue
  

Вот getLink() и setLink() :

     public void setLink(LLObjectNode link)
{
    // sets link of this LLObjectNode
    this.link = link;
}


public LLObjectNode getLink()
{
    // returns link of this LLObjectNode
    return link;
}
  

Спасибо, что прочитали мой пост.

С этим кодом существует ряд проблем, которые, я думаю, не связаны с заявленной вами проблемой, но если ваш начальный узел является задним, то вам нужно продвинуться вперед перед печатью, иначе сначала будет напечатан задний. Также … я не думаю, что ваша size() функция когда-либо вернется…в циклической очереди следующий элемент никогда не будет равен null. Также сложно отладить это без публикации кода для getLink() и setLink()

Редактировать Хорошо, я думаю, проблема в том, что ваш enequeue метод должен выглядеть следующим образом

 public void enqueue(Object element)
{
    LLObjectNode newNode = new LLObjectNode(element);

    if (rear == null){
        newNode.setLink(newNode);

    }else{
        newNode.setLink(rear.getLink()); 
        rear.setLink(newNode);      
    } 

    rear = newNode;   
}// end enqueue()
  

Кроме того, вам нужно изменить свой метод удаления из очереди. Прямо сейчас у вас есть обратная сторона, указывающая на элемент, который вы только что исключили из очереди.

 public Object dequeue() throws QueueUnderflowException
{
    if (isEmpty())
        throw new QueueUnderflowException("Dequeue attempted on an empty queue.");
    else
    {
        Object element;                 // create a reference to the Object to return
        element = rear.getLink();       // set the reference to the information in the front node
        rear.setLink(element.getLink());          // set the rear reference to point at the next node

        return element;                 
    }// end else
}// end dequeue()