5.1 Implement a priority queue based on a sorted linked list. The remove operati

Question

5.1

Implement a priority queue based on a sorted linked list. The remove operation on the priority queue should remove the item with the smallest key.

5.2

Implement a deque based on a doubly linked list. (See programming project 4.2 - Create a Deque class based on the discussion of deques (double-ended queues) in this chapter. It should include insertLeft(), insertRight(), removeLeft(), removeRight(), isEmpty(), and isFull() methods. It will need to support wraparound at the end of the array, as queues do.) The user should be able to carry out the normal operations on the deque.

Explanation / Answer

OUTPUT:

~/PriorityQSort$ java PriorityQueue
Inserted elements at random into the queue such that Priority queue contains highest element at the end
sorted List based on Priority Queue . removing minimum element from the front of the list and displaying:
10 32 35 37 45 47 56 63 67 84

Efficient way of implementing a Priority queue is by using a heap O(nlog(n))

**********************************************************************************************************************************************************************************************************************************************************************************************

import java.io.*;
class Node
{
public int data;
public Node next;
public Node previous;
public Node(int x)
{
data=x;
}
public void displayNode()
{
System.out.print(data+" ");
}
}
class DoublyLinkList
{
private Node first;
private Node last;
public DoublyLinkList()
{
first=null;
last=null;
}
public void insertFirst(int x)
{
Node newNode=new Node(x);
newNode.next=null;
if(isEmpty())
last=newNode;
else
first.previous=newNode;
newNode.next=first;
first=newNode;
}
public void insertLast(int x)
{
Node newNode=new Node(x);
newNode.next=null;
if(isEmpty())
first=newNode;
else
{
last.next=newNode;
newNode.previous=last;
}
last=newNode;
}
public int deleteFirst()
{
int t=first.data;
if(first.next==null)
last=null;
else
first.next.previous=null;
first=first.next;
return t;
}
public int deleteLast()
{
int t=last.data;
if(first.next==null)
first=null;
else
last.previous.next=null;
last=last.previous;
return t;
}
public boolean isEmpty()
{
return(first==null);
}
public void displayForward()
{
Node current=first;
while(current!=null)
{
current.displayNode();
current=current.next;
}
}
public void displayBackward()
{
Node current=last;
while(current!=null)
{
current.displayNode();
current=current.previous;
}
}
}
class Deque
{
private DoublyLinkList l;
public Deque()
{
l=new DoublyLinkList();
}
public void insertLeft(int x)
{
l.insertFirst(x);
System.out.print("Inserted to Front ");
}
public void insertRight(int x)
{
l.insertLast(x);
System.out.print("Inserted to Rear ");
}
public int deleteLeft()
{
return l.deleteFirst();
}
public int deleteRight()
{
return l.deleteLast();
}
public boolean isQueueEmpty()
{
return l.isEmpty();
}
public void displayFromFront()
{
l.displayForward();
}
public void displayFromRear()
{
l.displayBackward();
}
}
class DequeApp
{
public static void main(String args[])throws IOException
{
String ch="y";
DataInputStream inp=new DataInputStream(System.in);
int n,d;
Deque q=new Deque();
while(ch.equals("y"))
{
System.out.println("MENU");
System.out.println("--------");
System.out.println("1.Insert at Front");
System.out.println("2.Insert at Rear");
System.out.println("3.Delete at Front");
System.out.println("4.Delete at Rear");
System.out.println("5.Display From Front");
System.out.println("6.Display From Rear");
System.out.println("Enter your choice ");
n=Integer.parseInt(inp.readLine());
switch(n)
{
case 1: System.out.println("Enter the data ");
d=Integer.parseInt(inp.readLine());
q.insertLeft(d);
break;
case 2: System.out.println("Enter the data ");
d=Integer.parseInt(inp.readLine());
q.insertRight(d);
break;
case 3: if(q.isQueueEmpty())
System.out.print("Deque is Empty ");
else
{
d=q.deleteLeft();
System.out.print("Deleted data:- "+d);
}
break;
case 4: if(q.isQueueEmpty())
System.out.print("Deque is Empty ");
else
{
d=q.deleteRight();
System.out.print("Deleted data:- "+d);
}
break;
case 5: if(q.isQueueEmpty())
System.out.print("Deque is Empty ");
else
{
System.out.print("Datas in Deque From Front:- ");
q.displayFromFront();
}
break;
case 6: if(q.isQueueEmpty())
System.out.print("Deque is Empty ");
else
{
System.out.print("Datas in Deque From Rear:- ");
q.displayFromRear();
}
break;
default: System.out.print("Invalid choice ");
}
System.out.println("");
System.out.print("Enter y to continue ");
ch=inp.readLine();
}
}
}

Related Questions

Navigate

• Browse (All)
• Browse 5
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.