Building a Deque ADT

A dequeue, which stands for double-ended queue, is a queue that can insert and remove items from two sides: thefrontandback. To build this data structure, we are going to adopt theDoublyLinkedListdata type we already built in the previous chapter. Similar to the Queue data type, the Dequeue data type also has the Front() operation to fetch the front-most element's value. The Enqueue() operation in the Queue data type will become EnqueueBack() in the Dequeue data type, and the Dequeue() operation in the Queue data type will become DequeueFront() in the Dequeue data type. However, since we adopt the DoublyLinkedList data type instead of LinkedList, the implementation will be different. Besides those operations, we are also going to build the following operations:

• The Back() operation to fetch the back-most element's value.
• The EnqueueFront() operation to insert a new element into the front side. It will be similar to the implementation of the InsertHead() operation in the...