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 theDoublyLinkedList
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 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 theInsertHead()
operation in the...