Data Structure
Queue
Prepared by
Dalton Meitei Thounaojam
Queue
Stores the elements in an ordered manner.
The first element in the order are processed first.
Also known as First In First Out (FIFO).
Array representation of Queue
Insertion
Step 1: IF REAR = MAX-1
Write OVERFLOW
Goto step 4
[END OF IF]
Step 2: IF FRONT = -1 and REAR = -1
SET FRONT = REAR = 0
ELSE
SET REAR = REAR + 1
[END OF IF]
Step 3: SET QUEUE[REAR] = NUM
Step 4: EXIT
Array representation of Queue
Deletion
Step 1: IF FRONT = -1 OR FRONT > REAR
Write UNDERFLOW
ELSE
SET VAL = QUEUE[FRONT]
SET FRONT = FRONT + 1
[END OF IF]
Step 2: EXIT
Link List representation of Queue
Insertion
Step 1: Allocate memory for the new node and name it as
PTR
Step 2: SET PTR -> DATA = VAL
Step 3: SET PTR -> NEXT = NULL
Step 4: IF FRONT = NULL
SET FRONT = REAR = PTR
SET FRONT -> NEXT = NULL
ELSE
SET REAR -> NEXT = PTR
SET REAR = PTR
[END OF IF]
Step 4: END
Link List representation of Queue
Deletion
Step 1: IF FRONT = NULL
Write “Underflow”
Go to Step 5
[END OF IF]
Step 2: SET PTR = FRONT
Step 3: SET FRONT = FRONT -> NEXT
Step 4: FREE PTR
Step 5: END
Types of Queue
Circular queue
Dequeue
Priority Queue
Multiple Queue
Circular Queue
Suppose we have a queue which is full
10 20 30 40 50
0 1 2 3 4
index FRONT REAR
After two consecutive deletion, then
30 40 50
0 1 2 3 4
index FRONT REAR
Even with free space we cannot perform insertion.
Insertion in a Circular Queue
Step 1: IF (FRONT = 0 and REAR = MAX – 1) or (REAR = FRONT-1)
Write “OVERFLOW”
Goto step 4
[End OF IF]
Step 2: IF FRONT = -1 and REAR = -1
SET FRONT = REAR = 0
ELSE
IF REAR = MAX - 1 and FRONT != 0
SET REAR = 0
ELSE
SET REAR = REAR + 1
[END OF IF]
[END OF IF]
Step 3: SET QUEUE[REAR] = VAL
Step 4: EXIT
Deletion in a Circular Queue
Step 1: IF FRONT = -1
Write “UNDERFLOW”
Goto Step 4
[END of IF]
Step 2: SET VAL = QUEUE[FRONT]
Step 3: IF FRONT = REAR
SET FRONT = REAR = -1
ELSE
IF FRONT = MAX -1
SET FRONT = 0
ELSE
SET FRONT = FRONT + 1
[END of IF]
[END OF IF]
Step 4: EXIT
Dequeue
Elements can be inserted or deleted at either end.
No element can be added and deleted from the
middle.
Also known as a head-tail linked list.
Also known as double-ended queue.
Also a circular queue.
Types are :
Input restricted dequeue: In this dequeue,
insertions can be done only at one of the ends, while
deletions can be done from both ends.
Output restricted dequeue: In this dequeue,
deletions can be done only at one of the ends, while
insertions can be done on both ends.
Dequeue
There are four basic operations
Insertion at rear end
Insertion at front end
Deletion at front end
Deletion at rear end
Insertion at rear in Dequeue
Step 1: IF REAR = MAX - 1
PRINT “OVERFLOW”
Goto step 6
[End OF IF]
Step 2: REAR = REAR + 1
Step 3: QUEUE[REAR] = NUM;
Step 4: IF REAR = 0
REAR = 1;
[End OF IF]
Step 5: IF FRONT = 0
FRONT = 1;
[End OF IF]
Step 6: EXIT
Insertion at front in Dequeue
Step 1 : IF FRONT <= 1
PRINT "Cannot add item at the front”
Go To Step 4
[End OF IF]
Step 2 : FRONT = FRONT + 1
Step 3 : QUEUE[FRONT] = NUM
Step 4 : EXIT
Deletion at front in Dequeue
Step 1 : IF REAR = 0
PRINT “Cannot delete value at rear end”
Go To Step 4
[End OF IF]
Step 2 : VAL = QUEUE[REAR]
Step 3 : IF FRONT = REAR
FRONT = 0
REAR = 0
ELSE
REAR = REAR - 1
Step 4 : EXIT
Deletion at rear in Dequeue
Step 1 : IF FRONT = 0
PRINT “ Underflow ”
Go To Step 4
[End OF IF]
Step 2 : VAL = QUEUE[FRONT]
Step 3 : IF FRONT = REAR
FRONT = 0
REAR = 0
ELSE
FRONT = FRONT + 1
[End OF IF]
Step-3 : EXIT
Priority Queue
The priority of the element will be used to determine
the order in which the elements will be processed.
The general rules of processing the elements of a
priority queue are :
An element with higher priority is processed before an
element with a lower priority.
Two elements with the same priority are processed on
a first-come-first-served (FCFS) basis.
Priority Queue using Link List
Insertion
When a new element has to be inserted in a priority
queue, we have to traverse the entire list until we find a
node that has a priority lower than that of the new
element.
The new node is inserted before the node with the
lower priority.
However, if there exists an element that has the same
priority as the new element, the new element is
inserted after that element.
Deletion
first node of the list will be deleted and the data of that
node will be processed first.
Thank you