Question 2 on this Project. I am attaching the problem, checklist, and my attempt(failed) at the code

import dsa.LinkedStack; import stdlib.StdIn; import stdlib.StdOut;

public class Sort { // Entry point. public static void main(String[] args) { LinkedDeque d = new LinkedDeque(); LinkedStack s = new LinkedStack(); while (!StdIn.isEmpty()) { String w = StdIn.readString(); if (d.size() == 0) { d.addFirst(w); } else if (less(w, d.peekFirst()) ) { d.addFirst(w); } else if (less(d.peekLast(), w)) { d.addLast(w); } else { s.push(d.peekFirst()); d.addFirst(w); while (!s.isEmpty()) { d.addFirst(s.pop()); }

} } StdOut.println(d); }

// Returns true if v is less than w according to their lexicographic order, and false otherwise. private static boolean less(String v, String w) { return v.compareTo(w) Problem 1. (Deque) A double-ended queue or deque (pronounced "deck") is a generalization of a stack and a queue that supports adding and removing items from either the front or the back of the data structure. Create a generic, iterable data type called LinkedDeque that uses a doubly-linked list to implement the following deque API: LinkedDeque LinkedDeque () boolean isEmpty() int size void addFirst(Item item) void addLast (Item item) Item peekFirst() Item removeFirst Item peeklast) Item removeLast() Iterator iterator() String toString() constructs an empty deque returns true if this deque empty, and false otherwise returns the number of items on this deque adds iten to the front of this deque adds iten to the back of this deque returns the item at the front of this deque removes and returns the item at the front of this deque returns the item at the back of this deque removes and returns the item at the back of this deque returns an iterator to iterate over the items in this deque from front to back returns a string representation of this deque Corner Cases The add*() methods should throw a NullPointerException("iten is null") if item is null. The peek+() and remove+() methods should throw a NoSuchelementException("Deque is empty") if the deque is empty. The next() method in the deque iterator shoud throw a NoSuchElementException("Iterator is empty") if there are no more items to iterate. Performance Requirements The constructor and methods in LinkedDeque and DequeIterator should run in time T(n) ~ 1. >- */workspace/project2 $ java LinkedDeque Filling the deque... The deque (364 characters) There is grandeur in this view of life, with its several powers, having been originally breathed into a few forms or into one; and that, whilst this planet has gone cycling on according to the fixed lav of gravity, from so simple a beginning endless forns most beautiful and most wonderful have been, and are being, evolved. Charles Darwin, The Origin of Species Emptying the deque... deque.isEmpty()? true Problem 2. (Sorting Strings) Implement a program called Sort.java that accepts strings from standard input, stores them in a LinkedDeque data structure, sorts the deque, and writes the sorted strings to standard output. Performance Requirements The program should run in time T(n) ~na, where n is the number of input strings. Problems Problem 2. (Sorting Strings) Hints: Create a deque di For each word w read from standard input Add w to the front of d if it is less than the first word in d Add w to the back of d if it is greater than the last word in di Otherwise, remove words that are less than w from the front of d and store them in a temporary stack s; add w to the front of d; and add words from s also to the front of d Write the words from d to standard output Use the helper method boolean less (String v, String w) to test if a string v is less than a string w