Page 89 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes 4.2 Array Implementation

Here too, there are two possible implementation strategies – one where the memory is used
statically and the other where memory is used dynamically.

4.2.1 Array-based Implementation

To represent a queue we require a one-dimensional array of some maximum size say n to hold
the data items and two other variables front and rear to point to the beginning and the end of the
queue. Hence a queue data type may be defined in C as follows:

struct queue
{
T data[n];
int front, rear;
}
During the initialization of a queue q, its front and rear are made to 0. At each insertion to the
queue, which takes place at the rear end, ‘rear’ is incremented by 1. At each deletion, ‘front’ is
incremented by 1. The following procedures show the implementation of the queue operations:
void insert(queue q[], T x)
/* This function inserts an element x into the queue q */
{
if(q.rear == n) printf(‘Queue is full!”);
else
{
q.rear = q.rear + 1;
q.data[q.rear] = x;
}
}
void delete(queue q[], T x)
/*deletes an element from the queue and stores in x*/
{
if(q.front == q.rear)
{
printf(“queue is empty!”)
q.front = 0;
q.rear = 0;
}
else
{
q.front= q.front + 1;
x =q.data[q.front];
}
boolean empty(queue q[])

84 LOVELY PROFESSIONAL UNIVERSITY