Abstract Data Type (ADT) is a very important concept and mechanism of object-oriented programming and design to implement information hiding and encapsulation. ADTs only define legal operations that can perform on them without specifications of how these operations are implemented, and these operations can be separately implemented in any way. In Java, ADTs are usually represented as interfaces. In this project you will design and implement a specific ADT with different data structures.

The ADT Deque is defined as a Java interface in our textbook. Write a Java program to implement this ADT with doubly linked list and circular array. Your program should consist of one interface and two classes:

• Define the interface Deque
• One class implements the dequeADT with a doubly linked list,
• One class implements the dequeADT with an array used in a circular fashion

Please include

• Java source code
• A class diagram describing the relationships of the interface and two classes as required
• Necessary documentation for the implemented operations