A double-ended queue or deque is like a stack or a queue but supports adding and removing items at both ends. A deque stores a collection of items and support the following API ublic class dequesItem> implement Iterable deque0 isEmpty0 size pushLeft(Item item)//add an item to the left end pushRight(Item item)//add an item to the right end popLeft0 popRight0 //create an empty deque //is the deque empty? /umber of items in the deque boolean int void void Item Item void void void //remove and return an item from left end /remove and return an item from right end //remove all items /display the items in the deque left to right //display the items in the deque right to left clear0 printo printRevO API for generic double-ended queue 1. Write a class Deque that uses a doubly-linked list to implement this API. You need to implement all methods of the doubly-linked list class and the deque class Write a driver program for this class. The driver program is a menu-driven For each method in the deque class (except the constructor), there will be a corresponding choice in the menu. 2. program Deliverables A softcopy and hardcopy of the project are both required and include the following. a. A single Word file containing the following i. Complete code listings for all classes required in addition to the main0 function Screen shots of the output. This should include normal cases as well as invalid input caseslike popping an empty deque