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)~n?, where n is the number of input strings. 1/3 Project 2 (Deques and Randomized Queues) > */workspace/project2 $ java Sort ABRACADABRA A A A D R R Problem 2. (Sorting Strings) Hints: Create a deque d 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 d 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 1. -import dsa.LinkedStack; 2 3 import stdlib.StdIn; import stdlib.Stdout; 4 5 7 public class Sort { // Entry point. public static void main(String[] args) { 8 9 10 } 11 12 // 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)