An Optimized Queue

• Download QueueDemo - 6.02 KB

Introduction

This article demonstrates and creates an optimized queue data structure which is a circular queue. Queue is one of the most important data structures. The most common scenario where we see queue being used is printing. We can insert element only on the front side and can remove only from the back side. Circular queue is an optimized version of a linear queue in the sense it reuses the space allocated after a popping operation. STL also has a container called queue. The definition and terminology that we understand here will also be applicable to the STL queue container.

Queues can be implemented either using an array or using a linked list. But linked list itself is a big data structure and can be another topic to be discussed in detail, so we will use arrays to demonstrate the queue here.

Other Details

I will also explain some of the other features of C++ also in this article like template and streams.
Templates are used to create class and libraries for generic data types without specifying the exact data type. The compiler creates a version of the data type when it sees its uses into the code. We are going to use template to create a CCircularQueue class. One important thing about template is it has to be defined in the .h files only so that all the code is propagated to all the files which #includes that .h file. This is required by the compiler as it needs all the template code anytime to generate a specific data type version.

Details of the CCircularQueue Class

Following are the structures and functions exposed by our queue class:

template <typename T>
class CCircularQueue 
{
private:
    int m_iCapacity;
    int m_iSize;
    T * m_arrContainer;
    int m_iRear, m_iFront;
    void Resize();    //Doubles the internal array
public:
    CCircularQueue();
    ~CCircularQueue();
    /****  Functions  *****/
    void Push(const T& elem);  //Adds an element in the queue
    T& Pop();     		//Removes an element from the queue and returns a reference. 
			//Does not destroy the element 
    bool IsEmpty();    	//Checks if the queue is empty
    void Clear();    	//Clears the whole queue. Does not destroy the objects
    int Size();     	//Returns the size
    void Print(ostream & os);  //Print the queue on to a console
};

m_arrContainer is pointer to a generic data type T which will be used to create a dynamic array. In the constructor:

template <typename T> CCircularQueue<T>::CCircularQueue():m_iCapacity(100)
, m_iSize(0)
, m_iRear(-1)
, m_iFront(-1)
{
    m_arrContainer = new T[m_iCapacity];
}

m_iRear and m_iFront initially point to nowhere (-1) but when we insert first element both point to them i.e. 0_^th position. As we go on inserting, m_iRear will keep on pointing to the 0^_th position, but m_iFront will go on incrementing its position. The reverse happens while popping the elements. m_iFront will keep on pointing to the same element but m_iRear will go on incrementing its position. 

The initial capacity of the queue is 100 but on the run time if it requires more space it will automatically grow to twice the length of the previous size. You can get the actual size and the capacity of the queue at any time using these two functions:

template <typename T> int CCircularQueue<T>::Size()
{
    return m_iSize;
}
template <typename T> int CCircularQueue<T>::Capacity()
{
    return m_iCapacity;
}

The most important among all these is the Push() function which is defined as below:

template <typename T> void CCircularQueue<T>::Push(const T& elem)
{
    //Case 1: queue is empty
    if(m_iRear == -1) 
    {
        m_arrContainer[++m_iRear] = elem;
        m_iFront = m_iRear; 
        m_iSize++; 
    }
    //Case 2: Still there is space available at the end
    else if((m_iFront < m_iCapacity-1) && (m_iFront+1 != m_iRear) )
    {
        m_arrContainer[++m_iFront] = elem;
        m_iSize++; 
    }
    //Case 3: We reached to end but space available at other end. 
    //Take advantage of circular queue
    else if(m_iFront == m_iCapacity-1 && m_iRear != 0) 
    {
        m_iFront = 0;
        m_arrContainer[m_iFront] = elem;
        m_iSize++; 
    } 
    //Case 4: No space available
    else
    {
        Resize();
        Push(elem);
    }
}

I will demonstrate each case here.

Case 1: Queue is empty.
Here both front and rear will point to -1. So just insert the element and move both the pointers to point to the first element.

Case 2: Still there is space available at the end.
It is a normal case where there are spaces available after the front. The condition makes sure the next element is not pointed by rear element because of the circular nature.

Case 3: We reached the end but there is space available at other end. Take advantage of circular queue.

This is demonstrated in the below diagram:

                                                         Before Push

                                                            After Push

This condition actually demonstrates a circular queue. If we Pop some element, then it will be removed from the start of the queue and hence rear pointer will move those many places forward making those spaces available for use in the other Push statements.

Case 4: No space available.
In all other cases, the queue is full. Here we resize the array container to double of the previous size and then recall the Push function recursively to insert the element.
The resize function is defined as below:

template <typename T> void CCircularQueue<T>::Resize()
{
    T * arrTemp = new T[2*m_iCapacity];
    int j = -1;
    for(int i = m_iRear; i <= m_iFront ; i++ )
    {
       arrTemp[++j] = m_arrContainer[i];
    }
    if(m_iFront < m_iRear)
    {
       for(int i = m_iRear;  i < m_iCapacity; i++)
       {
          arrTemp[++j] = m_arrContainer[i];
       }
       for(int i = 0; i<= m_iFront; i++)
       {
          arrTemp[++j] = m_arrContainer[i];
       }
    }
    delete [] m_arrContainer;
    m_arrContainer = arrTemp;
    m_iRear = 0;
    m_iFront = j;
    m_iCapacity*=2;
}

In all, what it does is it reallocates another array of double size, copies all the elements from rear to front to the new array, destroys the original array and points the m_arrContainer to the new array.
The Pop() function is defined as below:

template <typename T> T& CCircularQueue<T>::Pop()
{
    if(m_iRear == -1)
    throw new CGenericException("The queue is already empty\n");
    T &elem = m_arrContainer[m_iRear];
    if(m_iRear == m_iFront)  //The queue is empty now
    m_iRear = m_iFront = -1;
    else if(m_iRear == m_iCapacity -1)
    m_iRear = 0;
    else 
    m_iRear++;
    m_iSize--;
    return elem;
}

Notice that it actually does not destroy the elements but simply returns a reference to the element. User is supposed to delete the memory if allocated on the heap. This is the standard procedure for all STL libraries.

The function will throw an exception if we try to pop from an empty queue. The CGenericException class is user defined and is used just for showing information.
There are other functions which are self explanatory.

• bool IsEmpty(): It checks if the queue is empty or not.
• int Size(): It returns the size of the queue.
• int Capacity(): It returns the present capacity of the queue.
• void Print(ostream & os): It prints the elements on to a provided stream.
  If you want to print the output onto the console as the supplied sample does, then pass cout stream like this:
  C++

  CCircularQueue<int> cqInt;
  cqInt.Push(5);
  cqInt.Print(cout)

  If you want to write this onto a file, then pass a file stream like this:

  C++

  ofstream os("c:\\test.txt", ios::out /*| ios::app*/);
  cqInt.Print(os);
  os.close();

This concludes the article. You may wish to download the source code and look deep inside. You can also use this class in your project by just including the source files.

History

• First created on 11^th May, 2010