Question

Write an efficient java program to implement an integer doubly linked list Dequeue which insertion and deletion can be than at either end. You have to write 6 methods: add front, delete front, add rear, delete rear, print forward (left to right) and print backward (right to left). After each addition or deletion dequeue elements are printed forward or backward respectively.

Your main method should be as follow:

public static void main(String args[]) {

xxxxx dq = new xxxxx (); // xxxxx is the first 5 characters of your last name

try{

Scanner inf = new Scanner (System.in);                    

// Read input from KB/ File

while(inf.hasNext()){

// read operation type (optype):

//1:add front, 2:delete front, 3:add rear and delete rear            

optype = inf.nextInt();

       switch (optype){

                             case 1: x = inf.nextInt(); // read x

                                       dq.addfront(x);

                    dq.printfwd(); // print forward dequeuer elements

                                       break;

                             case 2: j = dq.delfront();// delete front

                                       if(j……….

                                       dq.printbwd(); // print backward dequeuer elements

                                       break;

                             case 3: x = inf.nextInt(); // read x

                                       dq.addrear(x);

                    dq.printfwd(); // print forward dequeuer elements

                                       break;

                             default: j = dq.delrear();// delete front

                                       if(j……….

                                       dq.printbwd(); // print backward dequeuer elements

       }//end switch

}// end while

inf.close();// close input file

}catch (Exception e) {prt("\nException " + e + "\n");}

}// end main method      

NOTE: Projects will not be graded if:

Your complete project is not in a SINGLE xxxxx.java file, where xxxxx is the first 5 characters of your last name.

It does not read input from System.in. i.e. command prompt.

Sample data file can be as follow:

1 100 2 2 3 500 3 600 3 250 4 1 150 1 220 2 4 1 50 3 55 1 20 1 80 3 90

Answer 1

Java Code:

package queue;

import java.util.Scanner;

import queue.Deque.DoublyLinkedListDeque.Node;

public class Deque {
public static void main(String args[]) { //main class
DoublyLinkedListDeque dq = new DoublyLinkedListDeque(); //create a queue object
try {
Scanner inf = new Scanner(System.in);
while (inf.hasNext()) { //loop through the input
int optype = inf.nextInt(); //store option
int x;
   Node j;
   switch (optype) { //check which option to excute
case 1:
x = inf.nextInt(); //get the number
dq.addfront(x); //call add to front
dq.printfwd(); //call print from front to rear
break;
case 2:
j = dq.delfront(); //delete the node at the front
if (j != null) {
   dq.printbwd(); //if successful print from rear to front
}
break;
case 3:
x = inf.nextInt(); //get the number
dq.addrear(x); //add to rear
dq.printfwd(); //call print from front to rear
break;
default:
j = dq.delrear(); //delete rear node
if (j != null) {
   dq.printbwd(); //if successful print from rear to front
}
}
}
inf.close();
} catch (Exception e) {
System.out.println("\nException " + e + "\n"); //catch any exception thrown
}
}

public static class DoublyLinkedListDeque { //creating a queue class
private Node head; //to store the head of the queue
private Node tail; //to store the tail of the queue

class Node { //creating a class node
int data;
Node next; //to reference the next element in the queue
Node prev; //to reference the previous element in the queue
Node(int data) {
   this.data = data; //contructor to create a new node
}
}
public DoublyLinkedListDeque() { //set the head and tail to null at the beginning
this.head = null;
this.tail = null;
}

public boolean isEmpty() { //check if queue is empty
return head == null;
}

public void printfwd() { //method to print from front to rear
   System.out.println("Printing front to rear");
Node currentNode = head;
while (currentNode != null) {
System.out.print(currentNode.data + " "); //print the node
currentNode = currentNode.next;
}
System.out.println("");
System.out.println("");
}

public void printbwd() { //method to print from rear to front
   System.out.println("Printing rear to front");
Node currentNode = tail;
while (currentNode != null) {
System.out.print(currentNode.data + " "); //print the node
currentNode = currentNode.prev;
}
System.out.println("");
System.out.println("");
}

public void addfront(int data) { //method to add to front of the queue
Node newNode = new Node(data);
if (isEmpty()) {
tail = newNode; //if queue is empty tail should should point to the head
} else {
head.prev = newNode; //else set the newNode at the previous position of the current head
newNode.next = head;
}
System.out.println("Adding "+ data +" at front");
System.out.println("");
head = newNode; //set the new node as the head
}

public void addrear(int data) { //method to add to the rear of the queue
Node newNode = new Node(data);
if (isEmpty()) {
head = newNode; //if queue is empty head should point to the tail
} else {
tail.next = newNode; //else set the newNode at the next position of the current tail
newNode.prev = tail;
}
System.out.println("Adding "+ data +" at rear");
System.out.println("");
tail = newNode; //set the new node as the tail
}

public Node delfront() { //method to delete the node at the front
   System.out.println("Deleting at front");
   System.out.println("");
if (head == null) {
System.out.println("Deque is empty");
System.out.println("");
return null; //if queue is empty return null
}
Node first = head; //get the head
if (head.next == null) {
tail = null; //if there is only one node in the queue set the tail as null
} else {
head.next.prev = null; //else set the previous of the next element of the head as null (this is to deference the head)
}
head = head.next; //move the head to the next position
return first;
}

public Node delrear() { //method to delete the node the rear
   System.out.println("Deleting at rear");
   System.out.println("");
if (tail == null) {
System.out.println("Deque is empty");
System.out.println("");
return null; // if queue is empty return null
}
Node last = tail; //get the tail
if (head.next == null) {
head = null; //if there is only one node in the queue set the head as null
} else {
tail.prev.next = null; //set the next node of the previous of the tail as null (this is to deference the tail)
}
tail = tail.prev; //move the tail to the previous position
return last;
}

}
}

Sample Output:

1 100 2 2 3 500 3 600 3 250 4 1 150 1 220 2 4 1 50 3 55 1 20 1 80 3 90
Adding 100 at front

Printing front to rear
100

Deleting at front

Printing rear to front

Deleting at front

Deque is empty

Adding 500 at rear

Printing front to rear
500

Adding 600 at rear

Printing front to rear
500 600

Adding 250 at rear

Printing front to rear
500 600 250

Deleting at rear

Printing rear to front
600 500

Adding 150 at front

Printing front to rear
150 500 600

Adding 220 at front

Printing front to rear
220 150 500 600

Deleting at front

Printing rear to front
600 500 150

Deleting at rear

Printing rear to front
500 150

Adding 50 at front

Printing front to rear
50 150 500

Adding 55 at rear

Printing front to rear
50 150 500 55

Adding 20 at front

Printing front to rear
20 50 150 500 55

Adding 80 at front

Printing front to rear
80 20 50 150 500 55

Adding 90 at rear

Printing front to rear
80 20 50 150 500 55 90