Problem: Implement a queue using an Array. Make efficient use of the space in the array.

Solution: Queue is a data structure that supports Enqueue and Dequeue methods. The Enqueue method adds an item to the end of the list and Dequeue method removes an item from the beginning of the list. This means that the Queue is a FIFO (First In First Out) data structure. Theoretically speaking a Queue doesn't have a fixed size. It grows as items are added to the end of the list. The implementation below has a fixed sized determined at the time of instantiating the Queue object. Ideally, the array should be reallocated to accommodate more items. The implementations makes use of the space efficiently by reusing space that is released when items are dequeued.

/************ Queue.h *********************/
// Queue class implements the Queue ADT(abstract data type) or Abstract Data Structure
// using an array as the underlying data structure
class Queue
{
    private:
        int *itemsArray;    // array used for storing items in the queue
        int startIndex;     // index in the array where the queue starts
        int size;           // size of the array holding the queue
        int count;          // number of items in queue

    public:
        Queue(int size);
        ~Queue();
        void Enqueue(int i);
        int Dequeue();
        int GetCount();
        void Print();
};

/************ Queue.cpp *********************/
#include "stdafx.h"
#include "malloc.h"
#include "Queue.h"

Queue::Queue(int size)
{
    this->size = size;
    itemsArray = (int *)malloc(sizeof(int) * size);
    startIndex = 0;
    count = 0;
}



Queue::~Queue()
{
    free(itemsArray);
}

// Enqueue method adds an item to the end of the queue
void Queue::Enqueue(int i)
{
    if(count < size) // queue is not full
    {
        int destinationIndex =  (startIndex + count) % size;
        itemsArray[destinationIndex] = i;
        count++;
    }
    else
    {
        printf("Queue is full...\n");
    }
}

// Dequeue method removes an item from the front of the queue
int Queue::Dequeue()
{
    if(count == 0)
    {
        printf("queue is empty!\n");
        throw "queue is empty";
    }
    int ret = itemsArray[startIndex];
    count--;
    startIndex = (startIndex + 1)%size;
    return ret;
}

int Queue::GetCount()
{
    return count;
}

// Print the current contents of the queue
void Queue::Print()
{
    printf("Queue contents: ");
    
   for(int i = 0; i<count;i++)
   {
        printf("%d, ", itemsArray[(startIndex + i)%size]);
   }
   printf("\n");
}