+
CS310 – Data Structure
Lecture – 08 – Queue
February 2, 2025
+
Objectives
At the end of this topic, you should be able to:
Analyze and define memory requirements for queue data structure.
Apply programming skills to implement queue data structures.
Develop an appropriate algorithm to perform different operations on queue
data structures.
For this purpose, we will discuss:
What is a Queue, and what are the major type of Queues
Main Queue operations
Learn how to implement a Queue as an array, and linked list
Discover some Queue applications
February 2, 2025
+
Recommended Readings
Chapter 6 – Queue, Dequeue
Chapter 9 – Priority Queue
February 2, 2025
+
What is a Queue
February 2, 2025
+
The Queue ADT
The Queue ADT stores arbitrary objects
Insertions and deletions follow the first-in first-out
scheme
Insertions are at the rear of the queue and removals are
at the front of the queue
Main queue operations:
enqueue(object): inserts an element at the end of the
queue
object dequeue(): removes and returns the element at the
front of the queue
February 2, 2025
+
The Queue ADT
Auxiliary queue operations:
getFront() – Return value at the Front of the Queue
getRear() – Return value at the Rear of the Queue
getSize() – Return number of elements in the Queue
isEmpty() – Return TRUE if Queue is Empty
isFull() – Return TRUE if Queue is Full
Boundary cases:
Attempting the execution of dequeue or first on an empty queue returns null
February 2, 2025
+
Main Queue Operations
Enqueue – To insert an element in Queue
Dequeue – To delete an element from Queue
February 2, 2025
+
Example
Operation Output Q
enqueue(5)
enqueue(3)
dequeue()
enqueue(7)
dequeue()
getfront()
getrear()
dequeue()
dequeue()
isEmpty()
enqueue(9)
enqueue(7)
getsize()
enqueue(3)
enqueue(5)
dequeue()
February 2, 2025
+
Example
Operation Output Q
enqueue(5) – (5)
enqueue(3) – (5, 3)
dequeue() 5 (3)
enqueue(7) – (3, 7)
dequeue() 3 (7)
getfront() 7 (7)
getrear() 7 (7)
dequeue() 7 ()
dequeue() null ()
isEmpty() true ()
enqueue(9) – (9)
enqueue(7) – (9, 7)
getsize() 2 (9, 7)
enqueue(3) – (9, 7, 3)
enqueue(5) – (9, 7, 3, 5)
dequeue() 9 (7, 3, 5)
February 2, 2025
+ Queue – Implementation
There are two ways to implement a Queue:
Using an Array,
First intuition: linearly
Better way: circularly
Using a Linked List
Either Linear
or Circular
February 2, 2025
+
Queue Implementation – Array
February 2, 2025
+
Queue Implementation – Array
The Front of the Queue is indicated by the
index front_index which is initialized with 0.
If the Queue is not empty, data[front_index]
Remove Insert
is the element in the front, next to be served front rea
(Dequeue) (Enqueue)
Dequeue off of the Queue at front_index++
r
The Rear of the Queue is indicated by the
index rear_index which is initialized with 0.
data[rear_index] is the location where the
next element will be added, first available
empty slot
Enqueue onto the Queue at
data[rear_index++] = value
February 2, 2025
+ Queue Implementation – Array (Java Class)
The EnQueue() and DeQueue() methods will be implemented in the Class February 2, 2025
+ Queue Implementation - Array (Algorithms)
Algorithm: isFull
Input: Array
Output: TRUE if count == size
Method:
1. Return (count == size)
2. End
February 2, 2025
+ Queue Implementation - Array (Algorithms)
Algorithm: isEmpty
Input: Array
Output: TRUE if count == 0
Method:
1. Return (count == 0)
2. End
February 2, 2025
+ Queue Implementation – Array (Algorithms)
Algorithm: EnQueue
Input: Array, value
Output: Update Array after EnQueue operation
Method:
1. If (isFull()) Then Display(“Queue is overflow”);
Return
[ End If]
2. Set Queue[rear_index] = value
3. Set rear_index = rear_index + 1
4. Set count = count + 1
5. End February 2, 2025
+ Queue Implementation – Array (Algorithms)
Algorithm: DeQueue
Input: Array
Output: Update Array after DeQueue operation
Method:
1. If (isEmpty()) Then Display(“Queue is underflow”);
Return [ End If]
2. Set temp = Queue[front_index]
3. Set front_index = front_index + 1
4. Set count = count - 1
5. Return temp
6. End February 2, 2025
+ Problem
Rear increases by 1 after each EnQueue( )
Front increases by 1 after each DeQueue( )
Rear Front
Now:
49 48 47 4 3 2 1 0
Rear Front
After Enqueue:
49 48 47 4 3 2 1 0
Rear Front
After Dequeue:
49 48 47 4 3 2 1 0
February 2, 2025
+ Problem
Suppose 50 calls to EnQueue() have been made, now the queue array
is full and Rear is 50
Assume 4 calls to DeQueue( ) are made
The queue is not full, but it is WRONG to add at position indexed by Rear
as it is out of bound! February 2, 2025
+ Solution 1 – change the DeQueue method
Algorithm: DeQueue
Input: Array
Output: Update Array after DeQueue operation (shift
everything to the left, front_index is always 0
Method:
1. Set temp = Queue[front_index]
2. Repeat for i = 0 to rear_index - 2
Very expensive, in the
3. Queue[i]=Queue[i+1] [End for]
worst case, n-1
4. Set rear_index = rear_index - 1 operations.
5. Set count = count - 1 We can be more
efficient!
6. Return [temp]
7. End
February 2, 2025
+ Solution 2 – A Circular Array
Allow the Front (and the Rear ) to
be moving around
When the Rear end is full and Front
part of the array has empty slots,
new insertions should go into the
front end
February 2, 2025
+ Queue Implementation - Circular Array
(Algorithms)
Algorithm: ENQueue
Input: Array, value
Output: Update Array after ENQueue operation
Method:
1. If (isFull()) Then Display(“Queue is overflow”);
Return
[ End If]
2. Set Queue[rear_index] = value
3. Set rear_index = (rear_index + 1) mod size
4. Set Count = Count + 1
5. End February 2, 2025
+ Queue Implementation - Circular Array
(Algorithms)
Algorithm: DEQueue
Input: Array
Output: Update Array after DEQueue operation
Method:
1. If (isEmpty()) Then Display(“Queue is underflow”);
Return
[ End If]
2. Set temp = Queue[front_index]
3. Set front_index = (front_index + 1) mod size
4. Set Count = Count – 1
5. Return temp
6. End
February 2, 2025
+
Queue Implementation – Array
Java Code
February 2, 2025
+ Linear Queue (array) 1- Create QueueArray Class that
implements queue using array
and implements the main
operations of the queue.
February 2, 2025
+
2- Create object from QueueArray Class.
You should specify the maximum size of the
queue.
February 2, 2025
+ Queue (Circular array)
February 2, 2025
+ Queue Implementation – Linked
List
February 2, 2025
+ Queue Implementation – Linked List
Linear or Circular Linked-List can be used to implement
a Queue. (No need to specify maximum size of the queue)
February 2, 2025
+ Queue – Linear Linked-List
Implementing a Queue using a Linked-List is fairly easy.
The Front of the Queue is the head
DeQueue EnQueue
The Rear of the Queue is at tail
Enqueue onto the Queue at rear
Dequeue off of the Queue at front
Head Tail
February 2, 2025
+ Queue – Linear Linked-List
February 2, 2025
+ Queue – Linear Linked-List (Java Class)
February 2, 2025
+ Queue – Linear Linked-List (Algorithms)
Algorithm: EnQueue
Input: Linear Linked-List, value
Output: Update Linear Linked-List after EnQueue
operation
Method:
1. Set Node newNode = new Node(Value, null)
2. If (isEmpty()) Then
Set front = newNode Set rear
= newNode
3. Else Set rear.Next=newNode Set rear =
newNode
February 2, 2025
4. [End If]
+ Queue – Linear Linked-List (Algorithms)
Algorithm: DeQueue
Input: Linear Linked-List
Output: Update Linear Linked-List after DeQueue
operation
Method:
1. If (isEmpty()) Then Display(“Queue is underflow”);
Return
[ End If]
2. Set front = front.Next
3. Set Count = Count – 1
4. If (Count == 0) then rear = null
5. End
February 2, 2025
+ Queue – Circular Linked List (Algorithms)
Algorithm: EnQueue
Input: Circular Linked-List, value
Output: Update the Circular Linked-List after EnQueue
operation
Method:
1. Set Node newNode = new Node(Value, null)
2. If (isEmpty()) Then
Set front = newNode, Set
rear = newNode
3. Else Set rear.Next=newNode, Set rear =
newNode
4. [End If] February 2, 2025
+ Queue – Circular Linked List (Algorithms)
Algorithm: DeQueue
Input: Circular Linked-List
Output: Update Circular Linked-List after DeQueue
operation
Method:
1. If (isEmpty()) Then Display(“Queue is underflow”);
Return
[ End If]
2. Set front = front.Next
3. Set rear.Next=front
4. Set Count = Count - 1
February 2, 2025
5. End
+
Two More Varieties of Queue
1. Double-Ended Queue (DEQueue)
Can add and delete from both front and rear
EnQueueFront, EnQueueRear, DeQueueFront, DeQueueRear
2. Priority Queue,
Add element in the queue
Delete the element with highest priority February 2, 2025
+ DEQueue – using Double Linked-List
February 2, 2025
+ DEQueue – using Linked-List
Algorithm: EnQueueRear
Input: Double Linked-List, value
Output: Update Double Linked-List after ENQueue operation
Method:
1. Set Node newNode = new Node(Value, null, null)
2. If (isEmpty()) Then
Set front = newNode Set rear
= newNode
3. Else Set rear. Next=newNode
Set newNode.Prev=rear, Set
rear = newNode
4. [End If] February 2, 2025
+ DEQueue – using Linked-List
Algorithm: EnQueueFront
Input: Double Linked-List, value
Output: Update Double Linked-List after EnQueue operation
Method:
1. Set Node newNode = new Node(Value, null, null)
2. If (isEmpty()) Then
Set front = newNode, Set rear
= newNode
3. Else Set front.Prev = newNode
Set newNode.Next = front, Set
front = newNode
4. [End If] February 2, 2025
+ DEQue – using Linked-List
Algorithm: DeQueueFront
Input: Double Linked-List
Output: Update Double Linked-List after DeQueue
operation
Method:
1. If (isEmpty()) Then Display(“Queue is underflow”);
Return
[ End If]
2. Set front = front.Next
3. Set front.previous=Null
4. Set Count = Count - 1
February 2, 2025
5. End
+ DEQue – using Linked-List
Algorithm: DeQueueRear
Input: Double Linked-List
Output: Update Double Linked-List after DeQueue
operation
Method:
1. If (isEmpty()) Then Display(“Queue is underflow”);
Return
[ End If]
2. Set rear = rear.Prev
3. Set rear.next = Null
4. Set Count = Count - 1
February 2, 2025
5. End
+ DEQue – using Linked-List
Example:
Operation Output Q
EnQueueFront(5)
EnQueueFront(3)
EnQueueRear(7)
getFirst()
DeQueueFront()
getLast()
DeQueueRear()
getSize()
DeQueueRear()
isEmpty()
February 2, 2025
+ DEQue – using Linked-List
Example:
Operation Output Q
EnQueueFront(5) - (5)
EnQueueFront(3) - (3,5)
EnQueueRear(7) - (3,5,7)
getFirst() 3 (3,5,7)
DeQueueFront() 3 (5,7)
getLast() 7 (5,7)
DeQueueRear() 7 (5)
getSize() 1 (5)
DeQueueRear() 5 ()
isEmpty() true ()
February 2, 2025
+
Priority Queue
February 2, 2025
+ Priority Queue
Priority Queue is a queue, where each element has a
"priority" associated with it. In a priority queue, an
element with high priority is served before an element
with low priority.
February 2, 2025
+ Two ways to keep the Priority Queue
Implementation with Implementation with a
an unsorted list sorted list
4 5 2 3 1 1 2 3 4 5
Performance: Performance:
insert takes 1 operation insert takes n operations
since we can insert the since we have to find the
item at the rear end place where to insert the
remove takes n operations item
since we have to remove takes 1 operation
traverse the entire queue since the element with
of length n to find the highest priority is at the
highest priority element front
February 2, 2025
+ Priorities
Each element in the Priority Queue is modeled as: Key-Value composite
known as entry. The Key indicates the priority of the element.
Example
A sequence of priority queue methods:
Unsorted List Sorted List Output Method (Key/priority,
value)
EnQueue(5,A)
EnQueue(9,C)
EnQueue(3,B)
DeQueue()
EnQueue(7,D)
DeQueue()
DeQueue()
DeQueue()
Dequeue()
IsEmpty() February 2, 2025
+ Priorities
Each element in the Priority Queue is modeled as: Key-Value composite known as
entry. The Key indicates the priority of the element.
Example
A sequence of priority queue methods:
Unsorted List Sorted List Output Method (Key/priority,
value)
{ (5,A) } { (5,A) } EnQueue(5,A)
{ (5,A) (9,C)} { (9,C) (5,A)} EnQueue(9,C)
{ (5, A) (9,C) (3,B) {(9,C) (5,A) EnQueue(3,B)
} (3,B)}
{ (5, A) (3,B) } {(5,A) (3,B)} (9,C) DeQueue()
{(5, A) (3,B) {(7,D) (5,A) EnQueue(7,D)
(7,D)} (3,B)}
{(5, A) (3,B)} {(5,A) (3,B)} (7,D) DeQueue()
{ (3, B) } { (3, B) } (5,A) DeQueue()
{} {} (3, B) DeQueue()
{} {} null Dequeue() February 2, 2025
+
Priority Queue Operations:
getMax() – Returns (but does not remove) a PQ entry (k,v) having
maximum key; returns null if the PQ is empty.
DeQueue/removeMax() – Removes and Returns an entry (k,v)
having maximum key; returns null if the PQ is empty.
EnQueue/insert(k,v) – Creates an entry (k,v) and inserts it in the
correct order. (entries are sorted by key)
isEmpty() – Returns TRUE if the PQ is Empty.
Size() – Returns the number of entries in the PQ.
February 2, 2025
+
Priority Queue Implementation
Using LinkedList (Sorted List)
February 2, 2025
+ Priority Queue – using Linear Linked-List
Algorithm: insert/ EnQueue
Input: Singly Linked-List, key, value
Output: Update Singly Linked-List after insert operation (insert in the correct
order)
Method:
1. Set Node newNode = new Node(value, key, null), Current = front , Prev=null
2. Repeat while (Current != null and key < Current.key) [ locate the correct
position]
1. Set Prev = Current
2. Set Current = Current.next,
[ End Loop ]
3. If (Prev=null) Then front = newNode Else Prev.next= newNode [End If]
4. Set newNode. next = current February 2, 2025
+ Queue – Linear Linked-List (Algorithms)
Algorithm: removeMax/DeQueue
Input: Linear Linked-List
Output: Update Linear Linked-List after DeQueue operation
Method:
1. If (isEmpty()) Then Display(“Queue is underflow”); Return null [ End
If]
2. Set Node temp=front
3. Set front = front.Next
4. Set size = size – 1
5. Return temp
6. End
February 2, 2025
+ Queue – Linear Linked-List (Algorithms)
Algorithm: getMax
Input: Linear Linked-List
Output: Node having the maximum key
Method:
1. If (isEmpty()) Then Display(“Queue is underflow”); Return null
Else Return front
[ End If]
2. End
February 2, 2025
+ Queue – Linear Linked-List (Algorithms)
Algorithm: isEmpty
Input: Linear Linked-List
Output: TRUE if size == 0
Method:
1. Return (size == 0)
2. End
February 2, 2025
PriorityQueue class
February 2, 2025
PriorityQueue class
February 2, 2025
PriorityQueue class
February 2, 2025
In the main(), create object from
PriorityQueue class
February 2, 2025
Key: 15 Value: BB
Outputs: Key: 10 Value: AA
Key: 9 Value: CC
Key: 5 Value: FF
Key: 3 Value: EE
Key: 2 Value: DD
Key: 1 Value: GG
BB has the max priority
Key: 15 Value: BB is deleted
-------Display---------
Key: 10 Value: AA
Key: 9 Value: CC
Key: 5 Value: FF
Key: 3 Value: EE
Key: 2 Value: DD
Key: 1 Value: GG
AA has the max priority
Key: 10 Value: AA is deleted
-------Display---------
Key: 9 Value: CC
Key: 5 Value: FF
Key: 3 Value: EE
Key: 2 Value: DD
Key: 1 Value: GG
February 2, 2025
+
Applications of Queues
February 2, 2025
+
Applications of Queues
Direct applications
Serving request of a single shared resource (printer, disk, CPU)
Call center phone system use Queue to hold people inline until a service
representative is free
Operating System maintain Queue of jobs that are ready to execute or
waiting for I/O operations
Indirect applications
Auxiliary data structure for algorithms
Component of other data structures
February 2, 2025
Application: Round Robin Schedulers
We can implement a round robin scheduler using a queue Q by
repeatedly performing the following steps:
1. e = Q.dequeue()
2. Service element e
3. Q.enqueue(e)
Queue
Dequeue Enqueue
Shared
Service
February 2, 2025
+
Practice
February 2, 2025
+
From the book
R-6.11: Suppose you have a DEQueue D containing the numbers
(1,2,3,4,5,6,7,8), in this order. Suppose further that you have an initially
empty queue Q. Give a code fragment that uses only D and Q (and no other
variables) and results in D storing the elements in the order (8,7,6,5,4,3,2,1).
R-6.12: Repeat the previous problem using the DEQueue D and an initially
empty stack S.
C-6.24: Implement a method with signature concatenate(LinkedQueue Q2) for
the LinkedQueue class that takes all elements of Q2 and appends them to the
end of the original queue.
February 2, 2025
+
R-6.11: Description:
D: (1,2,3,4,5,6,7,8) Q: Empty
Requirement: 1- only D and Q (and no other variables)
2- Contents of D should be in reversed order: (8,7,6,5,4,3,2,1).
EnQueueFront D EnQueueRear
8 7 6 5 4 3 2 1
DeQueueFront
DeQueueRear
1- DeQueue elements from D and EnQueue them into Q.
Q DeQueueFront or DeQueueRear?
2- DeQueue elements from Q and EnQueue them back
into D.
EnQueueFront or EnQueueRear?
February 2, 2025
+
R-6.11: Description:
EnQueueFront D EnQueueRear
8 7 6 5 4 3 2 1
DeQueueFront
DeQueueRear
1 2 3 4 5 6 7 8
EnQueueFront D EnQueueRear
1 2 3 4 5 6 7 8
DeQueueFront
DeQueueRear
February 2, 2025
+
R-6.11: Solution:
Algorithm: reverse D using Q
Input: D – (1,2,3,4,5,6,7,8)
Output: reversed D – (8,7,6,5,4,3,2,1)
Method:
Q=new Queue(8)
while(D is not Empty)
Q.EnQueue(D.DeQueueRear())
[EndLoop]
while(Q is not Empty)
D.EnQueueRear(Q.DeQueue())
[EndLoop]
End
February 2, 2025
+
R-6.12 : Description:
D: (1,2,3,4,5,6,7,8) Stack S: Empty
Requirement: 1- only D and S (and no other variables)
2- Contents of D should be in reversed order: (8,7,6,5,4,3,2,1).
EnQueueFront EnQueueRear
D
DeQueueFront
8 7 6 5 4 3 2 1
DeQueueRear
1- DeQueue elements from D and push them into S.
DeQueueFront or DeQueueRear?
S 2- Pop elements from S and EnQueue them back into
D.
EnQueueFront or EnQueueRear?
February 2, 2025
+
R-6.12 : Description:
EnQueueFront EnQueueRear
D
DeQueueFront
8 7 6 5 4 3 2 1
DeQueueRear
8
7
6
S
5
4
3
2
1
EnQueueFront EnQueueRear
D
DeQueueFront
1 2 3 4 5 6 7 8
DeQueueRear
February 2, 2025
+
R-6.12 : Solution:
Algorithm: reverse D using S
Input: D – (1,2,3,4,5,6,7,8)
Output: reversed D – (8,7,6,5,4,3,2,1)
Method:
S=new Stack(8)
while(D is not Empty)
S.push(D.DeQueueFront())
[EndLoop]
while(S is not Empty)
D.EnQueueRear(S.pop())
[EndLoop]
End
February 2, 2025
+
C-6.24: Solution:
Let Original Q1: (1,2,3,4,5,6,7,8)
Algorithm: concatenate Q1 and Q2
Input: Q2 – (9,10,11,12)
Output: Update Q1: (1,2,3,4,5,6,7,8,9,10,11,12) -> (Q1+Q2)
Method:
• While(Q2 is not Empty)
• Q1.EnQueue(Q2.DeQueue())
• [Endloop]
End
February 2, 2025
+
End of Queue - 07
February 2, 2025
