Linked representation of Queue

A linked queue can be implemented as a linked list with two pointer variables FRONT and REAR pointing to the nodes which is in the FRONT and REAR of the queue.

1. Insertion in Queues using Linked List Algorithm 

Algorithm: LINKQ_INSERT(INFO, LINK, FRONT, REAR, ITEM, AVAIL).

This algorithm inserts an element ITEM into a linked queue.

Step I: [OVERFLOW?]
If AVAIL := NULL, then: Write: OVERFLOW and Exit.
Step II: [Remove first node from AVAIL list.]
Set NEW := AVAIL, and
AVAIL := LINK[AVAIL].
Step III: Set INFO[NEW] := ITEM, and
LINK[NEW] := NULL. [Copies ITEM into new node.]
Step IV: If FRONT = NULL, then:
Set front := new and rear := new.
[If Q is empty then ITEM is the first element in the queue Q.]
Else:
Set LINK[REAR] := NEW, and
REAR := NEW.
[REAR points to the new node appended to the end of the list.]
Step V: Exit.

2. Deletion in Queues using Linked List Algorithm 

Algorithm: LINKQ_DELETE(INFO, LINK, FRONT, REAR, ITEM, AVAIL).

This algorithm deletes the front element of the linked queue and stores it in ITEM.

Step I: [UNDERFLOW?]
If FRONT = NULL, then: Write: UNDERFLOW and Exit.
Step II: Set ITEM := INFO[FRONT].
[Save the data value of FRONT.]
Step III: Set NEW := FRONT, and
Set FRONT := LINK[FRONT].
[Reset FRONT to the next position.]
Step IV: Set LINK[NEW] := AVAIL, and
AVAIL := NEW
[Add node to the AVAIL list.]
Step V: Exit.