You need a queue object in which you can explicitly control the adding and removing of objects to either the head (top) or tail (bottom).
A queue that allows explicit removal of items from the head and the tail is called a double-queue.
This class is defined as follows:
using System; using System.Collections; [Serializable] public class DblQueue : ICollection, IEnumerable, ICloneable { public DblQueue( ) { internalList = new ArrayList( ); } public DblQueue(ICollection coll) { internalList = new ArrayList(coll); } protected ArrayList internalList = null; public virtual int Count { get {return (internalList.Count);} } public virtual bool IsSynchronized { get {return (false);} } public virtual object SyncRoot { get {return (this);} } public static DblQueue Synchronized(DblQueue dqueue) { if (dqueue == null) { throw (new ArgumentNullException("dqueue")); } return (new SyncDeQueue(dqueue)); } public virtual void Clear( ) { internalList.Clear( ); } public virtual object Clone( ) { // Make a new DQ DblQueue newDQ = new DblQueue(this); return newDQ; } public virtual bool Contains(object obj) { return (internalList.Contains(obj)); } public virtual void CopyTo(Array array, int index) { internalList.CopyTo(array, index); } public virtual object DequeueHead( ) { object retObj = internalList[0]; internalList.RemoveAt(0); return (retObj); } public virtual object DequeueTail( ) { object retObj = internalList[InternalList.Count - 1]; internalList.RemoveAt(InternalList.Count - 1); return (retObj); } public virtual void EnqueueHead(object obj) { internalList.Insert(0, obj); } public virtual void EnqueueTail(object obj) { internalList.Add(obj); } public virtual object PeekHead( ) { return (internalList[0]); } public virtual object PeekTail( ) { return (internalList[internalList.Count - 1]); } public virtual IEnumerator GetEnumerator( ) { return (internalList.GetEnumerator( )); } public virtual object[] ToArray( ) { return (internalList.ToArray( )); } public virtual void TrimToSize( ) { internalList.TrimToSize( ); } // Nested Synchronized class [Serializable] public class SyncDeQueue : DblQueue { public SyncDeQueue(DblQueue q) { wrappedQ = q; root = q.SyncRoot; } private DblQueue wrappedQ = null; private object root = null; public override int Count { get { lock(this) { return (wrappedQ.Count); } } } public override bool IsSynchronized { get {return (true);} } public override object SyncRoot { get {return (root);} } public override void Clear( ) { lock(this) { wrappedQ.Clear( ); } } public override object Clone( ) { lock(this) { return (this.MemberwiseClone( )); } } public override bool Contains(object obj) { lock(this) { return (wrappedQ.Contains(obj)); } } public override void CopyTo(Array array, int index) { lock(this) { wrappedQ.CopyTo(array, index); } } public override object DequeueHead( ) { lock(this) { return (wrappedQ.DequeueHead( )); } } public override void EnqueueHead(object obj) { lock(this) { wrappedQ.EnqueueHead(obj); } } public override object PeekHead( ) { lock(this) { return (wrappedQ.PeekHead( )); } } public override object DequeueTail( ) { lock(this) { return (wrappedQ.DequeueTail( )); } } public override void EnqueueTail(object obj) { lock(this) { wrappedQ.EnqueueTail(obj); } } public override object PeekTail( ) { lock(this) { return (wrappedQ.PeekTail( )); } } public override IEnumerator GetEnumerator( ) { lock(this) { return (wrappedQ.GetEnumerator( )); } } public override object[] ToArray( ) { lock(this) { return (wrappedQ.ToArray( )); } } public override void TrimToSize( ) { lock(this) { wrappedQ.TrimToSize( ); } } } }
The double-queue class created for this recipe was developed in a
fashion similar to the PriorityQueue
in Recipe 10.2. It exposes most of the
ArrayList
members through wrapper methods. For
instance, the DblQueue.Count
and
DblQueue.Clear
methods, among others, simply
delegate their calls to the ArrayList.Count
and
ArrayList.Clear
methods, respectively.
The methods defined in Table 10-2 are of particular interest to constructing a double-queue.
Table 10-2. Members of the DblQueue class
The following code exercises the DblQueue
class:
class CTest { static void Main( ) { DblQueue dqueue = new DblQueue( ); // Count should be zero Console.WriteLine("dqueue.Count: " + dqueue.Count); try { // Attempt to remove an item from an empty queue object o = dqueue.DequeueHead( ); } catch (Exception e) { Console.WriteLine(e.ToString( )); } // Add items to queue dqueue.EnqueueHead(1); dqueue.EnqueueTail(2); dqueue.EnqueueHead(0); dqueue.EnqueueTail(3); // Clone queue DblQueue dqueueClone = (DblQueue) dqueue.Clone( ); Console.WriteLine("dqueueClone.Count: " + dqueueClone.Count); // Find these items in the cloned queue Console.WriteLine("dqueueClone.Contains(1): " + dqueueClone.Contains(1)); Console.WriteLine("dqueueClone.Contains(0): " + dqueueClone.Contains(0)); Console.WriteLine("dqueueClone.Contains(15): " + dqueueClone.Contains(15)); // Display all items in cloned queue foreach (object o in dqueueClone.ToArray( )) { Console.WriteLine("Queued Item (Cloned): " + o); } dqueueClone.TrimToSize( ); // Display all items in original queue foreach (int i in dqueue) { Console.WriteLine("Queued Item: " + i.ToString( )); } // Find these items in original queue Console.WriteLine("dqueue.Contains(1): " + dqueue.Contains(1)); Console.WriteLine("dqueue.Contains(10): " + dqueue.Contains(10)); // Peek at head and tail values without removing them Console.WriteLine("dqueue.PeekHead( ): " + dqueue.PeekHead( ).ToString( )); Console.WriteLine("dqueue.PeekTail( ): " + dqueue.PeekTail( ).ToString( )); // Remove one item from the queue's head and two items from the tail Console.WriteLine("dqueue.DequeueHead( ): " + dqueue.DequeueHead( )); Console.WriteLine("dqueue.DequeueTail( ): " + dqueue.DequeueTail( )); Console.WriteLine("dqueue.DequeueTail( ): " + dqueue.DequeueTail( )); // Display the count of items and the items themselves Console.WriteLine("dqueue.Count: " + dqueue.Count); foreach (int i in dqueue) { Console.WriteLine("Queued Item: " + i.ToString( )); } // Clear the cloned queue of all items (items are also removed from the // original queue, since this is a shallow copy dqueueClone.Clear( ); } }
The DblQueue
class implements the same three
interfaces as the Queue
class found in the
System.Collections
namespace of the FCL. These are
the ICollection
, IEnumerable
,
and ICloneable
interfaces. The
IEnumerable
interface forces the DblQueue
to implement the
GetEnumerator
method. The implementation of the
DblQueue.GetEnumerator
method returns the
IEnumerator
object for the internal
ArrayList
, used to store the queued items.
The
ICloneable
interface forces the
Clone
method to be implemented in the
DblQueue
class. This method returns a shallow copy
of the DblQueue
object.
The
ICollection
interface forces three properties and
a method to be implemented by the DblQueue
class.
The IsSynchronized
and SyncRoot
methods obtain a synchronized DblQueue
object that
is thread-safe. In addition to these two properties, a static method
called Synchronized
is added to enable clients of
this object to obtain a synchronized version of this class. These
synchronization properties and methods will be discussed at length in
Recipe 13.4.
The ICollection
interface also forces the
Count
property and the CopyTo
method to be implemented by the DblQueue
class.
Both of these delegate to the corresponding
ArrayList
property and method for their
implementations.
The Enqueue
and Dequeue
methods
of the Queue
class found in the FCL operate only
on the head of the queue. The DblQueue
class
allows these operations to be performed on both the head and tail of
a queue. The DblQueue
class has the flexibility of
being used as a first-in, first-out (FIFO) queue, which is similar in
operation to the System.Collection.Queue
class; or
of being used as a first-in, last-out (FILO) stack, which is similar
in operation to the System.Collection.Stack
class.
In fact, with a DblQueue
, you can start off using
it as a FIFO queue and then change in midstream to using it as a FILO
stack. This can be done without having to do anything special, such
as creating a new class.