Question

In: Computer Science

Implement a priority queue using a DoublyLinkedList where the node with the highest priority (key) is...

Implement a priority queue using a DoublyLinkedList where the node with the highest priority (key) is the right-most node.
The remove (de-queue) operation returns the node with the highest priority (key).
If displayForward() displays List (first-->last) : 10 30 40 55
remove() would return the node with key 55.
Demonstrate by inserting keys at random, displayForward(), call remove then displayForward() again.
You will then attach a modified DoublyLinkedList.java (to contain the new priorityInsert(long key) and priorityRemove() methods), and a driver to demonstrate as shown above.

Use the provided PQDoublyLinkedTest.java to test your code.

public class PQDoublyLinkedTest
{
    public static void main(String[] args)
    {                             // make a new list
        DoublyLinkedList theList = new DoublyLinkedList();

        theList.priorityInsert(22);      // insert at front
        theList.priorityInsert(44);
        theList.priorityInsert(66);

        theList.priorityInsert(11);       // insert at rear
        theList.priorityInsert(33);
        theList.priorityInsert(55);
        
        theList.priorityInsert(10);
        theList.priorityInsert(70);
        theList.priorityInsert(30);

        theList.displayForward();     // display list forward
        Link2 removed = theList.priorityRemove();
        System.out.print("priorityRemove() returned node with key: ");
        removed.displayLink2();
        
    }  // end main()
}  // end class PQDoublyLinkedTest

_____________________________________________________________________________________________________________________________________________________

// doublyLinked.java
// demonstrates doubly-linked list
// to run this program: C>java DoublyLinkedApp

class Link
{
public long dData; // data item
public Link next; // next link in list
public Link previous; // previous link in list

public Link(long d) // constructor
{ dData = d; }

public void displayLink() // display this link
{ System.out.print(dData + " "); }

} // end class Link

class DoublyLinkedList
{
private Link first; // ref to first item
private Link last; // ref to last item

public DoublyLinkedList() // constructor
{
first = null; // no items on list yet
last = null;
}

public boolean isEmpty() // true if no links
{ return first==null; }

public void insertFirst(long dd) // insert at front of list
{
Link newLink = new Link(dd); // make new link

if( isEmpty() ) // if empty list,
last = newLink; // newLink <-- last
else
first.previous = newLink; // newLink <-- old first
newLink.next = first; // newLink --> old first
first = newLink; // first --> newLink
}

public void insertLast(long dd) // insert at end of list
{
Link newLink = new Link(dd); // make new link
if( isEmpty() ) // if empty list,
first = newLink; // first --> newLink
else
{
last.next = newLink; // old last --> newLink
newLink.previous = last; // old last <-- newLink
}
last = newLink; // newLink <-- last
}

public Link deleteFirst() // delete first link
{ // (assumes non-empty list)
Link temp = first;
if(first.next == null) // if only one item
last = null; // null <-- last
else
first.next.previous = null; // null <-- old next
first = first.next; // first --> old next
return temp;
}

public Link deleteLast() // delete last link
{ // (assumes non-empty list)
Link temp = last;
if(first.next == null) // if only one item
first = null; // first --> null
else
last.previous.next = null; // old previous --> null
last = last.previous; // old previous <-- last
return temp;
}

// insert dd just after key
public boolean insertAfter(long key, long dd)
{ // (assumes non-empty list)
Link current = first; // start at beginning
while(current.dData != key) // until match is found,
{
current = current.next; // move to next link
if(current == null)
return false; // didn't find it
}
Link newLink = new Link(dd); // make new link

if(current==last) // if last link,
{
newLink.next = null; // newLink --> null
last = newLink; // newLink <-- last
}
else // not last link,
{
newLink.next = current.next; // newLink --> old next
// newLink <-- old next
current.next.previous = newLink;
}
newLink.previous = current; // old current <-- newLink
current.next = newLink; // old current --> newLink
return true; // found it, did insertion
}

public Link deleteKey(long key) // delete item w/ given key
{ // (assumes non-empty list)
Link current = first; // start at beginning
while(current.dData != key) // until match is found,
{
current = current.next; // move to next link
if(current == null)
return null; // didn't find it
}
if(current==first) // found it; first item?
first = current.next; // first --> old next
else // not first
// old previous --> old next
current.previous.next = current.next;

if(current==last) // last item?
last = current.previous; // old previous <-- last
else // not last
// old previous <-- old next
current.next.previous = current.previous;
return current; // return value
}

public void displayForward()
{
System.out.print("List (first-->last): ");
Link current = first; // start at beginning
while(current != null) // until end of list,
{
current.displayLink(); // display data
current = current.next; // move to next link
}
System.out.println("");
}

public void displayBackward()
{
System.out.print("List (last-->first): ");
Link current = last; // start at end
while(current != null) // until start of list,
{
current.displayLink(); // display data
current = current.previous; // move to previous link
}
System.out.println("");
}

} // end class DoublyLinkedList

class DoublyLinkedApp
{
public static void main(String[] args)
{ // make a new list
DoublyLinkedList theList = new DoublyLinkedList();

theList.insertFirst(22); // insert at front
theList.insertFirst(44);
theList.insertFirst(66);

theList.insertLast(11); // insert at rear
theList.insertLast(33);
theList.insertLast(55);

theList.displayForward(); // display list forward
theList.displayBackward(); // display list backward

theList.deleteFirst(); // delete first item
theList.deleteLast(); // delete last item
theList.deleteKey(11); // delete item with key 11

theList.displayForward(); // display list forward

theList.insertAfter(22, 77); // insert 77 after 22
theList.insertAfter(33, 88); // insert 88 after 33

theList.displayForward(); // display list forward
} // end main()
} // end class DoublyLinkedApp

____________________________________________________________________________________________________________________________________________________

Solutions

Expert Solution

//inserts a key in sorted order

class Link {

public long dData; // data item

public Link next; // next link in list

public Link previous; // previous link in list

public Link(long d) // constructor

{

dData = d;

}

public void displayLink() // display this link

{

System.out.print(dData + " ");

}

} // end class Link

class DoublyLinkedList {

private Link first; // ref to first item

private Link last; // ref to last item

public DoublyLinkedList() // constructor

{

first = null; // no items on list yet

last = null;

}

public boolean isEmpty() // true if no links

{

return first == null;

}

public void insertFirst(long dd) // insert at front of list

{

Link newLink = new Link(dd); // make new link

if (isEmpty()) // if empty list,

last = newLink; // newLink <-- last

else

first.previous = newLink; // newLink <-- old first

newLink.next = first; // newLink --> old first

first = newLink; // first --> newLink

}

public void insertLast(long dd) // insert at end of list

{

Link newLink = new Link(dd); // make new link

if (isEmpty()) // if empty list,

first = newLink; // first --> newLink

else {

last.next = newLink; // old last --> newLink

newLink.previous = last; // old last <-- newLink

}

last = newLink; // newLink <-- last

}

public Link deleteFirst() // delete first link

{ // (assumes non-empty list)

Link temp = first;

if (first.next == null) // if only one item

last = null; // null <-- last

else

first.next.previous = null; // null <-- old next

first = first.next; // first --> old next

return temp;

}

public Link deleteLast() // delete last link

{ // (assumes non-empty list)

Link temp = last;

if (first.next == null) // if only one item

first = null; // first --> null

else

last.previous.next = null; // old previous --> null

last = last.previous; // old previous <-- last

return temp;

}

// insert dd just after key

public boolean insertAfter(long key, long dd) { // (assumes non-empty list)

Link current = first; // start at beginning

while (current.dData != key) // until match is found,

{

current = current.next; // move to next link

if (current == null)

return false; // didn't find it

}

Link newLink = new Link(dd); // make new link

if (current == last) // if last link,

{

newLink.next = null; // newLink --> null

last = newLink; // newLink <-- last

} else // not last link,

{

newLink.next = current.next; // newLink --> old next

// newLink <-- old next

current.next.previous = newLink;

}

newLink.previous = current; // old current <-- newLink

current.next = newLink; // old current --> newLink

return true; // found it, did insertion

}

public Link deleteKey(long key) // delete item w/ given key

{ // (assumes non-empty list)

Link current = first; // start at beginning

while (current.dData != key) // until match is found,

{

current = current.next; // move to next link

if (current == null)

return null; // didn't find it

}

if (current == first) // found it; first item?

first = current.next; // first --> old next

else

// not first

// old previous --> old next

current.previous.next = current.next;

if (current == last) // last item?

last = current.previous; // old previous <-- last

else

// not last

// old previous <-- old next

current.next.previous = current.previous;

return current; // return value

}

public void displayForward() {

System.out.print("List (first-->last): ");

Link current = first; // start at beginning

while (current != null) // until end of list,

{

current.displayLink(); // display data

current = current.next; // move to next link

}

System.out.println("");

}

public void displayBackward() {

System.out.print("List (last-->first): ");

Link current = last; // start at end

while (current != null) // until start of list,

{

current.displayLink(); // display data

current = current.previous; // move to previous link

}

System.out.println("");

}

/**

* method to insert a key in sorted order

* @param key

* key to be added

public void insertSorted(long key) {

// if list is empty or key is less than current first, inserting at

// first

if (isEmpty() || key < first.dData) {

insertFirst(key);

return; // exiting method

}

// taking a reference to first

Link current = first;

// looping as long as current.next is not null

while (current.next != null) {

// checking if key can be added between current and current.next

if (key >= current.dData && key <= current.next.dData) {

// adding between current and current.next and updating all

// links

Link lnk = new Link(key);

lnk.next = current.next;

current.next.previous = lnk;

current.next = lnk;

lnk.previous = current;

return; //exiting

}

//otherwise, advancing to next link

current = current.next;

}

//if the element is still not inserted, adding to the end

insertLast(key);

}

// -------------------------------------------------------------

} // end class DoublyLinkedList

// PriorityLinkQueue.java (representing a Priority Queue using the above doubly linked list)

//class representing a PriorityLinkQueue

public class PriorityLinkQueue {

// using a DoublyLinkedList as instance variable

private DoublyLinkedList list;

// constructor initializing empty pq

public PriorityLinkQueue() {

list = new DoublyLinkedList();

}

// inserts a key in proper position

public void insert(long key) {

list.insertSorted(key);

}

// removes and returns the element with highest value

public long remove() {

// if empty, throwing an exception

if (list.isEmpty()) {

throw new RuntimeException("Priority Queue is empty!");

}

// otherwise, removing last value from doubly list and returning the

// data

return list.deleteLast().dData;

}

// returns true if pq is empty

public boolean isEmpty() {

return list.isEmpty();

}

// displays the queue forward

public void displayForward() {

list.displayForward();

}

// main method for testing the new PriorityLinkQueue, move this code to

// anywhere else if you want to.

public static void main(String[] args) {

// creating a queue

PriorityLinkQueue q = new PriorityLinkQueue();

// adding 10 random keys between 0 and 99 to the queue, displaying it

// after every insertion

for (int i = 0; i < 10; i++) {

q.insert((long) (Math.random() * 100));

q.displayForward();

}

// looping and removing all entries from queue, displaying the queue

// after every removal

while (!q.isEmpty()) {

System.out.println(q.remove() + " is removed");

q.displayForward();

}

/*OUTPUT*/

List (first-->last): 39

List (first-->last): 4 39

List (first-->last): 4 9 39

List (first-->last): 4 9 14 39

List (first-->last): 4 5 9 14 39

List (first-->last): 4 5 9 13 14 39

List (first-->last): 4 5 9 13 14 39 74

List (first-->last): 4 5 9 13 14 39 74 95

List (first-->last): 4 5 9 13 14 39 74 90 95

List (first-->last): 4 5 9 13 14 36 39 74 90 95

95 is removed

List (first-->last): 4 5 9 13 14 36 39 74 90

90 is removed

List (first-->last): 4 5 9 13 14 36 39 74

74 is removed

List (first-->last): 4 5 9 13 14 36 39

39 is removed

List (first-->last): 4 5 9 13 14 36

36 is removed

List (first-->last): 4 5 9 13 14

14 is removed

List (first-->last): 4 5 9 13

13 is removed

List (first-->last): 4 5 9

9 is removed

List (first-->last): 4 5

5 is removed

List (first-->last): 4

4 is removed

List (first-->last):

venereology answered 1 month ago

Next > < Previous

Related Solutions

Implement a priority queue using a DoublyLinkedList where the node with the highest priority (key) is...

Implement a priority queue using a DoublyLinkedList where the node with the highest priority (key) is the right-most node. The remove (de-queue) operation returns the node with the highest priority (key). If displayForward() displays List (first-->last) : 10 30 40 55 remove() would return the node with key 55. Demonstrate by inserting keys at random, displayForward(), call remove then displayForward() again. You will then attach a modified DoublyLinkedList.java (to contain the new priorityInsert(long key) and priorityRemove() methods). Use the provided...

Implement a priority queue using a DoublyLinkedList where the node with the highest priority (key) is...

Implement a priority queue using a DoublyLinkedList where the node with the highest priority (key) is the right-most node. The remove (de-queue) operation returns the node with the highest priority (key). If displayForward() displays List (first-->last) : 10 30 40 55 remove() would return the node with key 55. You will then attach priorityInsert(long key) and priorityRemove() methods). AND Use the provided PQDoublyLinkedTest.java to test your code. BOTH CODES SHOULD WORK TOGETHER, YOU JUST HAVE TO ADD priorityInsert(int). PLEASE PROVIDE...

Use a priority queue to simulate prioritized jobs Priority Queue class Queue Class Node Class (Node...

Use a priority queue to simulate prioritized jobs Priority Queue class Queue Class Node Class (Node will have a 4 digit job number and a priority (A, B, etc) with A highest priority In the driver Create a priority queue object Add 3 jobs of 'B' priority Add 4 jobs of 'D' priority Add 2 jobs of highest priority Print the queue

Implement the minimum priority queue UnsortedMPQ (using vector) that is a child class of the provided...

Implement the minimum priority queue UnsortedMPQ (using vector) that is a child class of the provided MPQ class. The functions from MPQ that are virtual function (remove min(), is empty(), min(), and insert()) must be implemented in the child classes. The functions remove min() and min() should throw an exception if the minimum priority queue is empty. For the UnsortedMPQ class, you will use a vector to implement the minimum priority queue functions. The insert() function should be O(1) and...

write a java program to Implement a Priority Queue using a linked list. Include a main...

write a java program to Implement a Priority Queue using a linked list. Include a main method demonstrating enqueuing and dequeuing several numbers, printing the list contents for each.

write C program to implement the priority queue with the operation insert

Implement a Priority Queue (PQ) using an UNSORTED LIST. Use an array size of 10 elements....

Implement a Priority Queue (PQ) using an UNSORTED LIST. Use an array size of 10 elements. Use a circular array: Next index after last index is 0. Add the new node to next available index in the array. When you add an element, add 1 to index (hit max index, go to index 0). Test if array in full before you add. When you remove an element, from the list, move the following elements to the left to fill in...

Priority Queue Application: Use your Java's Priority Queue. Make a priority queue to represent customers being...

Priority Queue Application: Use your Java's Priority Queue. Make a priority queue to represent customers being served at the Department of Motor Vehicles. Start with 100 customers in a List. In a loop, generate a priority for each customer (1-5) In a second loop, add the users to a priority queue Print the List and the Priority Queue

Linux always picks up the process from the highest priority queue that is not empty. How...

Linux always picks up the process from the highest priority queue that is not empty. How does it prevent starvation of processes in the lower priority queues? (Please help Operating system question, 6 points)

What are the differences between a maximum priority queue and a minimum priority queue?

Subjects