C++ Data Structures and Algorithms

Building a Deque ADT

A dequeue, which stands for double-ended queue, is a queue that can insert and remove items from two sides: the front and back. To build this data structure, we are going to adopt the DoublyLinkedList data 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 ...