Algorithms and Data Structures
Course Code: CSC112
Instructor: Dr. Muhammad Awais Javed
Types of Queues
1. Circular Queue
2. Deque
3. Priority Queue
4. Multiple Queue
Circular Queue – Why needed?
Drawback of Linear Queue: Space available but overflow condition exists
Linear Queue Solutions for previous
challenge
Method 1
• Shift elements to the left so that vacant
space can be utilized efficiently
• Time consuming when queue is large
Method 2
• Use Circular Queue
Circular Queue
• First index comes right after the last index
Circular Queue – Full Queue
Circular Queue – Insertions
Circular Queue – Insertions
Circular Queue – Empty Queue
Circular Queue – Deletion
Circular Queue – Deletion
Deques
• Elements inserted or deleted from both ends
• Head-tail linked list
• Insertion and deletion from middle is not
allowed
• Implemented using circular array or circular
doubly linked list
• Advantage Efficient insertion and deletions
Variants of Deques
Priority Queue
• Data structure in which elements are assigned
priority
• Priority determine the order in which the
elements will be processed
Priority Rules
• 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 – Operating Systems
• Execute the highest priority process first
Priority = CPU time to get process executed
• P1, P2 and P3 take 5ns, 4ns, and 7ns. Which
one has highest priority?
Priority = Importance of process
• P1 and P2 are online order booking and
printing of stock details. Which one will be
executed first?
Implementation of Priority Queue
Method 1
• Insert element in a sorted list O(n)
• Dequeue element just like in normal queue O(1)
Method 2
• Enqueue element just like in normal queue O(1)
• Delete by searching element with highest
priority element O(1)
Both techniques have same complexity. Better
implementation in O(logn) by using Heaps
Priority Queue Implementation with
Linked List
• Linked List will have three parts
– Data
– Priority number
– Address of the next element
Priority Queue Implementation with
Linked List - Insertion
Priority Queue Implementation with
Linked List - Deletion
• First node will be deleted
• Just like in Normal Queue
Priority Queue Implementation with
Arrays
Priority Queue Implementation with
Arrays
• Two-dimensional array will be used
• Separate queue for each priority number
Queue size
Priority
number
Priority Queue Implementation with
Arrays
Priority Queue Implementation with
Array - Deletion
• Find first non-empty queue
• Remove front element of that queue
Multiple Queues
• Array sizing an issue
– Less size result in frequent overflows
– More size result in wastage of space
Applications of Queue
• Waiting list of shared resources e.g., printing
• Buffers on MP3 players, play lists
• Operating system task scheduling
Applications of Queue
E. Ben Hamida and M. A. Javed, "Channel-Aware ECDSA Signature Verification of Basic Safety Messages with K-Means Clustering in
VANETs," 2016 IEEE 30th International Conference on Advanced Information Networking and Applications (AINA), Crans-Montana,
Switzerland, 2016, pp. 603-610, doi: 10.1109/AINA.2016.51.
Applications of Queue
E. Ben Hamida and M. A. Javed, "Channel-Aware ECDSA Signature Verification of Basic Safety Messages with K-Means Clustering in
VANETs," 2016 IEEE 30th International Conference on Advanced Information Networking and Applications (AINA), Crans-Montana,
Switzerland, 2016, pp. 603-610, doi: 10.1109/AINA.2016.51.
