So I'm trying to implement a priority queue with a linked list. I think I have the basics together, but for some reason my test cases aren't working. When I run it, the size show up fine, but none of the node values are showing (only an arrow "->" pops up once). If anyone could help me figure out why it isn't working, or suggest a better way to set up test cases in java (I've never done that before) it would be appreciated!
Node class:
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
}
}
Linked List Class:
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(" ");
}
}
Priority Queue Class:
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();
}
}
Test Cases (so far, the delete one wasn't working so it's commented out):
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());
}
}
Aucun commentaire:
Enregistrer un commentaire