Homework SourseIn java I want you to implement a Data Structure known as a
In java , I want you to implement a Data Structure known as a Doubly-Ended-Queue. it is a “fair” data structure in that it implements a FIFO (First In First Out ) behavior. As such, it is often used to implement various wait lists in computer systems. For example, jobs waiting to use the CPU, jobs waiting for a printer, jobs waiting to be placed into RAM for execution. In short, whenever we want a fair strategy for waiting we use queues.
A DEQUE (Doubly-ended-queue) is a related data structure. Although similar to a Queue, it differs in that it allows for insertions AND deletions from either end of the list (both the front and the rear).
Your implementation MUST use a doubly-linked-list implementation. You may not use a static array implementation.
Thus, a Deque is a List but it is one which only concerns itself with the first and last positions for any insertion or deletion. The 6 operations supported are :
public void insertFront( int item ) - insert the given item (as a node) into the first position of the Deque.
public void insertRear( int item ) - insert the given item (as a node) into the last position of the Deque.
public int deleteFront( ) - delete and return the element stored in the first node of the Deque.
public int deletRear( ) – delete and return the element stored in the last node of the Deque.
public boolean isempty( ) - returns true if the Deque is currently empty or false if it is not.
public void printDeque( ) - print the integers from the list, one per line, from the first element through to the last in order.
Classes
Your program must implement the following 3 classes. public class dequeDriver
This class will contain your program’s main method. It will need to declare a deque object and process input as indicated below.
Your program should prompt the user for the path of an input file. It should open the file for input and process it line by line. Each line of the input file will have one of the following forms.
PR
IF <int value>
IR <int value>
DF
DR
The meanings of each input is as follows:
PR - print the current contents of the deque from front to rear using the printDeque( ) method of the deque object.
IF <val> - insert the given int value into the front of the deque.
IR <val> - insert the given int value into the rear of the deque.
DF - delete the front value from the deque.
DR – delete the rear element of the deque.
Below is an example input file that your program should be able to process.
PR
IF 4
IF 5
IF 6
IR 7
PR
DR
PR
DF
PR
The output for the input file shown above is :
EMPTY DEQUE
----- Front -----
6
5
4
7
----- Rear -----
----- Front -----
6
5
4
----- Rear -----
----- Front -----
5
4
----- Rear -----
public class dequeNode
This class will implement the linked nodes that will be used to implement the deque itself.
It should have the following protected data members.
protected dequeNode next; // next pointer to next node
protected dequeNode prev; // previous pointer to previous node
protected int val; // the integer value stored within the dequeNode.
The following methods should be supported :
public dequeNode getNext( ) - return the next field of the current dequeNode.
public dequeNode getPrev( ) – return the prev field of the current dequeNode.
public void setNext( dequeNode n ) – set the next field of the current dequeNode to n.
public void setPrev( dequeNode p ) – set the prev field of the current dequenode to p.
public int getVal( ) - simply returns the integer value stored in the val field.
The class should also have a constructor that expects an integer argument which will be placed into the integer field val.
public dequeNode( int v )
public class deque
This is the actual deque structure. It will consist of a variable of type dequeNode named elts.
protected dequeNode elts; // the pointer to the first element in deque.
The class will need a default constructor which takes no arguments and sets the dequeNode elts to null.
public deque( ) - set elts member to null for empty deque
The other methods are as described earlier….
public void insertFront( int item ) - insert the given item (as a node) into the first position of the Deque.
public void insertRear( int item ) - insert the given item (as a node) into the last position of the Deque.
public int deleteFront( ) - delete and return the element stored in the first node of the Deque.
public int deletRear( ) – delete and return the element stored in the last node of the Deque.
public boolean isempty( ) - returns true if the Deque is currently empty or false if it is not.
public void printDeque( ) - print the integers from the list, one per line, from the first element through to the last in order.
Solution
import java.io.File;
import java.util.Scanner;
import java.util.ArrayList;
public class DequeDriver {
public static void main(String[] args) {
// Will read a .txt file of valid commands and perform them on a deque.
Deque deque = new Deque();
Scanner input = new Scanner(System.in);
System.out.println(\"Please enter a file path: \" );
try {
Scanner fileReader = new Scanner(new File(input.nextLine()));
ArrayList<String> commands = new ArrayList<>();
while (fileReader.hasNextLine()) {
commands.add(fileReader.nextLine());
}
for (int i = 0; i < commands.size(); i++) {
if (commands.get(i).equals(\"PR\")) {
if (deque.isempty()) {
System.out.println(\"EMPTY DEQUE\");
}
else {
System.out.println(\"-----Front-----\");
deque.printDeque();
System.out.println(\"-----Rear-----\");
}
}
if (commands.get(i).substring(0, 2).equals(\"IR\")) {
deque.insertRear(Integer.parseInt(commands.get(i).substring(3,commands.get(i).length())));
}
if (commands.get(i).substring(0, 2).equals(\"IF\")) {
deque.insertFront(Integer.parseInt(commands.get(i).substring(3,commands.get(i).length())));
}
if (commands.get(i).equals(\"DF\")) {
deque.deleteFront();
}
if (commands.get(i).equals(\"DR\")) {
deque.deleteRear();
}
}
fileReader.close();
}
catch (Exception e) { // Deque methods are secure, so any exception thrown will be from input.
System.out.println(\"Sorry, your input was invalid. Try running again with different input.\");
e.printStackTrace();
input.close();
return;
}
input.close();
}
}
Deque.java
public class Deque {
private DequeNode elts; // The pointer to the first element in the deque
public void deque( ) { // Set elts member to null for empty deque
elts = null;
}
public void insertFront( int item ) {
// Insert the given item (as a node) into the first position of the Deque.
DequeNode node = new DequeNode(item);
if (this.isempty()) // Test for empty deque
elts = node;
else {
DequeNode temp = elts;
elts = node;
elts.setNext(temp);
if (temp.getPrev() == null) { // Test for deque with one item
elts.setPrev(temp);
temp.setNext(elts);
}
else {
elts.setPrev(temp.getPrev());
temp.getPrev().setNext(elts);
}
temp.setPrev(elts);
}
}
public void insertRear( int item ) {
// Insert the given item (as a node) into the last position of the Deque.
DequeNode node = new DequeNode(item);
if (this.isempty()) // Test for empty deque
elts = node;
else {
node.setNext(elts);
if (elts.getPrev() == null) { // Test for deque with one item
node.setPrev(elts);
elts.setNext(node);
}
else {
DequeNode temp = elts.getPrev();
node.setPrev(temp);
temp.setNext(node);
}
elts.setPrev(node);
}
}
public int deleteFront( ) {
// Delete and return the element stored in the first node of the Deque.
if (!this.isempty()) {
int val = elts.getVal();
if (elts.getPrev() == null) // If there\'s only 1 item, just delete it.
elts = null;
else {
elts.getPrev().setNext(elts.getNext());
elts.getNext().setPrev(elts.getPrev());
elts = elts.getNext();
}
return val;
}
else {
System.out.println(\"Deque is empty! Returning 0...\");
return 0;
}
}
public int deleteRear( ) {
// Delete and return the element stored in the last node of the Deque.
if (!this.isempty()) {
int val;
if (elts.getPrev() == null) { // If there\'s only 1 item, just delete it.
val = elts.getVal();
elts = null;
return val;
}
else {
val = elts.getPrev().getVal();
DequeNode oldRear = elts.getPrev();
oldRear.getPrev().setNext(elts);
elts.setPrev(oldRear.getPrev());
return val;
}
}
else {
System.out.println(\"Deque is empty! Returning 0...\");
return 0;
}
}
public boolean isempty( ) {
// Returns true if the Deque is currently empty or false if it is not.
return (elts == null);
}
public void printDeque( ) {
// Print the integers from the list, one per line, from the first element through to the last in order.
if (this.isempty())
System.out.println(\"EMPTY DEQUE\");
else {
DequeNode index = elts;
System.out.println(elts.getVal());
if (index.getNext() != null) {
index = index.getNext();
while (index != elts) {
System.out.println(index.getVal());
index = index.getNext();
}
}
}
}
}
DequeNode.java
package program1;
public class DequeNode {
protected DequeNode next; // Next pointer to next node
protected DequeNode prev; // Previous pointer to previous node
protected int val; // The integer value stored within the dequeNode.
public DequeNode() {
}
public DequeNode(int val) {
this.val = val;
}
public DequeNode getNext( ) { // Return the next field of the current dequeNode.
return next;
}
public DequeNode getPrev( ) { // Return the prev field of the current dequeNode.
return prev;
}
public void setNext( DequeNode n ) { // Set the next field of the current dequeNode to n.
next = n;
}
public void setPrev( DequeNode p ) { // Set the prev field of the current dequenode to p.
prev = p;
}
public int getVal( ) { // Simply returns the integer value stored in the val field.
return val;
}
}
