class EmptyListE extends Exception{}

public class DoublyLinkedList {

private NodeDL head;

private NodeDL tail;

private int size;

// TODO: default constructor

public DoublyLinkedList(){

}

// TODO: secondary constructor

public DoublyLinkedList(NodeDL head, NodeDL tail){

}

public int size() {

return this.size;

}

// TODO: Insert elem at the start of the DoublyLinkedList

void insertAtHead(E elem){

}

// TODO: Insert elem at the end of the DoublyLinkedList

void insertAtTail(E elem){

}

// TODO: Delete the element from the start of the DoublyLinkedList. Throw an EmptyListE if there's nothing to delete

E deleteAtHead() throws EmptyListE{

return null;

}

// TODO: Delete the element from the end of the DoublyLinkedList. Throw an EmptyListE if there's nothing to delete

E deleteAtTail() throws EmptyListE{

return null;

}

// TODO: Get the element at some position. If it's not possible, throw an IndexOutOfBoundsException

E get (int index) throws IndexOutOfBoundsException{

return null;

}

// TODO: Search the DoublyLinkedList for elem. If not found, return -1;

public int search(E elem){

return -1;

}

// TODO: When passed some object, return true if it's a DoublyLinkedList, has the same elements in the same order.

public boolean equals(Object o){

return false;

}

public String toString(){

String ret = "";

NodeDL temp = head;

for(int i = 0; i

ret += temp.data + " ";

temp = temp.next;

}

return ret;

}

}

import java.io.BufferedReader;

import java.io.FileReader;

import java.io.IOException;

import java.util.ArrayList;

import java.util.List;

// Feel free to reuse from HW1

public class MazeSolver {

static char[][] maze;

static int m, n; // dimensions of the maze

/*

TODO: setMaze - sets up the board

This method will take in a String, file, which is the path of the file we want to look at.

Using BufferedReader and FileReader, write this method so that it sets the rows, m, and columns, n,

to the first line of input. Then it fills the maze with the maze from the file.

*/

public static void setMaze(String file) throws IOException {

}

/*

TODO: isValid - checks if a position on the board has not been visited and is within bounds

*/

public static boolean isValid(int x, int y) {

return false;

}

/*

TODO: Using a stack, solve the maze WITHOUT recursion.

Pseudo:

1) Push start position onto Stack.

2) While it's not empty;

3) Pop from the stack to get the current considered location

4) If it's already explored ignore

5) If it's the goal, return true

6) If it's not the goal, then explore it.

7) You will need to compute all the possible neighbors. Then push those on the stack

8) Return false

*/

public static boolean solveMazeStack(int x, int y) throws EmptyStackE {

return false;

}

// TODO: Using a queue, solve the maze. Be sure to explain your algorithm for full points.

public static boolean solveMazeQueue(int x, int y) throws EmptyQueueE{

return false;

}

// TODO: Solve the board. Mode 1 = stack solving. Mode 2 = queue solving.

// 1: stack

// 2: queue

public static boolean solve(String file, int mode) throws IOException, EmptyStackE, EmptyQueueE {

// find starting point

// check if the maze can be solved

boolean solved = false;

System.out.println("Maze can be solved: " + solved);

return false;

}

}

public class NodeDL {

E data;

NodeDL prev;

NodeDL next;

public NodeDL(E elem) {

this.data = elem;

}

public String toString() {

return "" + this.data;

}

// TODO: Return whether the other has same type and same pointers

public boolean equals(Object o){

return false;

}

}

class EmptyQueueE extends Exception{}

public class Queue {

private DoublyLinkedList q;

private int size;

// TODO: default constructor

public Queue(){

}

// TODO: Put element at end of queue

public void enqueue(E elem){

}

// TODO: Return the head of the queue; If there's nothing to return then throw EmptyQueueE

public E dequeue() throws EmptyQueueE {

return null;

}

// TODO: Without affecting the queue, return the element at the top of the queue

public E peek() throws IndexOutOfBoundsException{

return null;

}

public int size() {

return this.size;

}

// TODO: Checks if inputted is the same Queue

public boolean equals(Object o){

return false;

}

public String toString(){

return "" + q.size();

}

}

class EmptyStackE extends Exception{}

public class Stack{

private DoublyLinkedList st;

private int size;

// TODO: default constructor

public Stack(){

}

// TODO: Push the element to the top of stack

public void push(E elem){

}

// TODO: Pop the element off the top of the stack. If nothing to pop, throw EmptyStackE

public E pop() throws EmptyStackE {

return null;

}

// TODO: Without affecting the stack, return the element at the top of the stack

public E peek() throws IndexOutOfBoundsException{

return null;

}

public int size() {

return this.size;

}

// TODO: Check if some other object is the same Stack

public boolean equals(Object o){

return false;

}

public String toString(){

return st.toString();

}

}

public class Coord{

private int x,y;

public Coord(int x, int y){

this.x = x;

this.y = y;

}

public int getX(){

return this.x;

}

public int getY(){

return this.y;

}

public String toString(){

return this.x + " " + this.y;

}

// TODO: This should be straightforward. This is a softball

public boolean equals(Object o){

return false;

}

}

Part I: Implementation of Doubly Linked List, Stack, and Queue You need to write generic classes for each of the following: DoublyLinkedList For this part of the assignment, you need to implement a doubly linked list class with a head and tail pointer. You need to implement the following methods: insertAtHead: Should insert at the start of the list deleteAtHead: Should delete from the start of the list. Throws EmptyListE if nothing to delete. insertAtTail: Should insert at the end of the list deleteAtTail: Should delete from the end of the list. Throws EmptyListE if nothing to delete. get: Should return the item at given index. Throws Inde OutOfBoundsException if cannot get at that index. search: Should search for a given item, and return the index or 1 if item is not found equals: Given some input, return whether it has the same type, order/Nodes. Stack Using your DoublyLinkedList, implement a Stack. The following operations need to be implemented: Push: Should insert at the top of the stack Pop: Should remove and return the item from the top of the stack. Throw EmptyStackE if there's nothing there. Peek: Should return the top of the stack. Throw IndexOutOfBoundsException if nothing returned. Equals: check if some other object is the same stack (order/accuracy) Queue Using your DoublyLinkedList, implement a Queue. The following operations need to be implemented: Enqueue: Should insert at the back of the queue Dequeue: Should remove and return the item front of the queue. If nothing to return throw EmptyQueueE Peek: Should return the front element. Throw Inde OutOfBoundsException if nothing returned. Equals: check if some other object is the same queue (order/accuracy) Part II: Application Maze solver - Without recursion 1. Redo assignment 1 using a Stack. Here is a rough algorithm (which needs some more work - such as what happens if the stack is empty at some point): Push the start position onto the atack. While atack la not empty Pop the stack to get the current location If location already explored do nothing If location li the goal, then qoal is reachable Otherwlse, this is a reachable non-finiah location, so explore it further: compute all the adjacent locations that are inalde the maze and aren't walls, and push them onto the atack Mark thla location as marked 2. Use a Queue to solve the maze. You need to devise your own algorithm to do this. Please be sure to explain our algorithm for full points. Bonus: Can you find the path from the start to the end? If you attempt the bonus, be sure to comment it on your submission on Canvas or else it will be ignored. This is your only warning. Read the instructions, If successfully completed, +15% ? Tests: Aim for code coverage of 100%. Your tests should test edge cases, Be sure to submit Junit tests for all. Submission to Autograder: -NodeDL.java -MazeSolver.java -DoublyLinkedList.java -Queue.java -Stack.java Submission to Canvas: - NodeDL.java -MazeSolver.java -DoublyLinkedList.java -Queue.java - Stack.java -any mazes you created - MazeSolverTest.java -DoublyLinkedListTest.java -StackTest.java -QueueTest.java