Data Structure "deque" (pronounced deck) is a queue, ll entry and exit on either end of the line, but no other insertions or deletions. It is similar to a line at a bank teller window. Regular customers enter at the end of the line, but special customers get escorted to the front of the line. Normally, customers exit from the front of the line when they are by the teller, but customers may choose to leave from the end of the line without being served if they are in a hurry For this exercise, implement a deque of Strings. Forma support the following operations: constructor initialize an empty deque. insertOnFront insert a given String on the front of the deque delete FromFront return (and delete) the String extracted from the front of the deque insertOnBack insert a given String on the back of the deque deleteFromBack return (and delete) the String extracted from the back of the deque isEmpty return true if the deque is empty, and false otherwise toString return a String summarizing the entire contents of the deque (from front to back) toStore return a String summarizing the entire contents of deque storage (from array index 0 to length-1) Application OWrite a simple test program to exercise all these operations on two instances of Deques. Construct an empty instance of each of these, then allow the user to repeatedly perform selected operations on either of the two, in any order, until they choose to quit. For each action, let the user select which Deque to manipulate, then allow them to choose from a menu of the available operations. Prompt for any necessary input, and display results of each operation (or a simple message acknowledging completion if there is no result) Implementation Use a single array of Strings to store the Deque. Give it an initial size of (admittedly small, for convenient testing), but allow it to grow, if necessary. If the user asks to insert an element in a Deque that is full, allocate an array twice the current size, copy the contents of the old array to the new one (you will actually be copying references, and carry out the requested insertion. If the user requests a deletion from an empty deque, just ignore the request without comment. (The isEmpty method is available to enable the user to detect that exceptional case.) (with Use the circular' array implementation strategy discussed in class (with queues). Allocate a single array wrap-around figuratively connecting the two ends of the array to store the deque's contents and respond to all insertion and deletion operations. Do not attempt to maintain two distinct regions within the array for separate of front and back operations. The implementation must be efficient Create one class called "Program4" for the program), and a separate, independent "Deque' application (the main class (NOT inside the Program4 class
