- It’s special data structure based on FIFO (First In First out Concept).
- It can be implemented using One dimensional Array as well as Singly linked list.
- REAR and FRONT are the two external pointers holds the addresses of two ends respectively.
- Insertion and deletion are done from two different ends known as REAR and FRONT respectively.
Types of Queue:
- Linear Queue: Elements are arranged in a linear order.
- Circular Queue: Elements are arranged in a queue by means of circular array.
- D-Queue.( Double Ended QUEUE ) The ADD and DELETE operations are done from both the ends.
- Priority QUEUE: The elements are stored and deleted in QUEUE on this basis of Priority.
Linear Queue:
Algorithm using Linked List:
CREATELQ( ARR, N , FRONT , REAR, ITEM)
[ ARR is the name of the array of size N. ITEM is the info. of element inserted in queue]
If REAR = N Then:
Write: ‘ Overflow’
Exit
[ End of If ]
If REAR = 0 Then:
FRONT <-- 1
REAR <-- 1
Else:
REAR <-- REAR + 1
[ End of If]
ARR[REAR] <-- ITEM
Exit
Algorithm for DELETE operation in Linear Queue:
DELETELQ ( ARR, FRONT, REAR)
[ ARR is name of the array of size N]
If FRONT=NULL Then:
Write: ‘ Empty Queue’
Exit
[ End of If ]
ITEM <-- FRONT --> INFO
If REAR = FRONT Then:
REAR <-- NULL
FRONT <-- NULL
Else
FRONT <-- FRONT --> NEXT
[ End of If]
Write: ‘Deleted Element ‘, ITEM
END
Algorithm using One dimensional Array.
ADDLQ(QUEUE,N, ITEM, REAR, FRONT)
If REAR=N Then:
Write: ‘ OverFlow’
Exit
[ End of If]
If REAR = -1 Then:
REAR <-- 0
FRONT <-- 0
Else
REAR <-- REAR +1
[ End of If]
QUEUE[ REAR] <-- ITEM
END
DELETELQ(QUEUE , REAR, FRONT)
If FRONT =-1 Then:
Write: ‘ Empty Queue’
Exit
[ End of If ]
Write: ‘ Deleted Element’ FRONT --> INFO
If FRONT= REAR Then:
FRONT= -1
REAR= -1
Else
FRONT <-- FRONT --> NEXT
[ End of If]
End
Circular Queue:
ADDCQ(QUEUE,N, ITEM, REAR, FRONT)
If FRONT =REAR +1REAR=N Then:
Write: ‘ OverFlow’
Exit
[ End of If]
If REAR = -1 Then:
REAR <-- 0
FRONT <-- 0
Else
REAR <-- REAR +1
[ End of If]
QUEUE[ REAR] <-- ITEM
END