开发者

Should I expect a circular linked list queue to print backward?

I am trying to implement a circular linked list queue with a single reference. I believe it is FIFO based on tests (rear is updating as it should each time an element is enqueued), but it is printing in reverse. Should I expect this, or am I missing something? I have tried changing the toString()开发者_高级运维. Here is my CircularLinkedQueue class:

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

Here are getLink() and setLink():

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


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

Thank you for reading my post.


There are a number of problems with this code that I think are unrelated to your stated problem, but if your starting node is the rear, then you need to advance before you print, otherwise it'll print the rear first. Also...I don't think your size() function will ever return...in a circular queue, the next element will never be null. It's also difficult to debug this without you posting the code for getLink() and setLink()

Edit Alright, I think the problem is that your enequeue method should look like this

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()

Also, you need to change your dequeue method. Right now you have the rear pointing to the element you just dequeued.

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()
0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜