|
Data Structures and Algorithms
with Object-Oriented Design Patterns in Ruby |
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 a DequeMethods methods module
and the Deque abstract class.
The DequeMethods module is intended to be mixed-in
to a Queue class implementation
in order to extend that queue into a deque.
Program: Deque module and the Deque abstract class.
Copyright © 2004 by Bruno R. Preiss, P.Eng. All rights reserved.