to write a Java program that manages a linked queue where the items in the queue
ID: 3762476 • Letter: T
Question
to write a Java program that manages a linked queue where the items in the queue have a priority. The head of the queue points to the first entry on the queue which is the entry with the highest priority. The first entry points to the 2nd node (or is null if the list is empty) which is the entry with the 2nd highest priority, etc. The last entry will point to null. Each node on the queue will have two parts, the pointer to the next entry on the queue (or null) and a pointer to the data item associated to that node entry (which should never be null). The data items are very simple and will consist of two parts, a priority which is a number from 0 to 100 inclusive with 100 being the highest and 0 being the lowest priority and a string.
You will need to create the following methods:
enqueue(newEntry): boolean Adds an entry to the proper place in the queue given its priority. Returns false if cannot add an entry and true if the addition was successful.
dequeue(): T Removes and returns the entry with the highest priority (the 1st entry on the queue).
isEmpty(): boolean Detects whether the queue is empty (true if yes, otherwise false).
clear(): void Removes all entries from the queue.
length(): int Returns the length of the queue.
returnArray(): array T Returns an array of all the entries on the queue in priority order (not nodes, just the data).
main(): void This will probably be the hardest method. It needs to have code that demonstrates that all of the other methods work.
Notes:
Do not use the Java built in list methods, create your own.
Assume that all initialization has been done.
Assume that a call to dequeue will always find something in the queue.
No restriction is placed on the length of the queue.
Feel free to steal code from the book.
Put all methods in a single “.java” file.
Explanation / Answer
/**
*
* Class to hold data items of priority queue along with their priorities
*
*/
class Data
{
//data members
private String info;
private int priority;
//constructor
public Data(String info,int priority)
{
this.info=info;
this.priority=priority;
}
//getter and setter methods
String getInfo() {
return info;
}
void setInfo(String info) {
this.info = info;
}
int getPriority() {
return priority;
}
void setPriority(int priority) {
this.priority = priority;
}
}
/**
*
* Class specifying a node in priority queue
*
*/
class Node
{
//data members
Data item;
Node next;
//constructor
public Node(String item, int priority) throws Exception
{
if(priority>=0 && priority <=100)
{
Data dt=new Data(item,priority);
this.setItem(dt);
this.setNext(null);
}
else
throw new Exception("Illegal node!");
}
/**
* @return the item
*/
Data getItem() {
return item;
}
/**
* @param item the item to set
*/
void setItem(Data item) {
this.item = item;
}
/**
* @return the next
*/
Node getNext() {
return next;
}
/**
* @param next the next to set
*/
void setNext(Node next) {
this.next = next;
}
}
/**
* PriorityQueue class
*/
public class PriorityQueue {
private Node head;
private int count;
/**
* Constructor
*/
public PriorityQueue() {
head=null;
count=0;
}
/**
* @return the head
*/
Node getHead() {
return head;
}
/**
* @param head the head to set
*/
void setHead(Node head) {
this.head = head;
}
/**
* @return the count
*/
int getCount() {
return count;
}
/**
* @param count the count to set
*/
void setCount(int count) {
this.count = count;
}
/**
* @return true if queue is empty.
*/
public boolean isEmpty()
{
if(head==null)
return true;
else
return false;
}
/**
* Clears the queue.
*/
public void clear()
{
head=null;
count=0;
}
/**
* function to return length of priority queue.
* @return
*/
public int length()
{
return count;
}
/**
* function to enqueue an item with a given priority into priority queue
* @param item - data item
* @param priority - priority of data item
* @return true if insertion successful, else false
* @throws Exception
*/
public boolean enqueue(String item, int priority)
{
boolean flag=false;
Node node=null;
try {
node=new Node(item,priority);
if((isEmpty()) || (head.getItem().getPriority() <= node.getItem().getPriority()))
{
node.setNext(head);
head=node;
count++;
flag=true;
}
else
{
Node curr=head;
while((curr.getNext()!=null) && (curr.getNext().getItem().getPriority() > node.getItem().getPriority()))
{
curr=curr.getNext();
}
node.setNext(curr.getNext());
curr.setNext(node);
count++;
flag=true;
}
} catch (Exception e) {
e.printStackTrace();
}
return flag;
}
/**
* function to dequeue element with highest priority from priority queue.
* @return data item with highest priority
*/
public Data dequeue()
{
Data item=null;
Node node=head; //head node always has highest priority
head=head.getNext();
item=node.getItem();
count--;
return item;
}
/**
* function to return array of data items of priority queue
* @return array containing data elements in the order of their priority
*/
public String[] returnArray()
{
String array[] = new String[count];
Node curr=head;
int i=0;
while(curr!=null)
{
array[i]=curr.getItem().getInfo();
i++;
curr=curr.getNext();
}
return array;
}
/**
* main function *
*/
public static void main(String[] args) {
System.out.println("Creating priority queue...");
PriorityQueue pq=new PriorityQueue();
System.out.println("Inserting data into priority queue...");
if(pq.enqueue("abc", 2))
System.out.println("Insertion successful!");
if(pq.enqueue("bca", 1))
System.out.println("Insertion successful!");
if(pq.enqueue("cab", 3))
System.out.println("Insertion successful!");
System.out.println("Length of priority queue after insertion:"+pq.length());
System.out.println("Checking data into priority queue...");
String[] arr=pq.returnArray();
for(int i=0;i<arr.length;i++)
System.out.println("element:"+arr[i]);
System.out.println("Deleting element with highest priority...");
Data item=pq.dequeue();
System.out.println("Deleted item:"+item.getInfo()+", priority:"+item.getPriority());
System.out.println("Length of priority queue after deletion:"+pq.length());
System.out.println("Clearing priority queue...");
pq.clear();
System.out.println("Length of priority queue after clearing:"+pq.length());
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.