How to add to the beginning of a queue in java

Question

I am making a simple queue implementation with nodes that have instance methods setNext, getNext. The class I am writing them has fields Node First, and Node Last. My enqueue method must have 3 cases

(1) Add to end of list (normal queue implementation)

this.back.setNext(node to add);
this.back = (node to add);

(2) Add to empty list

this.front = this.back = (node to add);

(3) Add to front of list (and thus move all other elements back)

It seems really simple to me but I am having a tough time sorting out how to get all of the next values to match and not overwrite any nodes. Please let me know of an algorithm that could do this. Thanks!

Update: one implementation I have tried is using an array:

Node[] x = new Node[this.totalNodes+1];
    Node current = this.front;
    int i = 0;
    while(current != null) {
      x[i] = current;
      current = current.getNext();
      i++;
    }
    int j = 0;
    Node current2 = this.front;
    this.front = (node to add)
    while(j < x.length-1) {

      current2.setNext(x[j+1]);
      current2 = current2.getNext();
      j++;
    }

Implementing a queue is a practice assignment. You need to try yourself and report back with code when you get stuck. — Maarten Bodewes
Do you want the old front node to point to the new front node as it's next node? — Jaybird
No, is that happening somewhere? The new front node should not be pointed to by anything, but should point to the old front node — usur22
Sorry yes, that's what I meant. So (node to add).setNext(this.front)? — Jaybird

Traian GEICU Traian GEICU · Accepted Answer · 2020-04-08T21:12:27

Maybe this is what you wanted

public class MyDS {
Node head=null;
Node next=null;
class Node
{
    String data;
    Node link=null;
    Node(String s)
    {
        data=s;
    }
}
public void add(Node n)
{
    if(head == null)
    {
        head = n;
        n.link = null;
    }
    else
    {
        if(next == null)
        {
            next = n;
            head.link = next;
        }
        else
        {
            next.link = n;
            next = n;

        }
    }

}
public void addTop(Node n)
{
    if(head == null)
    {
        head = n;
        n.link = null;
    }
    else
    {
        Node oldHead = head;
        head = n;
        n.link = oldHead;

    }
}

public String print()
{
    String str="";
    Node startN=head;
    while(startN.link != null)
    {
        str+=startN.data+"_";
        startN = startN.link;
    }
    if(startN.data !=null) str+=startN.data+"_End!";
    return str;
}

public static void main(String args[])
{
    MyDS myDS = new MyDS();
    myDS.add(myDS.new Node("a"));
    myDS.add(myDS.new Node("b"));
    myDS.add(myDS.new Node("c"));
    myDS.addTop(myDS.new Node("d"));
    myDS.add(myDS.new Node("e"));
    myDS.addTop(myDS.new Node("f"));
    System.out.println(myDS.print());
}
}

Output

f_d_a_b_c_e_End!

How to add to the beginning of a queue in java

1 Answers