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, getHead, enqueueHead and dequeueHead, and three operations to access the tail of the queue, getTail, 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 the six methods, getHead, enqueueHead, dequeueHead, getTail, enqueueTail, and dequeueTail.

  
Program: Deque interface.

• Array Implementation
• Linked List Implementation
• Doubly-Linked and Circular Lists

Copyright © 1998 by Bruno R. Preiss, P.Eng. All rights reserved.