Question

In: Computer Science

#data structure 1.Implement the generic PriorityQueueInterface in a class named PriorityQueue. Note: it must be named...

#data structure

1.Implement the generic PriorityQueueInterface in a class named PriorityQueue. Note: it must be named PriorityQueue The priority queue MUST be implemented using a linked list.

2 test program

checks that a newly constructed priority queue is empty

o checks that a queue with one item in it is not empty

o checks that items are correctly entered that would go at the front of the queue

o checks that items are correctly entered that would go at the end of the queue

o checks that items are correctly entered that would go in the middle of the queue

o checks that you can enqueue several items, dequeue ALL the items, check that the queue is now empty, enqueue new items, display the queue – in other words, give your code and queue a real workout.

// PriorityQueueInterface is here

public interface QueueInterface<T> {
  
public void enqueue(T item); // Add to the rear of the queue.
public T dequeue(); // Delete and return the item
// at the front of the queue.
public T front(); // Return the item at the front
// of the queue, do not delete.
  
public boolean isEmpty(); // Check if the queue is empty.
public boolean isFull(); // Check if the queue is full.
  
public String toString(); // Return a printable display
// of the items in the queue.
}

//integernode class is here

public class IntegerNode implements Comparable<IntegerNode>
{
  
Integer i; // The integer stored in the node.
  
public IntegerNode(Integer x) // The constructor initializes
{ // the instance variable i.
this.i = x;
}

/*
* compareTo() compares this objects integer to
* another (rhs - right hand side)
* objects integer value.
*
* If this node has a smaller integer value
* it has higher priority and in this sense
* is "bigger" than the rhs object and compareTo()
* returns +1.
*/   

public int compareTo(IntegerNode rhs)
{
if (this.i > rhs.i) // This object has lower priority
return -1; // ... so return -1.
else if (this.i < rhs.i) // This object has higher priority
return 1; // ... so return +1.
else // The objects have equal priority
return 0; // ... so return 0.
}

  
public String toString()
{ // The object's string representation
return i.toString(); // is just that of its integer.
}
}

Solutions

Expert Solution

Request : Please upload question 2 seperately . Thank You .

1 . Priority Queue Using Linked List :

Operations on Priority Queue :

  • push() : inserts new data into a queue.
  • pop() : removes the element with highest priority in queue.
  • peek() / top() : gets the element with highest priority in queue without removing it.

The list is so created that the highest priority element is always at the head of the list . The list is arranged in descending order of elements based on their priority . this allows us to remove highest priority of elements in O(1) time.

To insert an element we traverse the list and find the proper position to insert the node so that the overall order of the priority queue is maintained . This makes the PUSH operation take O(N) time .The POP operation and PEEK operation are performed in constant time.

The ALGORITHM is mentioned below :

Algorithm :
PUSH(HEAD, DATA, PRIORITY)
Step 1: Create new node with DATA and PRIORITY
Step 2: Check if HEAD has lower priority. If true follow Steps 3-4 and end. Else goto Step 5.
Step 3: NEW -> NEXT = HEAD
Step 4: HEAD = NEW
Step 5: Set TEMP to head of the list
Step 6: While TEMP -> NEXT != NULL and TEMP -> NEXT -> PRIORITY > PRIORITY
Step 7: TEMP = TEMP -> NEXT
[END OF LOOP]
Step 8: NEW -> NEXT = TEMP -> NEXT
Step 9: TEMP -> NEXT = NEW
Step 10: End

POP(HEAD)
Step 2: Set the head of the list to the next node in the list. HEAD = HEAD -> NEXT.
Step 3: Free the node at the head of the list
Step 4: End

PEEK(HEAD):
Step 1: Return HEAD -> DATA
Step 2: End

Below is the implementation of algorithm.

// Java code to implement Priority Queue  
// using Linked List  
import java.util.* ; 
  
class PriorityQueue 
{ 
    
    
// Node  
 static class Node {  
    int data;  
    
    // Lower values indicate higher priority  
    int priority;  
    
     Node next;  
    
} 
  
static Node node = new Node(); 
    
// Function to Create A New Node  
static Node newNode(int d, int p)  
{  
    Node temp = new Node();  
    temp.data = d;  
    temp.priority = p;  
    temp.next = null;  
    
    return temp;  
}  
    
// Return the value at head  
static int peek(Node head)  
{  
    return (head).data;  
}  
    
// Removes the element with the  
// highest priority form the list  
static Node pop(Node head)  
{  
    Node temp = head;  
    (head)  = (head).next;  
    return head; 
}    
    
// Function to push according to priority  
static Node push(Node head, int d, int p)  
{  
    Node start = (head);  
    
    // Create new Node  
    Node temp = newNode(d, p);  
    
    // Special Case: The head of list has lesser  
    // priority than new node. So insert new  
    // node before head node and change head node.  
    if ((head).priority > p) {  
    
        // Insert New Node before head  
        temp.next = head;  
        (head) = temp;  
    }  
    else {  
    
        // Traverse the list and find a  
        // position to insert new node  
        while (start.next != null &&  
               start.next.priority < p) {  
            start = start.next;  
        }  
    
        // Either at the ends of the list  
        // or at required position  
        temp.next = start.next;  
        start.next = temp;  
    }  
    return head; 
}  
    
// Function to check is list is empty  
static int isEmpty(Node head)  
{  
    return ((head) == null)?1:0;  
}  
    
// Driver code  
public static void main(String args[]) 
{  
    // Create a Priority Queue  
    // 7.4.5.6  
    Node pq = newNode(4, 1);  
    pq =push(pq, 5, 2);  
    pq =push(pq, 6, 3);  
    pq =push(pq, 7, 0);  
    
    while (isEmpty(pq)==0) {  
        System.out.printf("%d ", peek(pq));  
        pq=pop(pq);  
    }  
    
}  
} 
Output:
7 4 5 6 


Related Solutions

1.Implement the generic PriorityQueueInterface in a class named PriorityQueue. Note: it must be named PriorityQueue The...
1.Implement the generic PriorityQueueInterface in a class named PriorityQueue. Note: it must be named PriorityQueue The priority queue MUST be implemented using a linked list. 2 test program checks that a newly constructed priority queue is empty o checks that a queue with one item in it is not empty o checks that items are correctly entered that would go at the front of the queue o checks that items are correctly entered that would go at the end of...
1. Define a class counterType to implement a counter. Your class must have a private data...
1. Define a class counterType to implement a counter. Your class must have a private data member counter of type int and functions to set counter to the value specified by the user, initialize counter to 0, retrieve the value of counter, and increment and decrement counter by one. The value of counter must be nonnegative. 2. Some of the characteristics of a book are the title, author(s), publisher, ISBN, price, and year of publication. Design a class bookType that...
C++ Implement the array based Binary Heap data structure as discussed in class. This structure should...
C++ Implement the array based Binary Heap data structure as discussed in class. This structure should have a couple of constructures (default constructor, and a constructor that takes an array pointer and a size), a method for inserting items into the heap, a method for removing items from the heap, and a method that returns the number of items currently stored in the heap. This implementation should be templated so that it can store any type of data (you may...
You shall implement a class named DnaSequence, which models a sequence of DNA. Requirements: You must...
You shall implement a class named DnaSequence, which models a sequence of DNA. Requirements: You must implement all public constructors and methods described in this documentation. Your class must have only 1 field, and it must be a private char[]. No print statements are allowed anywhere in your class. The constructors require you to discard any character that is not 'A', 'C', 'G', or 'T'. This is very easily accomplished using a regular expression in String.replaceAll: // returns a String...
Java Implement a class MyInteger that contains: • An int data field/instance variable named value that...
Java Implement a class MyInteger that contains: • An int data field/instance variable named value that stores the int value represented by this object. • A constructor that creates a MyInteger object for a default int value. What default value did you choose? What other values did you consider? Why did you make this choice? • A constructor that creates a MyInteger object for a specified int value. • A getter method, valueOf(), that returns value. • A setter method,...
Implement our own stack class patterned after Java's Stack class. Start with a generic class that...
Implement our own stack class patterned after Java's Stack class. Start with a generic class that uses an ArrayList for storage of the elements: public class StackBox<E> { ArrayList<E> stack = new ArrayList<E>(); } Implement the following methods in StackBox: boolean empty() Tests if this stack is empty. E push(E item) Pushes an item onto the top of this stack. Returns item pushed. E pop() Removes the object at the top of this stack and returns that object as the...
Implement a class named stack pair that provides a pair of stacks. Make the class a...
Implement a class named stack pair that provides a pair of stacks. Make the class a template class. So, you will have two files: stack pair.h and stack pair.template, following the style of the text. The basic idea is that two stacks can share a single static array. This may be advantageous if only one of the stacks will be in heavy use at any one time. • The class should have various methods to manipulate the stack: T pop...
StackBox Implement our own stack class patterned after Java's Stack class. Start with a generic class...
StackBox Implement our own stack class patterned after Java's Stack class. Start with a generic class that uses an ArrayList for storage of the elements: public class StackBox<E> { ArrayList<E> stack = new ArrayList<E>(); } Implement the following methods in StackBox: boolean empty() Tests if this stack is empty. E push(E item) Pushes an item onto the top of this stack. Returns item pushed. E pop() Removes the object at the top of this stack and returns that object as...
Implement a class named Parade using an ArrayList, which will manage instances of class Clown. Each...
Implement a class named Parade using an ArrayList, which will manage instances of class Clown. Each Clown only needs to be identified by a String for her/his name. Always join a new Clown to the end of the Parade. Only the Clown at the head of the Parade (the first one) can leave the Parade. Create a test application to demonstrate building a parade of 3 or 4 clowns (include your own name), then removing 1 or 2, then adding...
In Java, design a class named MyInteger. The class contains: An int data field named value...
In Java, design a class named MyInteger. The class contains: An int data field named value that stores the int value represented by this object. A constructor that creates a MyInteger object for the specified int A get method that returns the int Methods isEven(), isOdd(), and isPrime() that return true if the value is even, odd, or prime, respectively. Static methods isEven(int), isOdd(int), and isPrime(int) that return true if the specified value is even, odd, or prime, respectively. Static...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT