In the Stack Module I gave you a project that shows how tocreate a Stack using doubly linked nodes.

StackWithDoublyLinkedNodes.zip

It is a template class that needs the Node class. You must usethis same Node class (no alterations) to create a Queue class .

public class Queue {

}

Use the NetBeans project above as an example.

I have put a driver program (q1.java) in the module. Alsohere:  q1.java This driver program should then run withyour Queue class (no modifications allowed to the driverprogram).

Your Queue class should have at least the following methods: oneor more constructors, enqueue, dequeue, peek, isEmpty, size,makeEmpty.

MUST INCLUDE:

Template Class

constructor

enqueue

dequeue

peek

isEmpty

size

makeEmpty

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

Q1.java

public class Q1 {

public static void main(String[] args) {

Queue myQ = new Queue(); //stringQ

String[] names = {\"harry\", \"mary\", \"mosi\", \"sadie\",\"tom\",\"janice\"};

for (int i=0; i

myQ.enqueue(names[i]);

System.out.println(\"Size is \" + myQ.getSize());

for (int i=0; i<6; i++)

System.out.println(myQ.dequeue()); //test that it also works forintegers

Integer[]numbers={4,5,6,7,8,17,100};

Queue myI = new Queue(); //IntegerQ

for (int i=0; i

myI.enqueue(numbers[i]);

System.out.println(\"Size is \" + myI.getSize());

//Verify it adds (and is an integer Q) and doesn'tconcatenate(String Q)

int total=0;

int tempSize=myI.getSize();

System.out.println(\"Integers in Queue are:\");

for (int i=0; i

//cannot use getSize() here because it changes every time youdequeue

{Integer val = myI.dequeue();

System.out.print(val+ \" \");

total=total+val;

}

System.out.println(\"\nTotal is:\" + total);

}

}

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

StackWithDoublyLinkedNodes.java

public class StackWithDoublyLinkedNodes {

/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
Stack s = new Stack();

Integer[] x = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

for (int i = 0; i < x.length; i++) {
Integer t = x[i];
s.push(t);
}
while (!s.isEmpty()) {
System.out.println(s.pop());
}
  
//verify the stack is empty and that
//we took care of the issues
//of trying to pop an empty stack
//and peek at the top of an empty stack
System.out.println(s.pop());   
System.out.println(s.peek());
System.out.println(\"********************************\");
//repeat using a stack of Strings
System.out.println(\"Repeat using a Stack of Strings\");
Stack s1 = new Stack();

String[] x1 = {\"Hi\", \"Bye\", \"One\", \"Four\",\"CMPSC\"};

for (int i = 0; i < x1.length; i++) {
String t1 = x1[i];
s1.push(t1);
}
while (!s1.isEmpty()) {
System.out.println(s1.pop());
}
}

}

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

Stack.java

public class Stack {

private Node head;
private int size;

Stack() {
head = null;
size = 0;
}

public void push(T newItem) {
Node temp = new Node(newItem);
if (this.isEmpty()) {
head = temp;
} else {
temp.setNext(head);
head.setPrev(temp);
head = temp;
}
size++;
}

public T pop() {
if (isEmpty()) {
return (T)\"Empty List\";
}
T temp = (T) head.getItem();
head = head.getNext();
if (head != null) {
head.setPrev(null);
}
size--;
return temp;
}

public T peek() {
if(isEmpty()){
return (T)\"Empty List\";
}
return (T) head.getItem();
}

public int getSize() {
return size;
}

public boolean isEmpty() {
return size == 0;
}

}

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

Node.java

public class Node {
//Node makes item, next, and prev all private
//and therefore has to provide accessors
//and mutators (gets and sets)
private T item;
private Node next;
private Node prev;

Node(T newItem) {
item = newItem;
next = null;
prev = null;
}

Node(T newItem, Node nextNode, Node prevNode) {
item = newItem;
next = nextNode;
prev = prevNode;
}

/**
* @return the item
*/
public T getItem() {
return item;
}

/**
* @param item the item to set
*/
public void setItem(T item) {
this.item = item;
}

/**
* @return the next
*/
public Node getNext() {
return next;
}

/**
* @param next the next to set
*/
public void setNext(Node next) {
this.next = next;
}

/**
* @return the prev
*/
public Node getPrev() {
return prev;
}

/**
* @param prev the prev to set
*/
public void setPrev(Node prev) {
this.prev = prev;
}

}