DSA Assignment-7

Queue is an ordered set of elements in which insertions are from the rear and deletions are from the front. It is a First in First Out structure (FIFO). 
PART-I 
Static Implementation (Array Implementation) 
A Queue is implemented statically by using an array of size MAX to hold the elements and it has two ends (integers) – front and rear. The ‘front’ stores the position of the current front element and ‘rear’ stores the position of the current rear element of the queue. The Queue elements can be integers, characters, strings or user defined data types. 
The operations to be performed on a Queue are 
public static void insert(int Q[])-adding an element x to the rear end of the queue Q 
public static void delete(int Q[])-deletes the element from the front of the queue Q 
public static void display(int Q[])-display all the elements of the queue Q. 
public static boolean is_full() -check if the queue  is full  or not. 
public static boolean is_empty() -check if the queue is empty or not. 
Write a menu driven Java Program using class, methods and array, to construct a Queue and implement the above five operations. 
The template for menu driven java program to use the above Queue and invoke the required methods to perform different operations is given below.
import java.util.Scanner; 
public class QueueDemo1 {  
 public static void insert(int Q[]) 
 {  ---- 
  --- 
 }  
/* Write the code for remaining user defined methods*/
public static final int MAX=5; 
 public static int front=-1; 
 public static int rear=-1; 
 public static void main(String[] args) { 
  Scanner sc=new Scanner(System.in); 
  int queue[]=new int[MAX];
    while(true) 
    {
   System.out.println("***MENU***"); 
   System.out.println("0: Exit"); 
   System.out.println("1: Insert"); 
   System.out.println("2: Delete"); 
   System.out.println("3: Display"); 
   System.out.println("Enter your choice"); 
   int choice=sc.nextInt(); 
   switch(choice) 
    { 
    case 0:  
      System.exit(0); 
    case 1:  
      insert(queue); 
      break; -----   
               -----
    default: 
     System.out.println("Invalid choice"); 
    } 
   } 
 } 
} 
import java.util.*;



public class Queue1 {



    public static final int MAX = 5;

    public static int front = -1;

    public static int rear = -1;



    public static void insert(int Q[]) {

        if (is_full()) {

            System.out.println("Queue is full. Insertion not possible.");

            return;

        } else {

            Scanner sc = new Scanner(System.in);

            System.out.print("Enter the element to be inserted: ");

            Q[++rear] = sc.nextInt();

            if (front == -1) {

                front = 0;

            }

            System.out.println("Element inserted successfully.");

        }

    }



    public static void delete(int Q[]) {

        if (is_empty()) {

            System.out.println("Queue is empty. Deletion not possible.");

            return;

        } else {

            System.out.println("Element deleted: " + Q[front]);

            if (front == rear) {

                front = rear = -1;  // Queue is now empty

            } else {

                front++;

            }

        }

    }



    public static void display(int Q[]) {

        if (is_empty()) {

            System.out.println("Queue is empty.");

            return;

        }

        System.out.print("Queue elements: ");

        for (int i = front; i <= rear; i++) {

            System.out.print(Q[i] + " ");

        }

        System.out.println();

    }



    public static boolean is_full() {

        return rear == MAX - 1;

    }



    public static boolean is_empty() {

        return front == -1;

    }



    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int queue[] = new int[MAX];



        while (true) {

            System.out.println("***MENU***");

            System.out.println("0: Exit");

            System.out.println("1: Insert");

            System.out.println("2: Delete");

            System.out.println("3: Display");

            System.out.println("Enter your choice:");

            int choice = sc.nextInt();

            switch (choice) {

                case 0:

                    System.exit(0);

                case 1:

                    insert(queue);

                    break;

                case 2:

                    delete(queue);

                    break;

                case 3:

                    display(queue);

                    break;

                default:

                    System.out.println("Invalid choice");

            }

        }

    }

}

Output:*****MENU*****
0: Exit
1: Insert
2: Delete
3: Display
--------------------
Enter your choice: 1
Enter the element to insert: 5
Element inserted.
*****MENU*****
0: Exit
1: Insert
2: Delete
3: Display
--------------------
Enter your choice: 1
Enter the element to insert: 10
Element inserted.
*****MENU*****
0: Exit
1: Insert
2: Delete
3: Display
--------------------
Enter your choice: 1
Enter the element to insert: 15
Element inserted.
*****MENU*****
0: Exit
1: Insert
2: Delete
3: Display
--------------------
Enter your choice: 2
Deleted element: 5
*****MENU*****
0: Exit
1: Insert
2: Delete
3: Display
--------------------
Enter your choice: 3
Queue elements: [10, 15]
*****MENU*****
0: Exit
1: Insert
2: Delete
3: Display
--------------------
Enter your choice: 0


PART-II 
Dynamic Implementation (Linked List Implementation) 
A Queue is implemented dynamically by using a Linked list where each node in the linked list has two parts, the data element and the reference to the next element of the queue.  
The class definition of Node is given below. 
class Node 
{ 
int info; 
Node next; 
} 
The Queue elements can be integers, characters, strings or user defined types. There is no restriction on how big the Queue can grow. 
The operations to be performed on a Queue: 
public static Node insert (Node rear, Node front) - adding an element x to the queue 
Q requires creation of node containing x and putting it next to the rear and rear points to the newly added element.  
public static Node delete (Node rear, Node front) - deletes the front node from the queue Q 
public static void display (Node rear, Node front)-display all the elements of the queue Q. 
Write a menu driven Java Program using class, methods and list, to construct a Queue and implement the above three operations. The code template for constructing the above Queue and performing the required operation is   
given below. 
import java.util.Scanner; 
public class QueueDemo2 { 
  
 public static Node insert(Node rear, Node front) 
 { 
  ---- ---- 
   
 }  
 /* Write the code for remaining user defined methods*/ 
 
  
 public static void main(String[] args) { 
   
  Scanner sc=new Scanner(System.in); 
  Node rear,front; 
  --- --- 
   
  while(true) 
  { 
   System.out.println("****MENU****"); 
   System.out.println("0:Exit"); 
   System.out.println("1:Insert"); 
   System.out.println("2:Delete"); 
   System.out.println("3:Display"); 
   System.out.println("Enter your choice"); 
   int choice=sc.nextInt(); 
   switch(choice) 
   { 
   case 0: 
    System.exit(0); 
     
   case 1: 
    front=insert(rear,front); 
      --- 
    break; 
 
     
   case 2: 
    front=delete(rear,front); 
    --- 
     break; 
    
    --- 
 
   default: 
    System.out.println("Wrong choice"); 
        
   } 
  } 
  
 } 
}
import java.util.Scanner;



class Node {

    int info;

    Node next;



    Node(int info) {

        this.info = info;

        this.next = null;

    }

}



public class Queue2 {

    public static Node rear = null;

    public static Node front = null;



    public static void insert() {

        Scanner sc = new Scanner(System.in);

        Node p = new Node(0);

        System.out.print("Enter the element to insert: ");

        p.info = sc.nextInt();

        System.out.println("Element inserted.");



        if (front == null) {

            front = p;

            rear = p;

        } else {

            rear.next = p;

            rear = p;

        }

    }



    public static void delete() {

        if (front == null) {

            System.out.println("Queue is empty!");

        } else {

            System.out.println("Deleted element: " + front.info);

            front = front.next;

            if (front == null) {

                rear = null;

            }

        }

    }



    public static void display() {

        if (front == null) {

            System.out.println("Queue is empty.");

            return;

        }

        Node p = front;

        System.out.print("Queue elements: [");

        while (p.next != null) {

            System.out.print(p.info + ", ");

            p = p.next;

        }

        System.out.println(p.info + "]");

    }



    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);



        while (true) {

            System.out.println("*****MENU*****");

            System.out.println("0: Exit");

            System.out.println("1: Insert");

            System.out.println("2: Delete");

            System.out.println("3: Display");

            System.out.println("--------------------");

            System.out.print("Enter your choice: ");

            int choice = sc.nextInt();

            switch (choice) {

                case 0:

                    System.exit(0);

                case 1:

                    insert();

                    break;

                case 2:

                    delete();

                    break;

                case 3:

                    display();

                    break;

                default:

                    System.out.println("Wrong choice");

            }

        }

    }

}

Output: Same as part 1 output