3.A double-ended queue, or deque(pronounced like deck), is introduced in Section 14.8. With a deque you can add, remove, or view elements from both ends of the queue. Rather than use the Deque interface supplied by the Java API, design your own DequeADT interface (patterned after QueueADT). Then, implement a deque using links.

Hint: Start with the LinkedQueue code that you completed as part of Lab 4. Also, each node will need both a next and a previous reference.

The driver should create a deque of moderate size (say five or six). It should repetitively add elements to the front, and then the rear. For each addition, output the contents of the deque as well as the size, front element, and last element. Then, repetitively remove elements from the deque. For each removal, output the contents of the deque as well as the size, front element, and last element. (Adapted from PP 14.6 and PP 14.7.)