Use this code:

D. 12 points -- Use a circular doubly linked chain to implement the ADT deque. In a doubly linked chain, the first and last nodes each contain one null reference, since the first node has no previous node and the last node has no node after it. In a circular doubly linked chain, the first node references the last node, and the last node references the first. Only one external reference is necessary-a reference to the first node-since you can quickly get to the last node from the first node. The code for this problem is provided in the Assignment-03-Code.zip archive. Your output must be identical to the output to the right