In lecture, we have seen that a deque can serve both as a stack and as a queuedepending on usage. We have also seen that a deque can be implemented using alinked list or an array to store its data. We will employ both of those features in thisproject.

Because we will use a deque as the storage medium for our queues and stacks, wewill begin there. You will implement two deque classes, one using an array to storethe contents and one using a linked list to store the contents. Notice that regardlessof how you store the data, the six operations that define a deque must be present:two pushes, two pops, and two peeks. If something calls itself a deque, it mustprovide at least those six methods. The programming pattern that enforces this iscalled an interface or more generally an abstract base class. We provide a completeabstract base class called Deque in the file Deque.py. Notice that the file does notcontain implementations; it only defines the functions that must be present. If youattempt to inherit from Deque, the child class must contain the methods listedin the abstract base class, or Python will refuse to construct the object andterminate. This is done via the special method __subclasshook__:

def __subclasshook__(child): required_methods = {‘push_front’, ‘push_back’, \ ‘peek_front’, ‘peek_back’, \’pop_front’, ‘pop_back’} if required_methods <= child.__dict__.keys(): return True return False

Python will call this method to see if a child class is allowed to inherit from the Dequeclass—that is, are the six required methods a subset of the methods in the child’snamespace? (In Python a set B is a subset of set A if and only if A <= B is True.) If allsix methods are there, __subclasshook__ will return True, indicating that child lookslike a deque and instantiation can proceed. If any method is missing,__subclasshook__ will return False, indicating that the child does not qualify as adeque and instantiation cannot proceed. This file is complete; do not modifyDeque.py.

Linked_List_Deque and Array_Deque should both inherit from Deque.Linked_List_Deque’s constructor will initialize an empty linked list for the data.Array_Deque’s constructor will initialize an empty array for the data. The six requiredmethods will have different implementations in each class because we interact witharrays and linked lists differently. Except for performance differences, the user ofyour deque should not be able to tell whether the implantation used a linked list oran array. Their functionality (and string representations) must be identical.