Data Structures and Algorithms with Object-Oriented Design Patterns in Python

Deques

In the preceding section we saw that a queue comprises a pile of objects into which we insert items at one end and from which we remove items at the other end. In this section we examine an extension of the queue which provides a means to insert and remove items at both ends of the pile. This data structure is a deque . The word deque is an acronym derived from double-ended queue .

Figure illustrates the basic deque operations. A deque provides three operations which access the head of the queue, Head, EnqueueHead and DequeueHead, and three operations to access the tail of the queue, Tail, EnqueueTail and DequeueTail.

Figure: Basic deque operations.

Program defines the Deque class. The abstract Deque class extends the abstract Container class defined in Program . Hence, it comprises all of the methods inherited from Container plus the methods, enqueueHead, dequeueHead, enqueueTail, and dequeueTail, and the properties, head and tail.

program7741
Program: Abstract Deque class.

The dequeueHead method of the Deque class is trivial to implement--it simply calls the dequeue method inherited from the Queue class. Similarly, the enqueueTail method simply calls the enqueue method inherited from the Queue class.