Saturday, 9 July 2011

Queue Implementation using Linked List in java

Here I am creating 3 files in order to implement the Queue using Linked list in java

1.QueueADT.java                   2. LLQueue.java              3. LLQueue_Test.java

//  QueueADT.java

package Queue;
public interface QueueADT<E>
{
    public Object getFront();
    public void enqueue(Object a);
    public Object dequeue();
    public boolean isEmpty();
   
}

// 2. LLQueu.java

import java.util.Scanner;
import Queue.*;
import java.util.*;
public class LLQueue<E> implements QueueADT<E>
{
    public ListNode front;
    public ListNode back;
   
    /*public LLQueue()
    {
        front=back=null;
    }*/
    // Test if the queue is logically empty, return true if empty else false
    public boolean isEmpty()
    {

        return front==null;
    }

    // Insert a new item in to queue;
    public void enqueue(Object x)
    {
        ListNode n=new ListNode(x);
        if(isEmpty())
            back=front=n;
        else
            back=back.next=n;
    }

    //Retun and remove the lest recently inserted item from the queue
   
    public Object dequeue()
    {
        if(isEmpty())
            throw new UnderflowException("Queue is empty");
        Object val=front.element;
        front=front.next;
        return val;
    }
   
    // get the least recently inserted element from the queue;

    public Object getFront()
    {
        if(isEmpty())
            throw new UnderflowException("Queue is empty");
        else
       
        return front.element;
    }
    // Make queue empty

    public void makeEmpty()
    {
        back=front=null;
    }
   
    // exit program
    public void exit()
    {
        System.exit(0);
    }
   
    // display all the itmes in the queue
    public void display()
    {
        if(!isEmpty())
        {

            ListNode current=front;
            while (current!=null)
            {
                System.out.println(current.element);
                current=current.next;
            }
        }
        System.out.println("\nQueue is empty\n");
    }
   
   
};

//Exception class for access in empty containers
 //* such as stacks, queues, and priority queues.
class UnderflowException extends RuntimeException
    {
        
        // Construct this exception object
        // Messages the error message
        public UnderflowException( String message )
        {
            super( message );
        }
    }
// class List Node
class ListNode
{
    public Object element;
    public ListNode next;

    // constructors
    public ListNode(Object Elem)
    {
        element=Elem;
    }

    public ListNode(ListNode n, Object Ele)
    {
        element=Ele;
        next=n;
    }

};
 
// LLQueue_Test.java

import java.util.*;
class Queue_Test
{
    public static void main(String[] args)
    {
        int choice,el;
     Scanner sc=new Scanner(System.in);
     LLQueue LLQ=new LLQueue();
        //size=sc.nextInt();
       
        while (true)
        {
            System.out.println("Please enter you choice\n");
            System.out.println(" 1 for insert or enqueue \n 2 for is Queue empty \n 3 to get front element \n 4 to dequeue the element");
            System.out.println(" 5 to display \n 6 to make Queue empty\n 7 to exit  ");
            System.out.print("\n Choice --> ");
            choice=sc.nextInt();
            switch (choice)
            {
            case 1:
                System.out.print("Please enter Enter your element --> ");
                el=sc.nextInt();
                LLQ.enqueue(el);
                System.out.println();
                break;
            case 2:
                System.out.println(LLQ.isEmpty());
            break;
            case 3:
                if(!LLQ.isEmpty())
                {

                    System.out.println("Front element is ");
                    System.out.println(LLQ.getFront());
                }
                else
                    System.out.println("\nArray stack is empty\n");
                break;
            case 4:
                System.out.println("\nPoped element is ");
                System.out.print(LLQ.dequeue());
                System.out.println();
                break;
            case 5:
                LLQ.display();
                break;
            case 6:
                LLQ.makeEmpty();
            break;
            case 7:
                LLQ.exit();
            default:
                System.out.println("Please choose correct choice");
               
           
            }
        }
    }
}

1 comment: