Data Structures and Algorithms with Object-Oriented Design Patterns in C#
next up previous contents index

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 .gif

Figure gif 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.

   figure7506
Figure: Basic deque operations.

Program gif defines the Deque interface. The Deque interface extends the Container interface defined in Program gif. Hence, it comprises all of the methods inherited from Container plus four methods, EnqueueHead, DequeueHead, EnqueueTail, and DequeueTail, and two properties, Head and Tail.

   program7866
Program: Deque interface.




next up previous contents index

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