Linked list implementation of Queue

Linked list implementation of Queue

1. LINKED LIST
IMPLEMENTATION OF
QUEUE
MODULE 3
1

2. IMPLEMENTING QUEUES USING
LINKED LISTS
•Allocatememoryforeachnewelementdynamically
•Linkthequeueelementstogether
•Usetwopointers,FrontandRear,tomarkthefrontand
rearofthequeue
Dr. SINDHIA LINGASWAMY, VIT
2

3. •Inalinkedqueue,everyelementhastwoparts,onethatstoresthe
dataandanotherthatstorestheaddressofthenextelement.
•TheSTARTpointerofthelinkedlistisusedasFRONT.
•Here,wewillalsouseanotherpointercalledREAR,whichwillstore
theaddressofthelastelementinthequeue.
•Allinsertionswillbedoneattherearendandallthedeletionswill
bedoneatthefrontend.
•IfFRONT=REAR=NULL,thenitindicatesthatthequeueisempty.
Dr. SINDHIA LINGASWAMY, VIT
3

4. ENQUEUING (EMPTY
QUEUE)
We need to make Frontpoint to the new node
also
New Node
newNode
Dr. SINDHIA LINGASWAMY, VIT
4

5. FUNCTION ENQUEUE
Dr. SINDHIA LINGASWAMY, VIT
5

6. DEQUEUEING (THE QUEUE
CONTAINS ONLY ONE ELEMENT)
•We need to reset Rearto NULL also
Nod
e
qFront
qRear
After dequeue:
qFront = NULL
qRear = NULL
Dr. SINDHIA LINGASWAMY, VIT
6

7. Function Dequeue
Dr. SINDHIA LINGASWAMY, VIT
7