For this program, you will implement an ADT known as a “deque” (double-ended queue). This ADT provides both Stack and Queue functionality. You will implement it as a linked collection from scratch without using any interfaces or classes from the Java Collections Framework (java.util). The files Main.java and SimpleDeque.java have already been provided to you. You will not make any changes to Main.java and you will fill in the SimpleDeque class as provided. Because you are writing a linked data structure from scratch, you may create another class for your linked node. See the example Output for runs of this program.

Here is the link to the GitHub Classroom assignment: https://classroom.github.com/a/amo2vZdu

(a)

Setup a project with the 2 files provided, Main.java and SimpleDeque.java. However you setup your project, keep the source files provided to you in the src directory provided at the root of the project directory. This makes grading more consistent. Once setup, you can ignore Main.java, as you will make no changes to it, and any changes you do make will be overwritten with the original version of the file.

(b)

Next, you will implement the SimpleDeque class as a “deque” ADT, from scratch without using the Java Collections Framework. This means you cannot use any interfaces or classes from the package java.util. You will also implement SimpleDeque as a linked collection (a collection of linked nodes), not as an array, so you may create an additional class for your node structure. Strictly speaking, your linked collection can be singly-linked, although it is easier to implement the methods with a doubly- linked collection. Keep in mind that the class is already using Java Generics, so you must keep that trend throughout the class.

The methods you must implement are:

public SimpleDeque()

public void push(E element) public E pop()

public void enqueue(E element) public E dequeue()

public boolean isEmpty() public int size()

public String toString()

The push(), pop(), and dequeue() methods operate on the front or head of the deque, while the

enqueue() method operates on the back or tail of the deque.

(c)

As you can see from the example Output and from Main.java, the toString() method of SimpleDeque should return a String with a listing of all the elements separate by a single space each. Do not put System.out.println() calls in this method! And do not return a string with any newlines in it. You are building a String variable and then returning it.

(d)

The inputs for this program are passed in as separate command-line arguments. You can provide them by calling your program from the shell, or you can provide them in the command line arguments textbox in the run / debug configuration settings of your project within your IDE. The commands are pu, po, en, de, ie, and sz. These commands activate the SimpleDeque methods: push(), pop(), enqueue(), dequeue(), isEmpty(), and size(), respectively. You can try your own input combinations by passing any series of commands, each followed an element. Each command requires an additional argument even if the command doesn’t normally take one (such as pop or size).

Submission

You will commit and push your changes to your specific GitHub Classroom repository for this assignment. Although you are encouraged to use an IDE for development, we will compile and run your program using the shell during grading. So please test your program in the shell. Please follow the directions in this document, make the requested code changes, and commit and push your changes any time before the due date. Your final output should have the functionality displayed in the example Output below.

This assignment has been answered 6 times in private sessions.