CS250 - Data Structures and
Algorithm
BESE-2A/B
Lecture 10
Aasma Zahid
Queue
10/4/2012 DSA - Fall 2012 - SEECS, NUST 2
Queue
• A linear data structure that is used for storing
and retrieval of data
• Storing and retrieval principle
– FIRST IN FIRST OUT (FIFO)
10/4/2012 DSA - Fall 2012 - SEECS, NUST 3
Example
• First one in line is the first to serve
10/4/2012 DSA - Fall 2012 - SEECS, NUST 4
Applications
• Real life examples
– Waiting in line
– Waiting on hold for tech support
• Applications related to Computer Science
– Threads
– Job scheduling (e.g. Round-Robin algorithm for
CPU allocation)
10/4/2012 DSA - Fall 2012 - SEECS, NUST 5
Queue Representation
Head:
Tail:
All items are
All new items
deleted from
are added on
this end
this end
10/4/2012 DSA - Fall 2012 - SEECS, NUST 6
First In First Out
rear
D rear
C rear C D
B rear B B C
rear front front front
A A front A A B
front
10/4/2012 DSA - Fall 2012 - SEECS, NUST 7
Queue Attributes
• Size
– Represents the total number of elements in a
queue
• Front
– Points to the first elements of queue
– Used for removal
• Rear
– Points to the last element of queue
– Used for insertion
10/4/2012 DSA - Fall 2012 - SEECS, NUST 8
Queue Operations
• Primarily two operations performed on both ends
• Enqueue
– Add an item at the back
of queue – using rear/tail
• Dequeue
– Remove an item from the
front of queue – using front/head
10/4/2012 DSA - Fall 2012 - SEECS, NUST 9
Queue Operations
• Enqueue(element) – add an element at the
end of the queue
• element Dequeue() – remove an element
from the front of the queue
• isEmpty() – check to see if queue is empty
• isFull() – check to see if queue is full
• FirstElement() – returns the first element in
queue without removing it
• Clear() – clear the queue
10/4/2012 DSA - Fall 2012 - SEECS, NUST 10
Choice of Implementation
• Array based Queue
– Maximum queue size is known ahead of time
• Linked List based Queue
– Maximum queue size unknown
10/4/2012 DSA - Fall 2012 - SEECS, NUST 11
Array based Queue
• Initialize
Front = -1 -1 -1 -1 -1 -1 Rear = -1
• Enqueue(5)
Front = 0 5 -1 -1 -1 -1 Rear = 0
• Enqueue(10)
Front = 0 5 10 -1 -1 -1 Rear = 1
• Enqueue(12)
Front = 0 5 10 12 -1 -1 Rear = 2
10/4/2012 DSA - Fall 2012 - SEECS, NUST 12
Array based Queue
• Dequeue()
Front = 1 -1 10 12 -1 -1 Rear = 2
• Enqueue(8)
Front = 1 -1 10 12 8 -1 Rear = 3
• Dequeue()
Front = 2 -1 -1 12 8 -1 Rear = 3
• Enqueue(15)
Front = 2 -1 -1 12 8 15 Rear = 4
• At the current state, can you enqueue anymore element?
10/4/2012 DSA - Fall 2012 - SEECS, NUST 13
Circular Queue
• Can be seen as circular queue
EMPTY QUEUE [2] [3] [2] [3]
J2 J3
[1] [4] [1] J1 [4]
[0] [5] [0] [5]
front = 0 front = 0
rear = 0 rear = 3
10/4/2012 DSA - Fall 2012 - SEECS, NUST 14
Circular Queue
• Use circular queue
– Reuse existing empty slots by rear and front
manipulation
– Mod operator
• Rear % (size – 1)
• Front % (size – 1)
10/4/2012 DSA - Fall 2012 - SEECS, NUST 15
Array based Circular Queue
• Initialize
Front = -1 -1 -1 -1 -1 -1 Rear = -1
• Enqueue(5)
Front = 0 5 -1 -1 -1 -1 Rear = 0
• Enqueue(10)
Front = 0 5 10 -1 -1 -1 Rear = 1
• Enqueue(12)
Front = 0 5 10 12 -1 -1 Rear = 2
10/4/2012 DSA - Fall 2012 - SEECS, NUST 16
Array based Circular Queue
• Dequeue()
Front = 1 -1 10 12 -1 -1 Rear = 2
• Enqueue(8)
Front = 1 -1 10 12 8 -1 Rear = 3
• Dequeue()
Front = 2 -1 -1 12 8 -1 Rear = 3
• Enqueue(15)
Front = 2 -1 -1 12 8 15 Rear = 4
10/4/2012 DSA - Fall 2012 - SEECS, NUST 17
Array based Circular Queue
• Enqueue(20)
Front = 2 20 -1 12 8 15 Rear = 0
• Enqueue(25)
Front = 2 20 25 12 8 15 Rear = 1
• Dequeue()
Front = 3 20 25 -1 8 15 Rear = 1
• Dequeue()
Front = 4 20 25 -1 -1 15 Rear = 1
10/4/2012 DSA - Fall 2012 - SEECS, NUST 18
Array based Circular Queue
• Dequeue()
Front = 4 20 25 -1 -1 15 Rear = 1
• Dequeue()
Front = 0 20 25 -1 -1 -1 Rear = 1
• Dequeue()
Front = 1 -1 25 -1 -1 -1 Rear = 1
• Dequeue()
Front = -1 -1 -1 -1 -1 -1 Rear = -1
10/4/2012 DSA - Fall 2012 - SEECS, NUST 19
Questions?
