Like us on google+

Wednesday, 27 November 2013

Widgets

PRIORITY QUEUE USING DOUBLY LINKED LIST

   

public interface PQInterface
{
public void Insert(int key,Object ele) throws invalidKeyException;
public Object removeMin()throws EmptyQueueException; 
public int Size();
public void display() throws EmptyQueueException; 
public boolean IsEmpty();
}

    public class DLLNode
   {
      private Object ele;
      private int key;
      private DLLNode prev;
      private DLLNode next;
       public DLLNode()
      {
         this(0,null,null,null);
      }
       public DLLNode(int k,Object e,DLLNode p,DLLNode n) 
      {
         key=k;
         ele=e;
         prev=p;
         next=n;
      }
   
       public void setKey(int k)
      {
         key=k;
      }
       public void setElement(Object e)
      {
         ele=e;
      }
       public void setPrev(DLLNode p)
      {
         prev=p;
      }
       public void setNext(DLLNode n)
      {
         next=n;
      }
       public Object getElement()
      {
         return ele;
      }
       public DLLNode getNext()
      {
         return next;
      }
       public DLLNode getPrev()
      {
         return prev;
      }
       public int getKey()
      {
         return key;
      }
   
   }

 public class PriorityQ implements PQInterface
   {
      private DLLNode head=new DLLNode();
      private DLLNode trail=new DLLNode();
      private int size;
       public PriorityQ()
      {
         head.setNext(trail);
         trail.setPrev(head);
         size=0;
      }
       public void Insert(int k,Object o)throws invalidKeyException
      {
         DLLNode temp=new DLLNode(k,o,null,null);
         if(k==0)
            throw new invalidKeyException("invalid key");
         if(IsEmpty())
         {
            head.setNext(temp);
            temp.setPrev(head);
            temp.setNext(trail);
            trail.setPrev(temp);
            size++;
         }
         else
         {
            DLLNode dup=head.getNext();
            while((dup.getKey()<k)&&(dup!=trail))
            {
               dup=dup.getNext();
            }
            DLLNode prev=dup.getPrev();
            temp.setNext(dup);
            dup.setPrev(temp);
            temp.setPrev(prev);
            prev.setNext(temp);
            size++;
         }
      }
       public Object removeMin() throws EmptyQueueException
      {
         if(IsEmpty())
            throw new EmptyQueueException("empty queue");
         else
         {
            DLLNode temp=head.getNext();
            Object e=temp.getElement();
            temp.getNext().setPrev(head);
            head.setNext(temp.getNext());
            size--;      
            return e;
         
         }
      }
       public int Size()
      {
         return size;
      }
       public boolean IsEmpty()
      {
         if(size==0)
            return true;
         else
            return false;
      }
       public void display()throws EmptyQueueException
      {
         if(IsEmpty())
            throw new  EmptyQueueException("empty queue");
         
         else
         {
            DLLNode temp=head.getNext();
            while(temp!=trail)
            {
               System.out.println("Priority = "+temp.getKey()+" Value = "+temp.getElement());
               temp=temp.getNext();
            }
         }
      }
   }

public class EmptyQueueException extends RuntimeException
{
public EmptyQueueException(String str)
{
super(str);
}
}
public class invalidKeyException extends RuntimeException
{
public invalidKeyException(String str)
{
super(str);
}
}

   import java.util.Scanner;
    public class PriorityQueueDemo
   {
       public static void main(String[] args)
      {
         Scanner in=new Scanner(System.in);
         PriorityQ p=new PriorityQ();
         boolean exit=false;
      
         while(exit==false)
         {
            System.out.println("-------------------------------------------");
            System.out.println("1. Insert ");
            System.out.println("2. Delete Minimum");
            System.out.println("3. Size");
            System.out.println("4. Display");
            System.out.println("5. Exit");
            System.out.println("-------------------------------------------");
            System.out.println("Enter choice :");
            int ch=in.nextInt();
            switch(ch)
            {
               case 1: in.nextLine();
                  System.out.println("Enter Name");
                  String item=in.nextLine();
                  System.out.println("Enter the priority");
                  int k=in.nextInt();
                  if(k<=0)
                  {
                     System.out.println("Invalid Priority");
                     break;
                  }
                  p.Insert(k,item);
                  break;
            
            
               case 2: 
                  Object ele=p.removeMin();
                 
                  System.out.println("Popped Element : "+ele);
                  break;
             
             
               case 3:
                  System.out.println(p.Size());
                  break;
           
               case 4:
                  p.display();
                  break;
           
               default: System.out.println("Exting.....");
                  exit=true;
            }
         }
      }
   }

-------------------------------------------------------------------------------
Instead of using getters and setters in the DLLNode class do not declare the member variables as private.....Its your choice..
Any queries do ask......This program may not be the most efficient one but hope so its helpful for the beginners....

SHARE THIS POST   

  • Facebook
  • Twitter
  • Myspace
  • Google Buzz
  • Reddit
  • Stumnleupon
  • Delicious
  • Digg
  • Technorati
About us:
Hi guys Sandesh and Rajesh here ... studing engineering in PESIT started this blog as a google contest and also we love blogging ...Hope u like it ...Encourage us by liking us on g+... Any queries dont hesitate to ask Read More →

0 comments: