Implementation of Queues ?

What comes to our mind with the word 'Queue' is quite often not a positive one. Long lines of people, waste of time & often leads to some inconveniences. 

But, one thing is universal, about Queues, that is ? of course the "First Comer leaves first, from the beginning". So, everybody joined in the queue eventually will be moved towards the front.

I'm not intending to talk about ordinary queue here. I'm actually talking about Queue the data structure we've to study during lessons of initial programming concepts.

Queue is an abstract data types because of the separate implementation, away from the actual operations with the data structure itself.

What're these Implementations ? Well Similar  to Stacks, Queues also contain three operations which could be implemented in abstract manner.

1. Insert
2. Remove
3. Peek Front

 Let's look into the C++ implementation of each on of these operations. Look at the class file.

// Queue.h
class Queue
{
    private:

        int maxSize;
        double *queueArray;
        int front;
        int rear;
        int numofitems;
        bool stats;

    public:
        ~Queue(); // destructor
        Queue(int size); // parametrized constructor 
        void insert(double item); // insert
        void remove(); // remove
        bool isFull(); // check is full
        bool isEmpty(); // check is empty
        double peekFront(); // peek front item

}; 

Implementation of the parametrized constructor should be as follows.

Queue::Queue(int size)
{
    stats;
    maxSize = size;
    queueArray = new double[maxSize];
    front = 0; // front is 0
    rear = -1; // initialize rear to -1
    numofitems = 0; // number of items 0
}

1. First, Insert. Well insert is where we can add items to the Queue. We've to do this from behind of the existing Queue.

void Queue::insert(double item)
{
    if(!isFull()) // Queue shouldn't be full 
    {
        queueArray[++rear] = item; // increment rear & assign value to the Queue
        numofitems++; // increment number of items by one
        front++; // increment front 
    }
    else
    {
        cout<<"Your Queue is Full!"<<endl;
    }   
}

2. Second, Remove. As mentioned before this operation should be happened at the beginning of the Queue.

void Queue::remove()
{
    if(!isEmpty())// checks whether the queue is empty
    {
        queueArray[rear--]; // removes item
        cout<<"An Item is removed!"<<endl;
    }
    else
    {
        cout<<"Queue is Empty!"<<endl;
    }
}  

3. Third, We can implement a method to check the front item of the Queue. So whenever there's an operation, this returns the front item.

double Queue::peekFront()
{
    return queueArray[rear];
}

Look at the following picture. It shows, the two types of Queues that exist. The above implementations can be applied to linear queues but not circular queues.

Image clearly, shows that, not like in Linear Queue the incrementation of the last item to the next item is problematic as the 0th Item removes first.

We've to set rear = 0 when, rear == maxSize - 1. Look at the method implementation below.

void Queue::inc(double &index)
{
    if(index==maxSize-1) // if index is the last element
    {
        // set index to zero
        index = 0;
    }
    else
    {
        index = index+1;
    }
}

Now, the enqueue() - insert item to queue method implements as show below.

void Queue::enQueue(double item)
{
    if(!isFull())
    {
        inc(rear);
        qArray[++rear] = item;
        cout<<"Item added!"<<end;
        nItems++;
        front++;
    }
    else
    {
        cout<<"Your Queue is Full"<<endl;
    }
}

Thank You!