Queue Array Implementation

The Queue ADT

 

A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle. The first element added to the queue is the first one to be removed. Insertions are limited to one end (Rear end) and deletions occur at the other end (Front end).

Key Operations on a Queue:

1. Enqueue: Adds an element to the rear of the queue.
2. Dequeue: Removes an element from the front of the queue.

Queue model

 

Array implementation of Queue

struct QueueRecord;

typedef struct QueueRecord *Queue;

 

int IsEmpty(Queue Q);

int IsFull(Queue Q);

Queue CreateQueue(int maxElements);

void DisposeQueue(Queue Q);

void MakeEmpty(Queue Q);

void Enqueue(int X, Queue Q);

void Dequeue(Queue Q);

 

# define maxElements 100

struct QueueRecord

{

         int Capacity;

         int Front;

         int Rear;

int size;

int * Array;

}

 

Note – Circular array implementation – when Front or Rear gets to the end of the array it is wrapped to the start of the array.

 

// Check for empty queue

int IsEmpty(Queue Q)

{

         return (Q->Size == 0);

}

 

// Check for full queue

int IsFull(Queue Q)

{

         return (Q->Size == Q->Capacity);

}

 

// Delete all elements in queue

void MakeEmpty(Queue Q)

{

         Q->Size = 0;

Q->Front = 1;

Q->Rear = 0;

}

 

// Create Queue

Queue CreateQueue(int maxElements)

{

         Queue Q;

         Q = malloc(sizeof(struct QueueRecord));

         Q->Array = malloc(sizeof(int) * maxElements);

         Q->Size = 0;

Q->Front = 1;

Q->Rear = 0;

         Q->Capacity = maxElements;

}

 

static int succ(int value, Queue Q)

{

if(++value == Q->Capacity)

         value = 0;

return value;

}

 

// Insert element at Rear

void Enqueue(int X, Queue Q)

{

         if(IsFull(Q))       

                 printf(“Error – Full queue. Cant insert.”);

         else

{

                 Q->Size++;

                 Q->Rear = succ(Q->Rear, Q);

                 Q->Array[Q->Rear] = X;

         }

}

 

// Delete element from Front

void Dequeue(Queue Q)

{

         if(IsEmpty(Q))    

                 printf(“Error – Empty queue. Cant delete.”);

         else

{

                 Q->Size––;

                 Q->Front++;

}      

}