Recipe 11.3. Creating a Double Queue Problem 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), also known as a double queue. Solution A queue that allows explicit removal of items from the head and the tail is called a double queue. Example 11-4 shows one way you can implement a double queue. Example 11-4. DblQueue class using System; using System.Collections; using System.Collections.Generic; [Serializable] public class DblQueue<T> : ICollection<T>, ICloneable { public DblQueue() { internalList = new List<T>(); } public DblQueue(ICollection<T> coll) { internalList = new List<T>(coll); } protected List<T> 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 virtual void Clear() { internalList.Clear(); } public object Clone() { // Make a new DblQueue. DblQueue<T> newDQ = new DblQueue<T>(); newDQ.CopyTo(internalList.ToArray(), 0); return newDQ; } public virtual bool Contains(T obj) { return (internalList.Contains(obj)); } public virtual void CopyTo(Array array, int index) { for (int cntr = 0; cntr < internalList.Count; cntr++) { array.SetValue((object)internalList[cntr], cntr); } } public virtual T DequeueHead() { T retObj = internalList[0]; internalList.RemoveAt(0); return (retObj); } public virtual T DequeueTail() { T retObj = internalList[internalList.Count - 1]; internalList.RemoveAt(internalList.Count - 1); return (retObj); } public virtual void EnqueueHead(T obj) { internalList.Insert(0, obj); } public virtual void EnqueueTail(T obj) { internalList.Add(obj); } public virtual T PeekHead() { return (internalList[0]); } public virtual T PeekTail() { return (internalList[internalList.Count - 1]); } public virtual IEnumerator GetEnumerator() { return (internalList.GetEnumerator()); } public virtual T[] ToArray() { return (internalList.ToArray()); } public virtual void TrimExcess() { internalList.TrimExcess(); } void System.Collections.Generic.ICollection<T>.Add(T item) { throw (new NotSupportedException( "Use the EnqueueHead or EnqueueTail methods.")); } void System.Collections.Generic.ICollection<T>.CopyTo(T[] item, int index) { for (int cntr = index; cntr < internalList.Count; cntr++) { item[cntr - index] = internalList[cntr]; } } bool System.Collections.Generic.ICollection<T>.Remove(T item) { throw (new NotSupportedException( "Use the DequeueHead or DequeueTail methods.")); } bool System.Collections.Generic.ICollection<T>.IsReadOnly { get {throw (new NotSupportedException("Not Supported."));} } IEnumerator<T> System.Collections.Generic.IEnumerable<T>.GetEnumerator() { return (internalList.GetEnumerator()); } }
|
The double queue class created for this recipe was developed in a fashion similar to the PriorityQueue<T> in Recipe 11.2. It exposes most of the List<T> members through wrapper methods. For instance, the DblQueue<T>.Count and DblQueue<T>.Clear methods, among others, simply delegate their calls to the List<T>.Count and List<T>.Clear methods, respectively. The methods defined in Table 11-2 are of particular interest to constructing a double queue. Table 11-2. Members of the DblQueue classMember | Description |
|---|
Count property | Returns an int indicating the number of items in the queue. | Clear method | Removes all items from the queue. | Clone method | Returns a copy of the DblQueue<T> object. | Contains method | Returns a bool indicating whether the queue contains a particular search object. Its syntax is: Contains(T obj)
where obj is the object to be found in the queue. | CopyTo method | Copies a range of items from this queue into an array. Its syntax is: CopyTo(Array array, int index)
where array is the array into which the queue will be copied and index is the index in the queue at which to start copying items. The head of the queue is at index 0. | DequeueHead method | Removes and returns the object at the head (i.e., position 0) of the queue. This method makes use of the indexer and RemoveAt methods of the internal List<T> to return the first (zeroth) element in the List<T>. Its syntax is: DequeueHead( )
| DequeueTail method | Removes and returns the object at the tail (i.e., position (List<T>.Count -1) of the queue. This method makes use of the indexer and RemoveAt methods of the internal List<T> to return the last element in the List<T>. Its syntax is: DequeueTail( )
| EnqueueHead method | Accepts an object type to add to the head of the queue. This method makes use of the Insert method of the internal List<T>to add an element to the start (zeroth position) in the List<T>. Its syntax is: EnqueueHead(T obj)
where obj is the object to add to the head of the queue. | EnqueueTail method | Accepts an object type to add to the tail of the queue. This method makes use of the Add method of the internal List<T> to add an element to the end of the List<T>. Its syntax is: EnqueueTail(T obj)
where obj is the object to add to the tail of the queue. | PeekHead method | Returns, but does not remove, the object at the head of the queue. This method makes use of the indexer of the internal List<T>to obtain the first (zeroth) element in the List<T>. Its syntax is: PeekHead( )
| PeekTail method | Returns, but does not remove, the object at the tail of the queue. This method makes use of the indexer of the internal List<T> to obtain the last element in the List<T>. Its syntax is: PeekTail>( )
| ToArray method | Returns the entire queue as an object array. Its syntax is: ToArray( )
The first element in the object array (index 0) is the item at the head object in the queue and the last element in the array is the tail object in the queue. | trimExcess method | Sets the capacity of the queue to the number of elements currently in the queue. Its syntax is: TrimExcess( )
|
The code in Example 11-5 exercises the DblQueue<T> class. Example 11-5. Testing the DblQueue class class Test { static void Main() { DblQueue<int> dqueue = new DblQueue<int>(); // 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("THIS EXCEPTION IS ON PURPOSE!"); Console.WriteLine(e.ToString()); Console.WriteLine("THIS EXCEPTION IS ON PURPOSE!") } // Add items to queue. dqueue.EnqueueHead(1); dqueue.EnqueueTail(2); dqueue.EnqueueHead(0); dqueue.EnqueueTail(3); dqueue.TrimExcess(); // 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()); // Copy this queue to an array. Array arr = Array.CreateInstance(typeof(object), dqueue.Count); dqueue.CopyTo(arr, 0); foreach (object o in arr) { Console.WriteLine("Queued Item (CopyTo): " + o.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()); } } }
|
The output for this method is shown here: dqueue.Count: 0 THIS EXCEPTION IS ON PURPOSE! System.ArgumentOutOfRangeException: Index was out of range. Must be non-negative and less than the size of the collection. Parameter name: index at System.ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument argument, ExceptionResource resource) at System.ThrowHelper.ThrowArgumentOutOfRangeException() at System.Collections.Generic.List`1.get_Item(Int32 index) at CSharpRecipes.DataStructsAndAlgorithms.DblQueue`1.DequeueHead() in C:\Documents and Settings\Admin\Desktop\CSharp Recipes 2nd Edition\Code\CSharpRecipes\11_ DataStructsAndAlgorithms.cs:line 570 at CSharpRecipes.DataStructsAndAlgorithms.CreatingAMoreVersatileQueue() in C:\ Documents and Settings\Admin\Desktop\CSharp Recipes 2nd Edition\Code\CSharpRecipes\ 11_DataStructsAndAlgorithms.cs:line 456 THIS EXCEPTION IS ON PURPOSE! Queued Item: 0 Queued Item: 1 Queued Item: 2 Queued Item: 3 dqueue.Contains(1): True dqueue.Contains(10): False dqueue.PeekHead(): 0 dqueue.PeekTail(): 3 Queued Item (CopyTo): 0 Queued Item (CopyTo): 1 Queued Item (CopyTo): 2 Queued Item (CopyTo): 3 dqueue.DequeueHead(): 0 dqueue.DequeueTail(): 3 dqueue.DequeueTail(): 2 dqueue.Count: 1 Queued Item: 1
Discussion The DblQueue<T> class implements the same three interfaces as the Queue<T> class found in the System.Collections.Generic namespace of the FCL. These are the ICollection, IEnumerable, and ICloneable interfaces. The IEnumerable interface forces the DblQueue<T> to implement the GetEnumerator method. The implementation of the DblQueue<T>.GetEnumerator method returns the IEnumerator object for the internal List<T>, used to store the queued items. The ICollection interface forces three properties and a method to be implemented by the DblQueue<T> class. The IsSynchronized property returns false, and the SyncRoot method returns the DblQueue<T> object on which it was called. These synchronization properties and methods will be discussed at length in Recipes 4.4, 4.10, and 18.2. The ICollection interface also forces the Count property and the CopyTo method to be implemented by the DblQueue<T> class. Both of these delegate to the corresponding List<T> property and method for their implementations. The Enqueue and Dequeue methods of the Queue<T> class found in the FCL operate in only one direction, enqueuing to the tail and dequeuing from the head of the queue. The DblQueue<T> class allows these operations to be performed on both the head and tail of a queue. The DblQueue<T> class has the flexibility of being used as a first-in, first-out (FIFO) queue, which is similar in operation to the Queue<T> class, or of being used as a first-in, last-out (FILO) stack, which is similar in operation to the Stack<T> class. In fact, with a DblQueue<T>, 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. See Also See the "List<T> Class," "IEnumerable Interface," "ICloneable Interface," and "ICollection Interface" topics in the MSDN documentation. |
