7/11/2023
PROGRAMMING II
Queue
Sherina Sally
D e p a r t m e n t o f I C T,
F a c u l t y o f Te c h n o l o g y,
University of Colombo
Introduction
• A linear data structure
• Follows the (FIFO) First In First Out rule
• The first element inserted will be removed first
• Insertion and deletion will be at different ends
Department of ICT, Faculty of Technology, University of Colombo | sherina@[Link]
1
7/11/2023
Applications of Queue
• Printer queue
• Request queues in web servers
• Message queues in communications
• CPU scheduling
Department of ICT, Faculty of Technology, University of Colombo | sherina@[Link] 3
Queue Operations
• Enqueue – Add an element to the queue
• Dequeue – Remove an element from the queue
• Peek – Read the value of the element at the front of the queue
• Traverse – Visit the elements of the queue
Dequeue Enqueue
Department of ICT, Faculty of Technology, University of Colombo | sherina@[Link] 4
2
7/11/2023
Queue Implementation
• Queue has two references: front and rear
• Front points to the first element of the queue
• Rear points to the last element of the queue
• Can be implemented using arrays or linked lists
• Initially, the front and rear will be -1
• The queue is full, when the rear has reached the maximum size of the array
Department of ICT, Faculty of Technology, University of Colombo | sherina@[Link] 5
Enqueue
• Add elements to the queue
• The first element added to the queue will be at the front of the queue
• The rear will be incremented by 1
• Check if the queue is full before adding to the queue
Initial front = -1
Queue rear = -1
Department of ICT, Faculty of Technology, University of Colombo | sherina@[Link] 6
3
7/11/2023
Enqueue Steps
front = -1
Add First front = 0
rear = -1
Element rear = 0
Add Second front = 0
Element rear = 1
Add Third front = 0
Element rear = 2
Add Fourth front = 0
Element rear = 3
7
Department of ICT, Faculty of Technology, University of Colombo | sherina@[Link]
Enqueue Implementation
begin procedure enqueue: queue, MAX, element
if rear == MAX
print “Queue is Full”
return
else if queue is empty
front ← rear ← 0
else
rear ← rear + 1
queue[rear] ← element
end procedure
8
Department of ICT, Faculty of Technology, University of Colombo | sherina@[Link]
4
7/11/2023
Dequeue
• The front most element of the queue will be removed
• The front will be incremented by 1
• Check if the queue is empty before removing from the queue
• When all the elements are removed from the queue set the front and rear to -1
front = 0 Initial
rear = 3 Queue
After front = -1
Removing 9
rear = -1
Elements
Department of ICT, Faculty of Technology, University of Colombo | sherina@[Link]
Dequeue Steps
front = 0
Remove First front = 1
rear = 3
Element rear = 3
Remove Second front = 2
Element rear = 3
Remove Third front = 3
Element rear = 3
Remove Fourth front = -1
Element rear = -1
10
Department of ICT, Faculty of Technology, University of Colombo | sherina@[Link]
5
7/11/2023
Dequeue Implementation
begin procedure dequeue: queue
if queue is empty
print “Queue is Empty”
return
else if front == rear
front ← rear ← -1
else
front ← front + 1
end procedure
11
Department of ICT, Faculty of Technology, University of Colombo | sherina@[Link]
Peek
• The front most element of the queue will be read
• No element will be removed
front
0 1 2 3
Department of ICT, Faculty of Technology, University of Colombo | sherina@[Link] 12
6
7/11/2023
Queue Operations Example
Draw the queue after following the steps below indicating the values for front and rear:
• Enqueue(34)
• Enqueue(20)
• Enqueue(10)
• Dequeue()
Department of ICT, Faculty of Technology, University of Colombo | sherina@[Link] 13
Queue Operations Example - Solution
Draw the queue after following the steps below indicating the values for front and rear:
• Enqueue(34) Operation front rear
• Enqueue(20)
Enqueue(34) 0 0
• Enqueue(10)
Enqueue(20) 0 1
• Dequeue()
Enqueue(10) 0 2
Dequeue() 1 2
Department of ICT, Faculty of Technology, University of Colombo | sherina@[Link] 14
7
7/11/2023
Time Complexity
Operation Time Complexity
Enqueue O(1)
Dequeue O(1)
Search O(n)
15
Department of ICT, Faculty of Technology, University of Colombo | sherina@[Link]
Priority Queue
• Each element in the queue has a priority score
• Elements are comparable with each other
• An entry has a value that will be considered as a priority score
• Elements with higher priority are served first
• Insertion can occur in any order, swap the elements until it attains the priority order
• Removal is based on the priority value
• Elements with the same priority will follow the FIFO principle
16
Department of ICT, Faculty of Technology, University of Colombo | sherina@[Link]
8
7/11/2023
Circular Queue
• The last element of the queue is connected to the first element
• Insertion is at the rear and deletion is at the front
• Empty slots of the queue can be utilized
• Use (rear + 1) Mod n to find the next index to enqueue
• Use (front + 1) Mod n to find the new front index when dequeue occurs
Department of ICT, Faculty of Technology, University of Colombo | sherina@[Link] 17
Circular Queue - Example
Perform the following operations to the circular queue
• Dequeue()
• Enqueue(20)
• Enqueue(40)
• Enqueue(45)
• Dequeue()
Department of ICT, Faculty of Technology, University of Colombo | sherina@[Link] 18
9
7/11/2023
Circular Queue - Solution
Perform the following operations to the circular queue
• Dequeue()
Operation front rear
• Enqueue(20) Dequeue() 1 5
• Enqueue(40) Enqueue(20) 1 6
• Enqueue(45) Enqueue(40) 1 7
(rear + 1) % n
• Dequeue() Enqueue(45) 1 ?? = (7 + 1) % 8
=8%8
Dequeue() 2 0 =0
19
Department of ICT, Faculty of Technology, University of Colombo | sherina@[Link]
10