CSharp Cookbook-CSharp Cookbook

Recipe 10.3 Creating a More Versatile 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).

Solution

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

Member

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

Contains method

Returns a bool indicating whether the queue contains a particular search object. Its syntax is:

Contains(object 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 in which the queue will be copied into, and index is the index in the queue 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 ArrayList to return the first (zeroth) element in the ArrayList. Its syntax is:

DequeueHead( )

DequeueTail method

Removes and returns the object at the tail (i.e., position (ArrayList.Count - 1) of the queue. This method makes use of the indexer and RemoveAt methods of the internal ArrayList to return the last element in the ArrayList. 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 ArrayList to add an element to the start (zeroth position) in the ArrayList. Its syntax is:

EnqueueHead(object 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 ArrayList to add an element to the end of the ArrayList. Its syntax is:

EnqueueTail(object 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 ArrayList to obtain the first (zeroth) element in the ArrayList. 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 ArrayList to obtain the last element in the ArrayList. 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.

TrimToSize method

Sets the capacity of the queue to the number of elements currently in the queue. Its syntax is:

TrimToSize( )

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( );
    }
}

Discussion

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.

Recipe 10.3 Creating a More Versatile Queue

Problem

Solution

Table 10-2. Members of the DblQueue class

Discussion

See Also