Page 92 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 4: Queues

4.2.2 Pointer-based Implementation Notes

As in stacks, a queue could be implemented using a linked list.

A queue can be implemented by the following declarations and algorithms:
struct queueNode
{
T item;
queueNode *next;
};
struct queueNode, *front, *rear;
void insert(queueNode *front, queueNode *rear, T e)
{
struct queueNode *x;
x = new(queueNode);
x->item = e;
if(front == NULL) front = x;
else rear->next = x;
rear = x;
}
void delete(queueNode *front, T e, queueNode *front)
/*This procedure deletes the element from the front of the queue & stores it in
e */
{
if(front == NULL) printf(“Queue is empty”);
else
{
e = front->item;
front = front->next;
if(front == NULL) rear = NULL;
}
}
boolean empty(queueNode *q) /* check if queue is empty* /
{
if(q == NULL) return(true) else return(false);
}
void initialize(queueNode *front, queueNode *rear)
{
front = NULL; rear = NULL;
}

Task Write a program to implement a circular queue.

LOVELY PROFESSIONAL UNIVERSITY 87