//---------------------------------------------------------
// A queue class.
//
// D. Searls
// Mar 2009
//---------------------------------------------------------

#ifndef H_QUEUECLASS
#define H_QUEUECLASS
 
#include<iostream>
using namespace std;

template<class itemType>
class queue
{  
private:

    itemType* arr;
    unsigned int n;
    unsigned int capacity;
  
public:

    //-----------------------------------------------------
    // Default Constructor
    //
    // Constructs an empty queue.
    //-----------------------------------------------------
    queue()
    {
        try
        {
            capacity = 100;
            arr = new itemType[capacity];
            n = 0;
            
        }
        catch (bad_alloc bae)
        {
            cout << "FATAL ERROR: Memory allocation failure.";
            cout << endl << endl;
            exit (0);
        }
    }
    
    //-----------------------------------------------------
    // Initialization Constructor
    //
    // Construct a queue with the specified capacity.
    //
    // The specified capacity must be > 0.
    //
    // In Parameter: maxCapacity
    //-----------------------------------------------------
    queue(int maxCapacity)
    {
        try
        {
            if (maxCapacity > 0)
            {
                capacity = maxCapacity;
            }
            else
            {
                capacity = 100;
            }
            arr = new itemType[capacity];
            n = 0;
        }
        catch (bad_alloc bae)
        {
            cout << "FATAL ERROR: Memory allocation failure.";
            cout << endl << endl;
            exit (0);
        }
    }
    
    //-----------------------------------------------------
    // Copy Constructor
    //
    // Create a new queue that is an exact copy of the
    // specified queue.
    //
    // In Parameter: q
    //-----------------------------------------------------
    queue(const queue& q)
    {
        try
        {
            capacity = q.capacity;
            arr = new itemType[capacity];
            n = q.n;
            for (unsigned int i = 0; i < n; i++)
            {
                arr[i] = q.arr[i];
            }
        }
        catch (bad_alloc bae)
        {
            cout << "FATAL ERROR: Memory allocation failure.";
            cout << endl << endl;
            exit (0);
        }
    }
    
    //-----------------------------------------------------
    // Destructor
    //
    // Return the memory allocated for the queue back to
    // the operating system.
    //-----------------------------------------------------
    ~queue()
    {        
        delete [] arr;
    }
    
    //-----------------------------------------------------
    // enqueue
    //
    // Add the specified item at the back of the queue.
    //
    // The application program should verify that the queue
    // is not full before invoking this function. If the
    // queue is full, this function does nothing.
    //
    // In Parameter: item
    //-----------------------------------------------------
    void enqueue(const itemType& item)
    {
        if (!full())
        {
            arr[n] = item;            
            n++;
        }
    }
    
    //-----------------------------------------------------
    // dequeue
    //
    // Remove and discard the item at the front of the queue.
    //
    // The application program should verify the the queue
    // is not empty before invoking this function. If the
	// queue is empty, this function does nothing.
    //-----------------------------------------------------
    void dequeue()
    {
        if (!empty())
        {
            n--;
            for (unsigned int i = 0; i < n; i++)
            {
                arr[i] = arr[i+1];
            }
        }
    }
    
    //-----------------------------------------------------
    // clear
    //
    // Remove all of the elements from the queue.
    //-----------------------------------------------------
    void clear()
    {
        n = 0;
    }
    
    //-----------------------------------------------------
    // size
    //
    // Return the number of items in the queue.
    //-----------------------------------------------------
    unsigned int size()
    {
        return n;
    }
        
    //-----------------------------------------------------
    // empty
    //
    // Return true if the stack is empty and false
    // otherwise.
    //-----------------------------------------------------
    bool empty()
    {
        return (n == 0);
    }
    
    //-----------------------------------------------------
    // full
    //
    // Return true if the stack is full and false
    // otherwise.
    //-----------------------------------------------------
    bool full()
    {
        return (n == capacity);
    }
  
    //-----------------------------------------------------
    // front
    //
    // Return the item at the front of the queue.
    //
    // The application program should verify that the queue
    // is not empty before invoking this function.
    //-----------------------------------------------------
    itemType front()
    {
        return arr[0];
    }
    
    //-----------------------------------------------------
    // back
    //
    // Return the item at the back of the queue.
    //
    // The application program should verify that the queue
    // is not empty before invoking this function.
    //-----------------------------------------------------
    itemType back()
    {
        return arr[n-1];
    }
};

#endif