Write in Java:

Create 2 new ADTs (aka Abstract Data Types): Stack and Queue. Additionally, make a class with a main method that tests the Stack and Queue classes and demonstrates that they work then solves a few problems (below) with stacks and queues.

HINT: Stacks and Queues can be thought of as special cases of lists. They will be very easy for you to implement by making a copy of your Linked List class, renaming and editing some methods, and deleting what you dont need. I have attached a copy of my Linked List class below.

Your stack should include the following methods:

pushadd item to top of stack

popremove item from top of stack

peekuse top item in stack without removing it

Your queue should include the following methods:

enqueueadd item to the front of the list

dequeueremove item from the end of the queue

peekuse item from end of the queue without removing it

In the class in which you implement your main method, you should make methods that solve the following problems. In solving the problems you can only use the stack & queue methods described above. It doesnt count as solved if you bypass the stack & queue methods by accessing other linked list methods that you may have in your stack.

1. Move the contents of a stack to a queue. Maintain order so that if you were to pop and print all of the items from the stack and dequeue and print all the items from the queue it would print the same thing.

2. Move all the contents of a queue to a stack. Maintain order so that if you were to pop and print of the items from the stack and dequeue and print all the items from the queue it would print the same thing.

3. Move the contents of a stack to another stack. Maintain order so that if you were to pop and print the items of both stacks, they would print the same thing.

The copy of the Linked List class to use is:

import java.util.*;

public class NodeH3 { private String value; private NodeH3 back; private NodeH3 next;

public String getValue() { return value; } public NodeH3 getBack() { return back; } public NodeH3 getNext() { return next; } public void setValue(String val) { value = val; } public void setBack(NodeH3 n) { back = n; } public void setNext(NodeH3 n) { next = n; } }

public class NodelistH3 { private NodeH3 front; private NodeH3 last; private int size;

NodelistH3() { front = new NodeH3(); last = new NodeH3(); front.setNext(last); last.setBack(front); size = 0; }

public int getSize() { return size; }

public NodeH3 getFront() { return front; }

public NodeH3 getLast() { return last; } public void insert(String string) { NodeH3 n = new NodeH3(); n.setValue(string); if(size == 0) { front.setNext(n); n.setBack(front); n.setNext(last); last.setBack(n); } else { NodeH3 temp1 = front; NodeH3 temp2 = front.getNext();

while(temp2 != last) { int ret = temp2.getValue().compareTo(string); if( ret > 0) { break; } else if(ret < 0 ) { temp1 = temp2; temp2 = temp2.getNext(); } else return; } temp1.setNext(n); n.setNext(temp2); n.setBack(temp1); temp2.setBack(n); } size++; } public NodeH3 search(String key) {NodeH3 temp = front.getNext(); int i = 1; if(size == 0) { System.out.println("Element not found"); return null; } while(temp != last) { if(temp.getValue().equals(key)) { System.out.println("String: " + key + " found at position : " + i); return temp; } i++; temp = temp.getNext(); } System.out.println("String element not found"); return null; } public void printForward() { NodeH3 temp = front.getNext(); while(temp != last) { System.out.print(temp.getValue() + " "); temp = temp.getNext(); } System.out.println(""); }

public void printBackward() { NodeH3 temp = last.getBack(); while(temp != front) { System.out.print(temp.getValue() + " "); temp = temp.getBack(); } System.out.println(""); } public void deleteNode(String key) { NodeH3 n = search(key); if(n == null) { System.out.println("No string available in the list"); return; } NodeH3 temp = n.getBack(); temp.setNext(n.getNext()); n.getNext().setBack(temp); System.out.println("Node <" + key +"> deleted"); }

public void destroyList() { NodeH3 temp = front.getNext(); NodeH3 temp2; while(temp != last) { temp2 = temp; temp = temp.getNext(); temp2.setBack(null); temp2.setNext(null); } front.setNext(last); last.setBack(front); } public static void main(String []args) { NodelistH3 list = new NodelistH3(); list.insert("Pencil"); list.insert("Paper"); list.insert("Eraser"); list.insert("Book");

list.printForward(); list.printBackward(); list.deleteNode("Book"); list.printForward(); list.printBackward(); list.deleteNode("Paper"); list.printForward(); list.printBackward(); list.deleteNode("Paper");

list.destroyList(); list.printForward(); list.printBackward(); }

}