In: Computer Science
#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.
}
}
Request : Please upload question 2 seperately . Thank You .
1 . Priority Queue Using Linked List :
Operations on Priority Queue :
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