an enclosing instance that contains Queue.Node is required

Question

So I'm working on a Binary Search Tree and need to do a Level Order Traversal. I will be printing out all the keys that are on the same level.

Problem I'm having right now is that I need to create a FIFO Queue. I have the Queue created but when I try to add the node to the queue I keep getting the an enclosing instance that contains Queue.Node is required error message. Can someone help me out on what I'm doing wrong.

This is my Level Order Traversal at the moment.

public void LevelOrder_Traversal(BST_Node node){
    Queue temp=new Queue();


    Queue.Node newNode=new Queue.Node();

    temp.enqueue(node);

This is my Queue class

public class Queue{
public class Node{
    private Integer key;
    private Node next;

    public Node(){
        this.key=null;
        this.next=null;
    }

    public Node(int key){
        this.key=key;
        this.next=null;
    }
}

int size;
Node head;

public Queue(){
    head=new Node();
    size=0;
}

public void enqueue(Node node){
    if(size==0){
        head=node;
    }

    Node curr=head;
    while(curr.next!=null){
        curr=curr.next;
    }
    curr.next=node;
    size++;
}

public Node dequeue(){
    Node temp=head;
    head=head.next;
    size--;

    return temp;
  }
}

I found a couple of other posts that are similar to what I'm doing but I wasn't really understanding them that much. If someone would be so kind as to explain what I'm doing wrong and why it's wrong that would be great. Do I need to extend the Queue class or anything like that?

Answer 1

This is because your Node inner class is non-static. Non-static classes in Java have an implicit reference to their enclosing class, so they must be instantiated by an instance method of the outer class. Instantiating it like this

Queue.Node newNode=new Queue.Node();

is not valid, even though the Node class is public.

Declare it with the static keyword to fix this compile issue: the class can be logically made static, because its methods do not require knowledge of the enclosing Queue class.

Answer 2

You declare:

public class Queue {
    public class Node {

This means that in order for a Node instance to exist, you must have an instance of Queue. Hence the message: "an enclosing [Queue in this case] instance that contains Queue.Node is required".

The quite ungainly syntax in order to obtain a Node with such a design is:

final Queue queue = new Queue();
final Node node = queue.new Node();

In general, you use this design if it is actually required for Node to have a Queue to be relevant at all. I have never seen that... Except for private inner classes.

But if your Node class can be created independently of a Queue, it must be declared static:

public class Queue {
    public static class Node { // <-- note the 'static'