Data Structures and Algorithms
with Object-Oriented Design Patterns in C#|
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 interface. The Deque interface extends the Container interface defined in Program . Hence, it comprises all of the methods inherited from Container plus four methods, EnqueueHead, DequeueHead, EnqueueTail, and DequeueTail, and two properties, Head and Tail.
Program: Deque interface.