public class Node {     //Node class structure

    int data;   //data contained in Node; for assignment purposes, data is an int
    Node next;  //pointer to Next Node

    //Node Constructor
    public Node(int data) {
        this.data = data;
        next = null;
    }

    //Set Methods
    public void setData(int data) {         //set Node value
        this.data = data;
    }
    public void setNext(Node next) {        //set next Node value
        this.next = next;
    }

    //Get Methods
    public int getData() {                  //get Node value
        return this.data;
    }
    public Node getNext() {                 //get next Node value
        return this.next;
    }

    //Display the Node Value
    public void displayNode() {
        System.out.println(data + "urgh");  //display value as a string
    }
}

import Question1.Node;

//basic set-up of a FIFO singly linked list
public class SLList{

    protected Node head;    //head of SLList
    protected Node tail;    //tail of SLList
    int n;      //number of elements in SLList

    //SLList constructor
    public SLList() {
        head = null;
        n = 0;
    }

    //check if list is empty
    public boolean isEmpty() {
        return head == null;
    }

    //return the size of the list
    public int size() {
        return n;
    }

    //add a new node to the end of the list
    public boolean insert(int x){
        Node y = new Node(x);

        if (head == null){  //if head is null, thus an empty list
            head = y;       //assign head as y
        }
        else{               //if there is already a tail node
            tail.next = y;  //assign the tail's pointer to the new node
        }
        tail = y;           //assign tail to y
        this.n++;           //increment the queue's size
        return true;        //show action has taken place
    }

    //remove and return node from head of list
    public Node remove(){
        if (n == 0){            //if the list is of size 0, and thus empty
            return null;        //do nothing
        }
        else{                           //if there are node(s) in the list
            Node pointer = head;        //assign pointer to the head
            head = head.next;           //reassign head as next node,
            n--;                        //decrement list size
            return pointer;             //return the pointer
        }
    }

    //display SLList as string
    public void displayList() {
        Node pointer = head;

        while (pointer != null) {
            pointer.displayNode();
            pointer = pointer.next;
        }
        System.out.println(" ");
    }
}

import Question1.Node;
import Question1.SLList;

public class PriorityQueue extends SLList {

    private SLList list;        //SLList variable

    public PriorityQueue(){     //create the official SLList
        list = new SLList();
    }

    //add a new node; new add method that ensures the first element is sorted to be the "priority"
    public boolean add(int x){
        Node y = new Node(x);

        if (n == 0){        //if there are 0 elements, thus an empty list
            head = y;       //assign head as y
        }
        else if (y.data < head.data){   //if new node y is the smallest element, thus highest priority
            y.next = head;              //assign y's next to be current head of queue
            head = y;                   //reassign head to be actual new head of queue (y)
        }
        else{               //if there is already a tail node
            tail.next = y;  //assign the tail's pointer to the new node
        }
        tail = y;           //assign tail to y
        n++;                //increment the queue's size
        return true;        //show action has taken place
    }

    //delete the minimim value (highest priority value) from the queue and return its value
    public Node deleteMin(){
        return list.remove();       //the list is sorted such that the element being removed in indeed the min
    }

    //return the size of the queue
    public int size() {
        return n;
    }

    //display Queue as string
    public void displayQueue() {
        System.out.println("->");
        list.displayList();
    }
}

import Question1.PriorityQueue;

public class TestQ1 {           //Test code

    public static void main(String[] args){
        PriorityQueue PQueue1 = new PriorityQueue();

        PQueue1.add(3);
        PQueue1.add(2);
        PQueue1.add(8);
        PQueue1.add(4);

        System.out.println("Test add(x): ");
        PQueue1.displayQueue();
        System.out.println("Test size(): " + PQueue1.size());

        PriorityQueue PQueue2 = new PriorityQueue();
        //Node node1 = PQueue1.deleteMin();

        System.out.println("Test deleteMin():");
        PQueue2.displayQueue();
        System.out.println("Test size(): " + PQueue2.size());
    }
}