Linked Implementation of Queues

Linked Implementation of Queues

The items are deleted from the front of a queue and inserted at the rear. A pointer to the first element of a list represent the front of the queue. Another pointer to the last element of the list represent the rear of the queue.

If (empty(q))

{

Printf(“Queue underflow”);

Exit(1);

}

P=q.front;

X=info(p);

q.front=next(p) ;

if(q.front == null)

q.rear = null;

freenode(p);

return(x);

The operation insert(q,x) is implemented by

P = getnode();

Info(p) = x;

Next(p) = null;

If (q.rear == null)

q.front = p;

else

next(q.rear) = p;

q.rear = p;