Implementing a linked queue with java

Question

I'm having great difficulty coming up with an enqueue method for my queue class. I need it so that the head will toString() into with it pointing to A first. And the tail to be pointing at C where insertion into the queue will happen. I just need a push in the right direction, thanks!

public class SinglyLinkedQueue {
    public static void main(String[] args) {
        SinglyLinkedQueue myQueue = new SinglyLinkedQueue();
        myQueue.enqueue("A");
        myQueue.enqueue("B");
        myQueue.enqueue("C");
        System.out.println(myQueue.toString());
    }
    private SinglyLinkedNode head = new SinglyLinkedNode("",null);
    private SinglyLinkedNode tail = new SinglyLinkedNode("",null);

    public boolean isEmpty() {
        return head == null && tail == null;
    }
    public String toString() {
        if(isEmpty() == true) {
            return "";
        } else {
            return toString(head);
        }
    }
    public String toString(SinglyLinkedNode n1) {
        if(n1 == null) {
            return "";
        }
        String comma = "<";
        if(head != n1) {
            comma = ",";
        } if(n1.getNext() == null) {
            comma = ">";
        }
        return comma+n1.getValue()+toString(n1.getNext());
    }
    public void enqueue(String str) {

    }
}

I have an entire stack class implemented and the toString() method works wonderfully. I just copied and pasted it into here because thats what I was told to do. — Exception, Mar 02 '14 at 00:27
Using recursion for your toString() will limit the number of element you can have in your queue to the size of your stack. You should use a loop instead. — Ted Bigham, Mar 02 '14 at 00:27
I currently have no output because my enqueue class is empty. I tried doing something similar to a stack which gave me but thats not my desired outcome. — Exception, Mar 02 '14 at 00:27
In that case, just use the `<` and `>` in the toString(), and append the nodes, you don't need to use recursion. — Peter Lawrey, Mar 02 '14 at 00:28
@TedBigham What times would I need to iterate past my stack size? — Exception, Mar 02 '14 at 00:29
@PeterLawrey Hmm.. how would i iterate through the for-loop? — Exception, Mar 02 '14 at 00:31
Ok well it still leaves me with my problem on how to implement enqueue, its very confusing getting the head and tail correct — Exception, Mar 02 '14 at 00:54

score 0 · Answer 1 · edited May 23 '17 at 11:57

Assuming this is a FIFO queue and your SinglyLinkedNode constructor is for the node's value and next node: you firstly need set the current tail to point to the new tail, then secondly to set the tail to point to the new tail:

    public void enqueue(String str) {
        // Empty queue
        if (isEmpty()) {
            head = new SinglyLinkedNode(str, null);
            tail = head;
        }
        // Non-empty queue
        else {
            SinglyLinkedNode newTail = new SinglyLinkedNode(str, null);
            tail.next = newTail;
            tail = newTail;
        }
    }

Note that it doesn't make a lot of sense to set the head and tail as separate nodes with an empty String (they are different instances of SinglyLinkedNode). Instead your declaration of fields in SinglyLinkedQueueshould be:

private SinglyLinkedNode head, tail;

Head and tail are just pointers to a particular node(s). You just need to keep them updated as you modify the queue (and of course ensure you keep your nodes all linked appropriately).

Lastly for iterative toString() as pointed out by Ted Bigham:

    @Override
    public String toString() {
        if (isEmpty()) {
            return "";
        }

        String result = "<";
        SinglyLinkedNode current = head;
        while (current != null) {
            result += current.value;
            current = current.next;

            if (current != null) {
                result += ",";
            }
        }
        return result + ">";
    }

Though I think it would be better to return <> for empty queue instead as it is more informative and simplifies the code.

Note also the @Override annotation should be used as you are overriding the default toString() method. Why it is useful is indicated here.

Implementing a linked queue with java

1 Answers1