Chapter 2: Basic Abstract Data Types. Problem 2.15

Circular Queues. 

Lets take a look at what a circular queue is -->  

If we wish to implement a queue using an array, we are faced with the inherent problem of deletion that plagues arrays - to delete an element, all elements after it need to be moved up - which is time consuming. 
One way out of this is to create a circular queue - where the list is imagined to be a circle. 
Lets look at an example. 

Lets take a queue of length 4. Initially all elements are empty - represented by E. 

E   E   E   E
F
B

F = Front pointer
B = Back pointer 

Queue is a First In First Out (FIFO) structure - think of a queue at a bank. 

When F = B, queue is empty. 
An element is added at B position. After adding the element, B points to the next empty space. This next step is circular -- that is when B reaches the end, it start over again from the start. 
An element is deleted at F position. After deleting the element, F points to the next element (again in circular order). 

Lets add some data to this queue. 

Initial position --> Empty Queue. 
E   E   E   E
F
B

Add 1 to the queue. 
1   E   E   E
F
    B

Add 2 to the queue. 
1   2   E   E
F
        B

Add 3 to the queue. 
1   2   3   E
F
            B

Add 4 to the queue. 
1   2   3   4
F
B

Notice a problem here. F = B but the queue is full! So how do we distinguish an empty queue from a full one? 

One strategy is to always leave one element empty - so this the above case, 
only three elements will fit in a queue of length 4. 
If B + 1 (in circular sense) = F, queue is Full. 

Another strategy is to keep a bit that represents an empty queue. 
If bit = 1 and F = B, queue is empty. 
If bit = 0 and F = B, queue is full. 

The problem is to implement this solution by keeping an extra bit.   

#include <iostream>
using namespace std;

const int MAXLENGTH = 10; 

class QUEUE
{
    int list[MAXLENGTH]; 
    int front; 
    int back;
    bool bQEmpty; 

public: 
    //Constructor
    QUEUE(); 
    bool QEmpty() { return bQEmpty ? true : false; }
    bool QFull() 
    { 
        if( (front == back) && !bQEmpty )
            return true;
        return false;
    }

    bool EnQueue(int val); 
    bool DeQueue(int& val); //OUTPUT = val
    void PrintQ(); 
}; 

QUEUE::QUEUE()
{
    memset(list, 0, sizeof(list)); 
    front = back = 0; 
    bQEmpty = true;
}

bool QUEUE::EnQueue(int val)
{
    if( QFull() )
    {
        cout << "ERROR: Queue is full" << endl;
        return false;
    }

    list[back] = val;
    back = (back+1)%MAXLENGTH; //circular
    if( bQEmpty )
        bQEmpty = false;
    return true; 
}

bool QUEUE::DeQueue(int& val) //OUTPUT = val
{
    if( QEmpty() )
    {
        cout << "ERROR: Queue is empty" << endl;
        return false;
    }

    val = list[front]; 
    front = (front+1)%MAXLENGTH; 
    if( front == back )
        bQEmpty = true;
    return true; 
}

void QUEUE::PrintQ()
{
    if( QEmpty() )
    {
        cout << "EMPTY QUEUE." << endl;
        return; 
    }

    cout << "QUEUE is ---->" << endl;

    //Printing this is a bit tricky :) 
    int n = front; 
    if( front == back ) //special case - queue is full.
    {
        cout << list[n] << " ";
        n = front+1;
    }

    for ( ; n != back; n=(n+1)%MAXLENGTH)
        cout << list[n] << " ";  

    cout << endl << "<---- END of QUEUE" << endl;
}

//Little driver program to test this
void main()
{
    QUEUE q; 
    q.PrintQ(); 
    int val = 0;

    cout << endl << "EnQueuing 10 elements.. " << endl;
    for( val = 0; q.EnQueue(val); val++) 
        q.PrintQ();

    cout << endl << "DeQueuing 5 elements.. " << endl;
    q.DeQueue(val);
    q.PrintQ(); 
    q.DeQueue(val);
    q.PrintQ(); 
    q.DeQueue(val);
    q.PrintQ(); 
    q.DeQueue(val);
    q.PrintQ(); 
    q.DeQueue(val);
    q.PrintQ(); 

    cout << endl << "EnQueuing 10 elements.. " << endl;
    for( val = 0; q.EnQueue(val); val++) 
        q.PrintQ();
}