Create two new files named Stack.java and Queue.java which will contain classes for a stack and a queue using a LinkedList to store their data. The LinkedList class is given already and should be fully functional. Each class will need to take a generic data type, T.

Stack will need three methods. push will take a T parameter and store it in the LinkedList. The pop method will remove a T item from the LinkedList in correct stack orderand return it. getList will return the LinkedList being used by the stack (this is required for testing)

Queue will need three methods. add will take a T parameter and store it in the LinkedList. The remove method will remove a T item from the LinkedList in correct queue order and return it. getList will return the LinkedList being used by the queue (this is required for testing)

You may feel free to add other helper methods to your classes, but they are not required. Do not change LinkedList.java and do not use any built in Java data types.

Goal: Create Stack.java & Queue.java as described above

Starter Code given below.

LinkedList.java

import java.util.Scanner; import java.util.ArrayList;

public class LinkedList{

Node head; Node tail;

public class Node{ //inner class T data; Node next; Node prev;

public Node(T data){ this.data = data; } }

public void addHead( T data ){ Node n = new Node( data ); if(head == null){ //empty list head = n; tail = n; return; } head.prev = n; n.next = head; head = n; }

public void addTail( T data ){ Node n = new Node( data ); if(tail == null){ //empty list head = n; tail = n; return; } tail.next = n; n.prev = tail; tail = n; }

public T remHead( ){ Node ret = head;

if(head==null) //empty list return null; if(head==tail){ //empty after removing tail head=null; tail=null; return ret.data; } head = head.next; head.prev = null; return ret.data; }

public T remTail( ){ Node ret = tail;

if(tail==null) //empty list return null; if(head==tail){ //empty after removing tail head=null; tail=null; return ret.data; }

tail = tail.prev; if(tail==null) head = null; else{ tail.next = null; } return ret.data; }

public T getHead( ){ if(head == null) //empty list return null; return head.data; }

public T getTail( ){ if(tail == null) //empty list return null; return tail.data; }

public String toString(){ String ret = "";

Node curr = head; while( curr != null ){ ret += curr.data + " "; curr = curr.next; } return ret; } }