Explain how circular queue differs from linear queue?

Answer 1

Both linear and circular queues are constructed from nodes:

struct node { T data; // the node's value (of type T)

node* next; // refers to the next node in the sequence

};

To implement a queue efficiently, we need to keep track of both the front and back of the queue. This is because all insertions occur at the back of the queue while all extractions occur at the front of the queue, and both operations must be performed in constant time.

struct queue {

node* head; // refers to the front of the queue

node* tail; // refers to the back of the queue

};

Initially, the queue is empty, so both the head and tail must be set to NULL.

We use the following function to insert some data at the back of the queue:

node* push (queue* q, T value) {

node* n = malloc (sizeof (node));

n->data = value;

n->next = NULL;

if (q->tail == NULL) {

q->head = n;

q->tail = n;

} else {

q->tail->next = n;

q->tail = n;

}

return n;

}

The following function extracts the head node:

void pop (queue* q) {

node* n = q->head;

if (q->head) {

q->head = q->head->next; // may be NULL

if (!q->head) q->tail = NULL;

}

free n;

}

In a circular queue, we don't need to keep track of the head because tail->next always points to the head unless tail is NULL. So we can eliminate the head pointer from the queue structure:

struct queue {

node* tail;

};

The insertion function therefore changes as follows:

node* push (queue* q, T value) {

node* n = malloc (sizeof (node));

n->data = value;

if (q->tail == NULL) {

n->next = n;

q->tail = n;

} else {

n->next = q->tail->next;

q->tail->next = n;

q->tail = n;

}

return n;

}

And the extraction function changes as follows:

void pop (queue* q) {

if (q->tail == NULL) return; // empty list

node* n = q->tail;

if (q->tail == q->tail->next) // a list of one

q->tail = NULL;

else

q->tail->next = q->tail->next->next; // adjust the head

free n;

}