1

CSC331- Data Structure & Algorithms

Lahore Garrison University

Lec9+10 Fall 2020
Instructor: Sahar Moin
Preamble (Past Lesson Brief)
• Infix, Prefix, Postfix notation, Conversions
• Precedence of Operators
• Postfix Expression Evaluation
• Queue introduction

2 Lahore Garrison University

Queues
• It is named queue as it behaves like a real-world queue, for example –
queue(line) of cars in a single lane, queue of people waiting at food
counter etc.
• Queue is an abstract data type with a bounded (predefined) capacity.
• It is a simple data structure that allows adding and removing elements in
a particular order.
• A queue is a linear structure for which items can be only inserted at one
end and removed at another end.
• The order is FIFO(First IN First OUT) or LILO(Last In Last Out).
Some types of Queue

• Simple Queue
• Circular Queue
• Priority Queue
Some Applications of Queue Data Structure –
• Queue is used when things but have to be processed in First In First Out
order. Like
 CPU scheduling, Disk Scheduling.
 Handling of interrupts in real-time systems. The interrupts are
handled in the same order as they arrive, First come first served.
 In real life, Call Center phone systems will use Queues, to hold
people calling them in an order, until a service representative is
free.
 When data is transferred asynchronously between two processes.
Queue is used for synchronization.
Queues
Queue Operations

Enqueue(X) – place X at the rear of the queue.

Dequeue() -- remove the front element and return it.
Front() -- return front element without removing it.
IsEmpty()-- return TRUE if queue is empty, FALSE otherwise
Enqueue
Enqueue is basically what insert operation is called in a queue. Enqueue or insertion always takes place at the rear end of a
queue.

To enqueue an element into the queue, first check if the queue is full or not. If it is full then just print overflow statement.
Otherwise increase the rear value of the queue and insert the element at the rear-th index. Note that front and rear are
initially set to -1. Steps:

Check if queue size is equal to rear-front value of the queue. If it is, it means the queue is full. Print "Overflow!". Otherwise
do the following:
Check if front value is equal to -1. If so, set it to 0.
Increase the value of rear by 1.
Add the value at the rear-th index of the array in queue.
Dequeue
• Dequeue is the deletion operation of a queue. It always takes place from the
front end.
• To dequeue and element you have to first check if the queue is empty or not.
If so, then print ""Underflow!". Otherwise just increase the value of front by
1. Steps:
Check if the front value is greater than rear value or if both are equal to -1. These two conditions indicate that the queue
is empty.
If so, print "Underflow". Otherwise do the following:
increase front by 1.
Queue Implementation using Array
 If we use an array to hold queue elements, both
insertions and removal at the front (start) of the array are
expensive.
 This is because we may have to shift up to “n” elements.
 For the stack, we needed only one end; for queue we
need both.
 To get around this, we will not shift upon removal of an
element.
Queue using Array

front rear
1 7 5 2
1 7 5 2
0 1 2 3 4 5 6 7

front rear
0 3
Queue using Array

enqueue(6)

front rear
1 7 5 2 6
1 7 5 2 6
0 1 2 3 4 5 6 7

front rear
0 4
Queue using Array

enqueue(8)

front rear
1 7 5 2 6 8
1 7 5 2 6 8
0 1 2 3 4 5 6 7
front rear
0 5
Queue using Array

dequeue()

front rear
7 5 2 6 8
7 5 2 6 8
0 1 2 3 4 5 6 7
front rear
1 5
Queue using Array

dequeue()

front rear
5 2 6 8
5 2 6 8
0 1 2 3 4 5 6 7

front rear
2 5
Queue using Array
enqueue(9)
enqueue(12)

front rear
5 2 6 8 9 12
5 2 6 8 9 12
0 1 2 3 4 5 6 7
front rear
enqueue(21) ?? 2 7
Algorithm for isEmpty( ) Algorithm for isFULL( )
Step 1: [Check for underflow] begin procedure isempty
If ( front -1 and rear -1 ) if front is less than MIN OR front is
greater than rear
empty
return true
Step 2: Else RETURN 0 else
contain a value return false
endif
end procedure
Algorithm for ENQUEUE Algorithm for DEQUEUE
Algorithm for enqueue operation procedure dequeue
procedure enqueue(data)
if queue is full if queue is empty
return underflow
return overflow
end if
endif
rear ← rear + 1 data = queue[front]
front ← front + 1
queue[rear] ← data
return true
return true
end procedure end procedure
#include<iostream>
using namespace std;
class Queue {
private: bool isEmpty() {
int front; if (front == -1 && rear == -1)
int rear; return true;
int arr[5]; else
return false;
public: }
Queue() { bool isFull() {
front = -1; if (rear == 4)
rear = -1; return true;
for (int i = 0; i < 5; i++) { else
arr[i] = 0; return false;
} }
}
ENQUEUE
DEQUEUE

front
main()
Complexity Analysis:

Time Complexity:
Operations Complexity
Enque(insertion) O(1)
Deque(deletion) O(1)
Front(Get front) O(1)
Rear(Get Rear) O(1)
Queue using Array
 We have inserts and removal running in constant time
but we created a new problem.
 Cannot insert new elements even though there are two
places available at the start of the array.
 Solution: allow the queue to “wrap around”.
Circular Queue
• Circular Queue is a linear data structure in which the operations are
performed based on FIFO (First In First Out) principle and the last position is
connected back to the first position to make a circle. It is also called ‘Ring
Buffer’. It is a type of Queue data structure which overcomes some drawback
of the simple queue data structure.
• In a Linear queue, once the queue is completely full, it’s not possible to insert
more elements. Even if we dequeue the queue to remove some of the
elements, until the queue is reset, no new elements can be inserted. You must
be wondering why?
Circular queue

1- why we need circular queue ?

2- when the rear point to the end, insertion will be denied even if room/ space is
available at front
3- this concept is used in queue as we discussed it earlier.
4- to over come this we can use Circular queue
5- Because the rare and front is concted at the same end in the form of queue
the logic we use to use circular queue is a[0] is comes after a[n-1], or after a[n-
1], a[0] apprared,where n is the actual size of array.
When we dequeue any element to remove it from the queue, we are
actually moving the front of the queue forward, thereby reducing the
overall size of the queue. And we cannot insert new elements, because
the rear pointer is still at the end of the queue. The only way is to reset
the linear queue, for a fresh start.
Standard Queue Operations –

• Enqueue() – Add item to the queue from the REAR.

• Dequeue() – Remove item from the queue from the FRONT.
• isFull() – Check if queue is full or not.
• isEmpty() – Check if queue empty or not.
• count() – Get number of items in the queue.
• A simple modification in the exist simple queue data structure algorithm/code
can convert it into a circular queue data structure.
Queue using Array
 Basic idea is to picture the array as a circular array.

0 1
front rear front
7 12 5 2 2
5 2 6 8 9 12
6 9 2 3 rear
0 1 2 3 4 5 6 7 8 6
5 4 7

noElements =6
Size =8
Queue using Array
enqueue(21)
0 1
front rear 21 front size
7 12 5 2 2 8
5 2 6 8 9 12 21
1 2 3 4 5 6 7 0
6 9 8 6
2 3 noElements
rear 7
5 4 0
void enqueue(int x)
{ size = 8
rear = 7
rear = (rear+1)%size;
rear = (7+1)%8 =0
array[rear] = x; noElements=6+1=7
noElements = noElements+1;
}
Queue using Array
enqueue(7)
0 1
front rear 21 7 front size
7 2 2 8
12 5
5 2 6 8 9 12 21 7
6 9 2
3 rear noElements
2 3 4 5 6 7 0 1 8 6
5 4 1 8
int isFull()
{ return noElements == size; // 8=8
}
int isEmpty()
{ return noElements == 0; // 0==0
}
Queue using Array
dequeue()
0 1
front rear 21 7 front size
7 2 2 8
12 5
5 2 6 8 9 12 21 7
2 3 4 5 6 7 0 1 6 9 2
3 noElements
8 6
8

int dequeue()
{
size = 8 size = 8
int x = array[front];
noElements = 8 noElements = 7
front = (front+1)%size; front= 2 front= 3
noElements = noElements-1; front = (2+1)%8 =3 front = (3+1)%8 =4
return x; noElements=8-1=7 noElements=7-1=6
}
Queue using Array
dequeue()
0 1
front rear 21 7 front size
7 12 2 4 8
6 8 9 12 217
6 9 3 rear noElements
2 3 4 5 6 7 0 1 8 6
int dequeue() 5 4 1 6
{
size = 8 size = 8
int x = array[front];
noElements = 8 noElements = 7
front = (front+1)%size; front= 2 front= 3
noElements = noElements-1; front = (2+1)%8 =3 front = (3+1)%8 =4
return x; noElements=8-1=7 noElements=7-1=6
}
Implementation of Circular
Queue using Arrays
ARRAY IMPLEMENTATION OF CIRCULAR QUEUE
Algorithm
Step 1: [Include All Header Files Required]

Step 2: [Define the array size as 5 and declare front and rear pointers]

Step 3: Declare the functions isEmpty() , isFull(), enqueue(), size(),dequeue(), peek() and view()]

Step 4: [Call the functions]

Choice :1 CALL enqueue()

Choice :2 CALL deenqueue()

Choice :3 CALL peek()

Choice :4 CALL size()

Choice :5 CALL view()

Algorithm for isEmpty( ) Algorithm for isFULL( )
Step 1: [Check for underflow]
Step 1: [Check for overflow]
If ( front -1 and rear -1 )
If (= (rear+1)% qsize ==front )
empty
RETURN -1
Step 2: Else RETURN 0
Step 2: Else RETURN 0
contain a value
[Finish the process]
Algorithm for ENQUEUE Algorithm for DEQUEUE
STEP 1: If[front= =rear] STEP 1: If[front = =rear]
1.1: temp=queue[front]
Initialize front=rear=-1 1.2: Initialize front=rear=-1
STEP 2: else rear=(rear+1)% qsize STEP 2:else
2.1: front=(front+1)% qsize
Set queue[rear] =value [return]
[return
Algorithm for View( )

STEP 1: If [front = =rear]

Write (“Queue is empty”)
STEP 2: else
[display elements]
0 1 2 3 4 5 6 7
21 7 5 2 6 8 9
int arr[8];
0 1 int rear =
21 7 int front = 0
7 2
5

6 9 2
3
8 6
5 4
Use of Queues
 Out of the numerous uses of the queues, one of the
most useful is simulation.
 A simulation program attempts to model a real-world
phenomenon.
 Many popular video games are simulations, e.g.,
SimCity, FlightSimulator
 Each object and action in the simulation has a
counterpart in real world.
Uses of Queues
 If the simulation is accurate, the result of the program
should mirror the results of the real-world event.
 Thus it is possible to understand what occurs in the real-
world without actually observing its occurrence.
 Let us look at an example. Suppose there is a bank with
four tellers.
Priority Queue
Priority Queue
• In computer science, a priority queue is an abstract data type similar to a regular queue
or stack data structure in which each element additionally has a "priority" associated
with it.
• In a priority queue, an element with high priority is served before an element with low
priority.
• In some implementations, if two elements have the same priority, they are served
according to the order in which they were enqueued, while in other implementations,
ordering of elements with the same priority is undefined.
What are the Characteristics of a Priority Queue?

A queue is termed as a priority queue if it has the following

characteristics:
• Each item has some priority associated with it.
• An item with the highest priority is moved at the front and deleted
first.
• If two elements share the same priority value, then the priority
queue follows the first-in-first-out principle for de queue
operation.
Priority Queue
Priority Queue Display