DATA STRUCTURES
II PCA
LINKED REPRESENTATION OF
QUEUE
LINKED REPRESENTATION OF QUEUE
• Array implementation of the queue is implemented in case the
queue size is small or its maximum size is known in advance
• Linked representation of queue is used if the array size cannot
be determined in advance
• In a linked queue, every node has two part
To store data
To store the address of the next node.
LINKED REPRESENTATION OF QUEUE
The START pointer of the linked list is used as FRONT
Another pointer called REAR is used to store the address of
the last element in the queue.
All insertions will be done at the rear end and all the deletions
will be done at the front end.
If FRONT = REAR = NULL, then it indicates that the queue is
empty
OPERATIONS ON A LINKED QUEUE
A linked queue supports all the three stack operations,
Insert Operation
Delete Operation
Peek Operation
INSERT OPERATION
• The insert operation is used to insert an element into a
queue.
• The new element is added as the last element of the queue
INSERT OPERATION
Example of Insert operation in a Linked Queue
• To insert an element with value 9
• If FRONT=NULL.
Indicates Queue is empty and allocate memory for a new node, store
the value in its DATA part and NULL in its NEXT part.
The new node will then be called both FRONT and REAR
If FRONT!= NULL,
Insert the new node at the rear end of the linked queue and name this
new node as REAR
INSERT OPERATION
. Linked Queue
Linked queue after inserting a new node
Algorithm to insert an element in a linked queue
Step 1: In Step 1,
Allocate memory for the new node and name• The memory is allocated for the new
it as NEW_NODE node.
Step 2: In Step 2,
SET NEW_NODE -> DATA = VAL • The DATA part of the new node is
initialized with the value to be stored in
the node.
Step 3:
IF TOP = NULL
In Step 3,
SET NEW_NODE -> NEXT = NULL
If TOP = NULL
SET TOP = NEW_NODE
NULL is stored in the NEXT part of the
ELSE node and the new node is called TOP.
SET NEW_NODE -> NEXT = TOP ELSE
SET TOP = NEW_NODE It is added before the first node of the
[END OF IF] list and termed as TOP.
Step 4: END
DELETE OPERATION
• The delete operation is used to delete the element that is first
inserted in a queue, i.e., the element whose address is stored
in FRONT
• If FRONT=NULL, it means that the queue is empty and no
more deletions can be done.
• An UNDERFLOW message is printed, if an attempt is made
to delete a value from a queue that is already empty.
• If FRONT!=NULL, then delete the first node pointed by FRONT
and FRONT will now point to the second element of the
linked queue
DELETE OPERATION
Linked queue
Linked queue after deletion of an element
Algorithm to delete an element from a linked
Queue
In Step 1,
we first check for the UNDERFLOW condition
In Step 2,
A pointer PTR is used that points to FRONT.
In Step 3,
FRONT is made to point to the next node in
sequence.
In Step 4,
The memory occupied by PTR is given back to the
free pool.
