Data Structures and Algorithms

Objectives
In this session, you will learn to:
Identify the features of queues
Implement the different types of queues
Apply queues to solve programming problems
Store and search data by using hashing

Ver. 1.0

Session 11

Data Structures and Algorithms

Defining Queues
Consider a situation where you have to create an
application with the following set of requirements:
Application should serve the requests of multiple users.
At a time, only one request can be processed.
The request, which came first should be given priority.

However, the rate at which the requests are received is

much faster than the rate at which they are processed.
Therefore, you need to store the request somewhere until they
are processed.

How can you solve this problem?

You can solve this problem by storing the requests in such a
manner so that they are retrieved in the order of their arrival.
A data structure called queue stores and retrieves data in the
order of its arrival.
A queue is also called a FIFO list.
Ver. 1.0

Session 11

Data Structures and Algorithms

Defining Queues (Contd.)
Elements
Queue
is aare
listinserted
of elements
at theinrear
which
end
anand
element
deleted
is inserted
from the
at one
front
end.
end and deleted from the other end of the queue.

REAR

FRONT

Ver. 1.0

Session 11

Data Structures and Algorithms

Just a minute
A queue is also known as a __________ list.

Answer:
FIFO

Ver. 1.0

Session 11

Data Structures and Algorithms

Identifying Various Operations on Queues
Various operations implemented on a queue are:
Insert
Delete

REAR

FRONT

Ver. 1.0

Session 11

Data Structures and Algorithms

Identifying Various Operations on Queues
(Contd.)
Insert: It refers to the addition of an item in the queue.
Suppose you want to add an item F in the following queue.
Since the items are inserted at the rear end, therefore, F is
inserted after D.
Now F becomes the rear end.

REAR REAR

FRONT

Ver. 1.0

Session 11

Data Structures and Algorithms

Identifying Various Operations on Queues
(Contd.)
Delete: It refers to the deletion of an item from the queue.
Since the items are deleted from the front end, therefore, item
B is removed from the queue.
Now A becomes the front end of the queue.

FRONT FRONT

Ver. 1.0

REAR

Session 11

Data Structures and Algorithms

Just a minute
Queues are the data structures in which data can be added
at one end called ______ and deleted from the other end
called _________.

Answer:
rear, front

Ver. 1.0

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array
Problem Statement:
Consider a scenario of a bank. When the customer visits the
counter, a request entry is made and the customer is given a
request number. After receiving request numbers, a customer
has to wait for some time. The customer requests needs to be
queued into the system and processed on the basis of their
arrival. You need to implement an appropriate data storage
mechanism to store these requests in the system.

Ver. 1.0

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
How
cantrack
solve
this
To
keep
insert
ayou
request
of thenumber,
rearproblem?
andyou
front
need
positions,
to perform
you the
need to
declare
following
two
steps:
integer
and FRONT.
You can
solve
thisvariables,
problem byREAR
implementing
a queue.
Increment
value
of REAR
byan
1. array that
If
the
queue
isthe
empty,
REAR
and
FRONT
are set
to 1.
Let
us
implement
a queue
using
stores
these
Insertnumbers
the element
at index
in the array.
request
in the
orderposition
of theirREAR
arrival.

FRONT = 1
REAR = 1

Ver. 1.0

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
Write an algorithm to insert values in a queue implemented
through array.
Algorithm to insert values in a queue:
1. If the queue is empty:
a. Set FRONT = 0.

2. Increment REAR by 1.
3. Store the element at index position REAR in the array.

Ver. 1.0

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
Let us now insert request numbers
the following
queue.3
Requestinnumber
generated

FRONT = 1
REAR = 1

If the queue is empty:

a.

Set FRONT = 0.

2.

Increment REAR by 1.

3.

Store the element at index position

REAR in the array.

10
0

Ver. 1.0

1.

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
1.

Request number generated

FRONT = 1
REAR = 1

a.

Set FRONT = 0.

2.

Increment REAR by 1.

3.

Store the element at index position

REAR in the array.

10
0

Ver. 1.0

If the queue is empty:

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
1.

Request number generated

a.

FRONT = 0

FRONT = 1
REAR = 1

Set FRONT = 0.

2.

Increment REAR by 1.

3.

Store the element at index position

REAR in the array.

10
0

Ver. 1.0

If the queue is empty:

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
1.

Request number generated

FRONT = 0

REAR = 1

a.

REAR = 0

Set FRONT = 0.

2.

Increment REAR by 1.

3.

Store the element at index position

REAR in the array.

10
0

Ver. 1.0

If the queue is empty:

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
1.

Request number generated

FRONT = 0

If the queue is empty:

a.

REAR = 0

Set FRONT = 0.

2.

Increment REAR by 1.

3.

Store the element at index position

REAR in the array.

310
0

Insertion complete

Ver. 1.0

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
1.

Request number generated

FRONT = 0

If the queue is empty:

a.

REAR = 0

Set FRONT = 0.

2.

Increment REAR by 1.

3.

Store the element at index position

REAR in the array.

310
0

Ver. 1.0

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
1.

Request number generated

FRONT = 0

If the queue is empty:

a.

REAR = 0

Set FRONT = 0.

2.

Increment REAR by 1.

3.

Store the element at index position

REAR in the array.

310
0

Ver. 1.0

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
1.

Request number generated

FRONT = 0

If the queue is empty:

a.

REARREAR
=0 =1

Set FRONT = 0.

2.

Increment REAR by 1.

3.

Store the element at index position

REAR in the array.

310
0

Ver. 1.0

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
1.

Request number generated

FRONT = 0

a.

REAR = 1

310

If the queue is empty:

Set FRONT = 0.

2.

Increment REAR by 1.

3.

Store the element at index position

REAR in the array.

Insertion complete

Ver. 1.0

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
1.

Request number generated

FRONT = 0

Ver. 1.0

a.

REAR = 1

310

If the queue is empty:

Set FRONT = 0.

2.

Increment REAR by 1.

3.

Store the element at index position

REAR in the array.

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
1.

Request number generated

FRONT = 0

Ver. 1.0

a.

REAR = 1

310

If the queue is empty:

Set FRONT = 0.

2.

Increment REAR by 1.

3.

Store the element at index position

REAR in the array.

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
1.

Request number generated

FRONT = 0

Ver. 1.0

a.

REAR = REAR
1
=2

310

If the queue is empty:

Set FRONT = 0.

2.

Increment REAR by 1.

3.

Store the element at index position

REAR in the array.

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
1.

Request number generated

FRONT = 0

a.

REAR = 2

310

If the queue is empty:

Set FRONT = 0.

2.

Increment REAR by 1.

3.

Store the element at index position

REAR in the array.

Insertion complete

Ver. 1.0

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
1.

Request number generated

FRONT = 0

Ver. 1.0

10

a.

REAR = 2

310

If the queue is empty:

Set FRONT = 0.

2.

Increment REAR by 1.

3.

Store the element at index position

REAR in the array.

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
1.

Request number generated

FRONT = 0

Ver. 1.0

10

a.

REAR = 2

310

If the queue is empty:

Set FRONT = 0.

2.

Increment REAR by 1.

3.

Store the element at index position

REAR in the array.

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
1.

Request number generated

FRONT = 0

Ver. 1.0

10

a.

REAR = REAR
2
=3

310

If the queue is empty:

Set FRONT = 0.

2.

Increment REAR by 1.

3.

Store the element at index position

REAR in the array.

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
1.

Request number generated

FRONT = 0

10

a.

REAR = 3

310

10

If the queue is empty:

Set FRONT = 0.

2.

Increment REAR by 1.

3.

Store the element at index position

REAR in the array.

Insertion complete

Ver. 1.0

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
1.

Request number generated

FRONT = 0

Ver. 1.0

15

a.

REAR = 3

310

10

If the queue is empty:

Set FRONT = 0.

2.

Increment REAR by 1.

3.

Store the element at index position

REAR in the array.

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
1.

Request number generated

FRONT = 0

Ver. 1.0

15

a.

REAR = 3

310

10

If the queue is empty:

Set FRONT = 0.

2.

Increment REAR by 1.

3.

Store the element at index position

REAR in the array.

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
1.

Request number generated

FRONT = 0

Ver. 1.0

15

a.

REAR =REAR
3
=4

310

10

If the queue is empty:

Set FRONT = 0.

2.

Increment REAR by 1.

3.

Store the element at index position

REAR in the array.

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
1.

Request number generated

15

FRONT = 0

If the queue is empty:

a.

REAR = 4

310

10

15

Set FRONT = 0.

2.

Increment REAR by 1.

3.

Store the element at index position

REAR in the array.

Insertion complete

Ver. 1.0

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
The requests stored in the queue are served on a
first-come-first-served basis.
As the requests are being served, the corresponding
request numbers needs to be deleted from the queue.

Ver. 1.0

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
Write an algorithm to delete an element from a queue
implemented through array.
Algorithm to delete an element from a queue:

Ver. 1.0

1.

Retrieve the element at index FRONT.

2.

Increment FRONT by 1.

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
OneLet
request
processed
us see
how requests are

deleted from the queue once they

get processed.
FRONT = 0

Ver. 1.0

1.

Retrieve the element at index

FRONT.

2.

Increment FRONT by 1.

REAR = 4

10

15

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
One request processed

FRONT = 0

Ver. 1.0

1.

Retrieve the element at index

FRONT.

2.

Increment FRONT by 1.

REAR = 4

310

10

15

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)

FRONT = 0FRONT = 1

1.

Retrieve the element at index

FRONT.

2.

Increment FRONT by 1.

REAR = 4

10

10

15

Delete operation complete

Ver. 1.0

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
One request processed

FRONT = 1

Ver. 1.0

1.

Retrieve the element at index

FRONT.

2.

Increment FRONT by 1.

REAR = 4

10

10

15

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
One request processed

FRONT = 1

Ver. 1.0

1.

Retrieve the element at index

FRONT.

2.

Increment FRONT by 1.

REAR = 4

10

10

15

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)

FRONT = FRONT
1
=2

10
0

1.

Retrieve the element at index

FRONT.

2.

Increment FRONT by 1.

REAR = 4

10

15

Delete operation complete

Ver. 1.0

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
To implement
insert or
delete
need
to
As
you delete an
elements
from
the operation,
queue, theyou
queue
moves
increment
the values of REAR or FRONT by one,
down
the array.
respectively.
The disadvantage of this approach is that the storage space
However,
these values
are never
in
the beginning
is discarded
and decremented.
never used again.
Consider the following queue.
FRONT = 3

10
0

REAR = 4

10

15

REAR is at the last index position.

Therefore, you cannot insert elements in this queue, even
though there is space for them.
This means that all the initial vacant positions go waste.
Ver. 1.0

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
How
can youFRONT
solve this
problem?
To
maintain
at zero
index position, every delete
operation
would
require
you to shift
all the
succeeding
One way
to solve
this problem
is to keep
FRONT
always at the
elements
zero index
in the
position.
array one position left.
to the following
queue.
Let Refer
us implement
a delete
operation on the following queue.

FRONT = 0

Ver. 1.0

REAR = 3

310

10

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
To maintain FRONT at zero index position, every delete
operation would require you to shift all the succeeding
elements in the array one position left.
Let us implement a delete operation on the following queue.

FRONT = 0

Ver. 1.0

REAR = 3

510

10

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
To maintain FRONT at zero index position, every delete
operation would require you to shift all the succeeding
elements in the array one position left.
Let us implement a delete operation on the following queue.

FRONT = 0

Ver. 1.0

REAR = 3

510

10

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
To maintain FRONT at zero index position, every delete
operation would require you to shift all the succeeding
elements in the array one position left.
Let us implement a delete operation on the following queue.

FRONT = 0

Ver. 1.0

REAR = 3

510

10

10

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
To maintain FRONT at zero index position, every delete
operation would require you to shift all the succeeding
elements in the array one position left.
Let us implement a delete operation on the following queue.

FRONT = 0

Ver. 1.0

REAR = 2REAR = 3

510

10

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
Advantage of this
Disadvantage
of this
approach:
approach:
Every
It
enables
delete
youoperation
to utilize requires
all the empty
you topositions
shift all the
in an
succeeding
array.
Therefore,inunlike
elements
the queue
the previous
one position
case,left.
there is no wastage of
space.
If the list is lengthy, this can be very time consuming.

FRONT = 0

Ver. 1.0

REAR = 2

510

10

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
An effective way to solve this problem is to implement the
queue in the form of a circular array.
In this approach, if REAR is at the last index position and if
there is space in the beginning of an array, then you can set
the value of REAR to zero and start inserting elements from
the beginning.
REAR = 0

FRONT = 3

REAR = 4

Insert 5
510
0

Ver. 1.0

10

15

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
The cells in the array are treated as if they are arranged in a
ring.

[0]

[4]

[1]

10

REAR = 3

[3]

Ver. 1.0

FRONT = 2

[2]

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
Let
Write
usan
now
algorithm
implement
to insert
a few
values
operations
ingenerated
a queueon
implemented
the
Requestinsert
number
15 following
circular
as a circular
queue:
array.
FRONT = 1

Ver. 1.0

REAR = 3

10

20

23

10

1.

If the queue is empty (If FRONT= 1):

a.
b.
c.

2.

If REAR is at the last index position:

a.
b.

Set FRONT = 0
Set REAR = 0
Go to step 4

Set REAR = 0
Go to step 4

3.

Increment REAR by 1

4.

Queue[REAR] = element

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
1.

Request number generated

FRONT = 1

Ver. 1.0

15
REAR = 3

10

20

23

10

If the queue is empty (If FRONT= 1):

a.
b.
c.

2.

If REAR is at the last index position:

a.
b.

Set FRONT = 0
Set REAR = 0
Go to step 4

Set REAR = 0
Go to step 4

3.

Increment REAR by 1

4.

Queue[REAR] = element

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
1.

Request number generated

FRONT = 1

Ver. 1.0

15
REAR = 3

10

20

23

10

If the queue is empty (If FRONT= 1):

a.
b.
c.

2.

If REAR is at the last index position:

a.
b.

Set FRONT = 0
Set REAR = 0
Go to step 4

Set REAR = 0
Go to step 4

3.

Increment REAR by 1

4.

Queue[REAR] = element

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
1.

Request number generated

FRONT = 1

Ver. 1.0

15
REARREAR
=3 =4

10

20

23

10

If the queue is empty (If FRONT= 1):

a.
b.
c.

2.

If REAR is at the last index position:

a.
b.

Set FRONT = 0
Set REAR = 0
Go to step 4

Set REAR = 0
Go to step 4

3.

Increment REAR by 1

4.

Queue[REAR] = element

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
1.

Request number generated

15

FRONT = 1

REAR = 4

10

20

23

10

a.
b.
c.
2.

Set FRONT = 0
Set REAR = 0
Go to step 4

If REAR is at the last index position:

a.
b.

15
4

If the queue is empty (If FRONT= 1):

Set REAR = 0
Go to step 4

3.

Increment REAR by 1

4.

Queue[REAR] = element

Insertion complete

Ver. 1.0

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
1.

Request number generated

FRONT = 1

Ver. 1.0

17
REAR = 4

10

20

23

10

a.
b.
c.
2.

Set FRONT = 0
Set REAR = 0
Go to step 4

If REAR is at the last index position:

a.
b.

15
4

If the queue is empty (If FRONT= 1):

Set REAR = 0
Go to step 4

3.

Increment REAR by 1

4.

Queue[REAR] = element

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
1.

Request number generated

FRONT = 1

Ver. 1.0

17
REAR = 4

10

20

23

10

a.
b.
c.
2.

Set FRONT = 0
Set REAR = 0
Go to step 4

If REAR is at the last index position:

a.
b.

15
4

If the queue is empty (If FRONT= 1):

Set REAR = 0
Go to step 4

3.

Increment REAR by 1

4.

Queue[REAR] = element

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
1.

Request number generated

FRONT = 1

Ver. 1.0

17
REAR = 4

10

20

23

10

a.
b.
c.
2.

Set FRONT = 0
Set REAR = 0
Go to step 4

If REAR is at the last index position:

a.
b.

15
4

If the queue is empty (If FRONT= 1):

Set REAR = 0
Go to step 4

3.

Increment REAR by 1

4.

Queue[REAR] = element

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
1.

Request number generated

REAR = 0

Ver. 1.0

FRONT = 1

17
REAR = 4

10

20

23

10

a.
b.
c.
2.

Set FRONT = 0
Set REAR = 0
Go to step 4

If REAR is at the last index position:

a.
b.

15
4

If the queue is empty (If FRONT= 1):

Set REAR = 0
Go to step 4

3.

Increment REAR by 1

4.

Queue[REAR] = element

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
1.

Request number generated

REAR = 0

Ver. 1.0

17

FRONT = 1

a.
b.
c.
2.

10

20

23

10

Set FRONT = 0
Set REAR = 0
Go to step 4

If REAR is at the last index position:

a.
b.

15
4

If the queue is empty (If FRONT= 1):

Set REAR = 0
Go to step 4

3.

Increment REAR by 1

4.

Queue[REAR] = element

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
1.

Request number generated

REAR = 0

17

FRONT = 1

a.
b.
c.
2.

17
10

20

23

10

Set FRONT = 0
Set REAR = 0
Go to step 4

If REAR is at the last index position:

a.
b.

15
4

If the queue is empty (If FRONT= 1):

Set REAR = 0
Go to step 4

3.

Increment REAR by 1

4.

Queue[REAR] = element

Insertion complete

Ver. 1.0

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
1.

Request number generated

REAR = 0

Ver. 1.0

25

FRONT = 1

a.
b.
c.
2.

17
10

20

23

10

Set FRONT = 0
Set REAR = 0
Go to step 4

If REAR is at the last index position:

a.
b.

15
4

If the queue is empty (If FRONT= 1):

Set REAR = 0
Go to step 4

3.

Increment REAR by 1

4.

Queue[REAR] = element

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
1.

Request number generated

REAR = 0

Ver. 1.0

25

FRONT = 1

a.
b.
c.
2.

17
10

20

23

10

Set FRONT = 0
Set REAR = 0
Go to step 4

If REAR is at the last index position:

a.
b.

15
4

If the queue is empty (If FRONT= 1):

Set REAR = 0
Go to step 4

3.

Increment REAR by 1

4.

Queue[REAR] = element

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
1.

Request number generated

REAR = 0

Ver. 1.0

25

FRONT = 1

a.
b.
c.
2.

17
10

20

23

10

Set FRONT = 0
Set REAR = 0
Go to step 4

If REAR is at the last index position:

a.
b.

15
4

If the queue is empty (If FRONT= 1):

Set REAR = 0
Go to step 4

3.

Increment REAR by 1

4.

Queue[REAR] = element

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
1.

Request number generated

REAR = 0

25

FRONT = 1

a.
b.
c.
2.

17
10

20

23

10

Set FRONT = 0
Set REAR = 0
Go to step 4

If REAR is at the last index position:

a.
b.

15
4

If the queue is empty (If FRONT= 1):

Set REAR = 0
Go to step 4

3.

Increment REAR by 1

4.

Queue[REAR] = element

Before
Inserting
REAR cannot
implementing
an element
be incremented
in
anainsert
full queue
operation,
because
leads
the
you
toqueue
queue
should
isoverflow.
always
full.
check for the
queue full condition.

Ver. 1.0

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
The conditions for queue full are as follows:

If FRONT = 0 and REAR

is at the last index position
FRONT = 0

OR

REAR = 4

310

10

Ver. 1.0

If FRONT = REAR + 1

REAR = 2

FRONT = 3

15

17
10

20

23

10

15

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
Modified algorithm for inserting an
element in a circular queue.

1.

If the queue is full:

a.
b.

2.

If queue is empty (If FRONT = 1):

a.
b.
c.

1.

Set FRONT = 0
Set REAR = 0
Go to Step 5

If REAR is at the last index position:

a.
b.

Ver. 1.0

Display Queue overflow

Exit

Set REAR = 0
Go to step 5

2.

Increment REAR by 1

3.

Queue[REAR] = element

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
Now let
implement
a delete operation
on a queue
Write
anus
algorithm
to implement
delete operation
in a queue
in the
form ofarray.
a circular array.
implemented as
a circular
To delete an element, you need to increment the value of
FRONT by one. This is same as that of a linear queue.
However, if the element to be deleted is present at the last
index position, then the value FRONT is reset to zero.
If there is only one element present in the queue, then the
value of FRONT and REAR is set to 1.

Ver. 1.0

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
Algorithm to delete an element
from a circular queue.

REAR = 1

17
10
0

Ver. 1.0

FRONT = 4

20
1

1.

a.
b.
c.
2.

3.

Set FRONT = 1
Set REAR = 1
Exit

If FRONT is at the last index

position:
a.
b.

15
2

If there is only one element in the

queue:

Set FRONT = 0
Exit

Increment FRONT by 1

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
One request processed

1.

If there is only one element in the

queue:
a.
b.
c.

REAR = 1

17
10
0

Ver. 1.0

FRONT = 4

20
1

2.

If FRONT is at the last index

position:
a.
b.

15
3.

Set FRONT = 1
Set REAR = 1
Exit

Set FRONT = 0
Exit

Increment FRONT by 1

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
One request processed

1.

If there is only one element in the

queue:
a.
b.
c.

REAR = 1

17
10
0

Ver. 1.0

FRONT = 4

20
1

2.

If FRONT is at the last index

position:
a.
b.

15
3.

Set FRONT = 1
Set REAR = 1
Exit

Set FRONT = 0
Exit

Increment FRONT by 1

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
One request processed

1.

If there is only one element in the

queue:
a.
b.
c.

REAR = 1

17
10
0

Ver. 1.0

FRONT = 4

20
1

2.

If FRONT is at the last index

position:
a.
b.

15
3.

Set FRONT = 1
Set REAR = 1
Exit

Set FRONT = 0
Exit

Increment FRONT by 1

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
One request processed

1.

If there is only one element in the

queue:
a.
b.
c.

FRONT = 0

17
10
0

Ver. 1.0

REAR = 1

FRONT = 4

20
1

2.

If FRONT is at the last index

position:
a.
b.

15
3.

Set FRONT = 1
Set REAR = 1
Exit

Set FRONT = 0
Exit

Increment FRONT by 1

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
One request processed

1.

If there is only one element in the

queue:
a.
b.
c.

FRONT = 0

17
10
0

2.

REAR = 1

If FRONT is at the last index

position:
a.
b.

20
2

3.

Set FRONT = 1
Set REAR = 1
Exit

Set FRONT = 0
Exit

Increment FRONT by 1

Deletion complete

Ver. 1.0

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
One request processed

1.

If there is only one element in the

queue:
a.
b.
c.

FRONT = 0

17
10
0

Ver. 1.0

2.

REAR = 1

If FRONT is at the last index

position:
a.
b.

20
2

3.

Set FRONT = 1
Set REAR = 1
Exit

Set FRONT = 0
Exit

Increment FRONT by 1

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
One request processed

1.

If there is only one element in the

queue:
a.
b.
c.

FRONT = 0

17
10
0

Ver. 1.0

2.

REAR = 1

If FRONT is at the last index

position:
a.
b.

20
2

3.

Set FRONT = 1
Set REAR = 1
Exit

Set FRONT = 0
Exit

Increment FRONT by 1

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
One request processed

1.

If there is only one element in the

queue:
a.
b.
c.

FRONT = 0

17
10
0

Ver. 1.0

2.

REAR = 1

If FRONT is at the last index

position:
a.
b.

20
2

3.

Set FRONT = 1
Set REAR = 1
Exit

Set FRONT = 0
Exit

Increment FRONT by 1

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
One request processed

1.

If there is only one element in the

queue:
a.
b.
c.

FRONT = 1
FRONT = 0
REAR = 1

17
10
0

2.

If FRONT is at the last index

position:
a.
b.

20
2

3.

Set FRONT = 1
Set REAR = 1
Exit

Set FRONT = 0
Exit

Increment FRONT by 1

Deletion complete

Ver. 1.0

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
One request processed

1.

If there is only one element in the

queue:
a.
b.
c.

FRONT = 1
REAR = 1

10
0

Ver. 1.0

2.

If FRONT is at the last index

position:
a.
b.

20
2

3.

Set FRONT = 1
Set REAR = 1
Exit

Set FRONT = 0
Exit

Increment FRONT by 1

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
One request processed

1.

If there is only one element in the

queue:
a.
b.
c.

FRONT = 1
REAR = 1

10
0

Ver. 1.0

2.

If FRONT is at the last index

position:
a.
b.

20
2

3.

Set FRONT = 1
Set REAR = 1
Exit

Set FRONT = 0
Exit

Increment FRONT by 1

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
One request processed

1.

If there is only one element in the

queue:
a.
b.
c.

FRONT = 1
REAR = 1

FRONT = 1

10
0

Ver. 1.0

2.

If FRONT is at the last index

position:
a.
b.

20
2

3.

Set FRONT = 1
Set REAR = 1
Exit

Set FRONT = 0
Exit

Increment FRONT by 1

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
One request processed

1.

If there is only one element in the

queue:
a.
b.
c.

2.

REAR = 1

FRONT = 1
REAR = 1

Ver. 1.0

If FRONT is at the last index

position:
a.
b.

10
1

3.

Set FRONT = 1
Set REAR = 1
Exit

Set FRONT = 0
Exit

Increment FRONT by 1

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
One request processed

1.

If there is only one element in the

queue:
a.
b.
c.

2.

FRONT = 1
REAR = 1

If FRONT is at the last index

position:
a.
b.

10
1

3.

Set FRONT = 1
Set REAR = 1
Exit

Set FRONT = 0
Exit

Increment FRONT by 1

Deletion complete

Ver. 1.0

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
TheAt
queue
is now empty.
this stage,
if you try to

1.

implement a delete operation, it

will result in queue underflow.

a.
b.
c.
2.

FRONT = 1
REAR = 1

3.

Set FRONT = 1
Set REAR = 1
Exit

If FRONT is at the last index

position:
a.
b.

10
0

If there is only one element in the

queue:

Set FRONT = 0
Exit

Increment FRONT by 1

Therefore, before implementing a

delete operation, you first need to
check whether the queue is
empty or not.
Ver. 1.0

Session 11

Data Structures and Algorithms

Implementing a Queue Using an Array (Contd.)
The
Modified
condition
algorithm
for queue
for deleting
empty an
is:
element
from a
queue:
FRONT
= circular
1

1.

If the queue is empty: // If

// FRONT = 1
a.
Display Queue underflow
b.
Exit

2.

If there is only one element in the

queue: // If FRONT = REAR
a.
b.
c.

3.

If FRONT is at the last index

position:
a.
b.

4.

Ver. 1.0

Set FRONT = 1
Set REAR = 1
Exit

Set FRONT = 0
Exit

Increment FRONT by 1

Session 11

Data Structures and Algorithms

Just a minute
What is the advantage of implementing a queue in the form
of a circular array, instead of a linear array structure?

Answer:
If you implement a queue in the form of a linear array, you can
add elements only in the successive index positions. However,
when you reach the end of the queue, you cannot start
inserting elements from the beginning, even if there is space
for them at the beginning. You can overcome this
disadvantage by implementing a queue in the form of a
circular array. In this case, you can keep inserting elements till
all the index positions are filled. Hence, it solves the problem
of unutilized space.
Ver. 1.0

Session 11

Data Structures and Algorithms

Activity: Implementing a Queue Using Circular Array
Problem Statement:
Write a program to implement insert and delete operations on a
queue implemented in the form of a circular array.

Ver. 1.0

Session 11

Data Structures and Algorithms

Implementing a Queue Using a Linked List
What is the disadvantage of implementing a queue as an
array?
To implement a queue using an array, you must know the
maximum number of elements in the queue in advance.

To solve this problem, you should implement the queue in

the form of a linked list.

Ver. 1.0

Session 11

Data Structures and Algorithms

Implementing a Queue Using a Linked List (Contd.)
To keep track of the rear and front positions, you need to
declare two variables/pointers, REAR and FRONT, that will
always point to the rear and front end of the queue
respectively.
If the queue is empty, REAR and FRONT point to NULL.
FRONT
310

Ver. 1.0

REAR
5

15

Session 11

Data Structures and Algorithms

Inserting an Element in a Linked Queue
Write an algorithm to implement insert operation in a linked
queue.

Ver. 1.0

Session 11

Data Structures and Algorithms

Inserting an Element in a Linked Queue (Contd.)
Algorithminitially,
to insertthe
anqueue
Suppose
Requestis
number
3
element
in a linked queue.
empty.generated

REAR = NULL
FRONT = NULL

1.

Allocate memory for the new node.

2.

Assign value to the data field of the new

node.

3.

Make the next field of the new node point to

NULL.

4.

If the queue is empty, execute the following

steps:
a.
b.
c.

Ver. 1.0

Make FRONT point to the new node

Make REAR point to the new node
Exit

5.

Make the next field of REAR point to the new

node.

6.

Make REAR point to the new node.

Session 11

Data Structures and Algorithms

Inserting an Element in a Linked Queue (Contd.)

Request number generated

REAR = NULL
FRONT = NULL

1.

Allocate memory for the new node.

2.

Assign value to the data field of the new

node.

3.

Make the next field of the new node point to

NULL.

4.

If the queue is empty, execute the following

steps:
a.
b.
c.

Ver. 1.0

Make FRONT point to the new node

Make REAR point to the new node
Exit

5.

Make the next field of REAR point to the new

node.

6.

Make REAR point to the new node.

Session 11

Data Structures and Algorithms

Inserting an Element in a Linked Queue (Contd.)

Request number generated

REAR = NULL
FRONT = NULL

1.

Allocate memory for the new node.

2.

Assign value to the data field of the new

node.

3.

Make the next field of the new node point to

NULL.

4.

If the queue is empty, execute the following

steps:
a.
b.
c.

310

Ver. 1.0

Make FRONT point to the new node

Make REAR point to the new node
Exit

5.

Make the next field of REAR point to the new

node.

6.

Make REAR point to the new node.

Session 11

Data Structures and Algorithms

Inserting an Element in a Linked Queue (Contd.)

Request number generated

REAR = NULL
FRONT = NULL

1.

Allocate memory for the new node.

2.

Assign value to the data field of the new

node.

3.

Make the next field of the new node point to

NULL.

4.

If the queue is empty, execute the following

steps:
a.
b.
c.

310

Ver. 1.0

Make FRONT point to the new node

Make REAR point to the new node
Exit

5.

Make the next field of REAR point to the new

node.

6.

Make REAR point to the new node.

Session 11

Data Structures and Algorithms

Inserting an Element in a Linked Queue (Contd.)

Request number generated

REAR = NULL
FRONT = NULL

1.

Allocate memory for the new node.

2.

Assign value to the data field of the new

node.

3.

Make the next field of the new node point to

NULL.

4.

If the queue is empty, execute the following

steps:
a.
b.
c.

310

Ver. 1.0

Make FRONT point to the new node

Make REAR point to the new node
Exit

5.

Make the next field of REAR point to the new

node.

6.

Make REAR point to the new node.

Session 11

Data Structures and Algorithms

Inserting an Element in a Linked Queue (Contd.)

Request number generated

REAR = NULL
FRONT = NULL
FRONT

310

Ver. 1.0

1.

Allocate memory for the new node.

2.

Assign value to the data field of the new

node.

3.

Make the next field of the new node point to

NULL.

4.

If the queue is empty, execute the following

steps:
a.
b.
c.

Make FRONT point to the new node

Make REAR point to the new node
Exit

5.

Make the next field of REAR point to the new

node.

6.

Make REAR point to the new node.

Session 11

Data Structures and Algorithms

Inserting an Element in a Linked Queue (Contd.)

Request number generated

1.

Allocate memory for the new node.

2.

Assign value to the data field of the new

node.

3.

Make the next field of the new node point to

NULL.

4.

If the queue is empty, execute the following

steps:

REAR = NULL
FRONT REAR

310

Ver. 1.0

a.
b.
c.

Make FRONT point to the new node

Make REAR point to the new node
Exit

5.

Make the next field of REAR point to the new

node.

6.

Make REAR point to the new node.

Session 11

Data Structures and Algorithms

Inserting an Element in a Linked Queue (Contd.)

Request number generated

1.

Allocate memory for the new node.

2.

Assign value to the data field of the new

node.

3.

Make the next field of the new node point to

NULL.

4.

If the queue is empty, execute the following

steps:

FRONT REAR

310

a.
b.
c.

Make FRONT point to the new node

Make REAR point to the new node
Exit

5.

Make the next field of REAR point to the new

node.

6.

Make REAR point to the new node.

Insert operation complete

Ver. 1.0

Session 11

Data Structures and Algorithms

Inserting an Element in a Linked Queue (Contd.)

Request number generated

1.

Allocate memory for the new node.

2.

Assign value to the data field of the new

node.

3.

Make the next field of the new node point to

NULL.

4.

If the queue is empty, execute the following

steps:

FRONT REAR

310

Ver. 1.0

a.
b.
c.

Make FRONT point to the new node

Make REAR point to the new node
Exit

5.

Make the next field of REAR point to the new

node.

6.

Make REAR point to the new node.

Session 11

Data Structures and Algorithms

Inserting an Element in a Linked Queue (Contd.)

Request number generated

1.

Allocate memory for the new node.

2.

Assign value to the data field of the new

node.

3.

Make the next field of the new node point to

NULL.

4.

If the queue is empty, execute the following

steps:

FRONT REAR

310

Ver. 1.0

a.
b.
c.

Make FRONT point to the new node

Make REAR point to the new node
Exit

5.

Make the next field of REAR point to the new

node.

6.

Make REAR point to the new node.

Session 11

Data Structures and Algorithms

Inserting an Element in a Linked Queue (Contd.)

Request number generated

1.

Allocate memory for the new node.

2.

Assign value to the data field of the new

node.

3.

Make the next field of the new node point to

NULL.

4.

If the queue is empty, execute the following

steps:

FRONT REAR

310

Ver. 1.0

a.
b.
c.

510

Make FRONT point to the new node

Make REAR point to the new node
Exit

5.

Make the next field of REAR point to the new

node.

6.

Make REAR point to the new node.

Session 11

Data Structures and Algorithms

Inserting an Element in a Linked Queue (Contd.)

Request number generated

1.

Allocate memory for the new node.

2.

Assign value to the data field of the new

node.

3.

Make the next field of the new node point to

NULL.

4.

If the queue is empty, execute the following

steps:

FRONT REAR

310

Ver. 1.0

a.
b.
c.

510

Make FRONT point to the new node

Make REAR point to the new node
Exit

5.

Make the next field of REAR point to the new

node.

6.

Make REAR point to the new node.

Session 11

Data Structures and Algorithms

Inserting an Element in a Linked Queue (Contd.)

Request number generated

1.

Allocate memory for the new node.

2.

Assign value to the data field of the new

node.

3.

Make the next field of the new node point to

NULL.

4.

If the queue is empty, execute the following

steps:

FRONT REAR

310

Ver. 1.0

a.
b.
c.

510

Make FRONT point to the new node

Make REAR point to the new node
Exit

5.

Make the next field of REAR point to the new

node.

6.

Make REAR point to the new node.

Session 11

Data Structures and Algorithms

Inserting an Element in a Linked Queue (Contd.)

Request number generated

1.

Allocate memory for the new node.

2.

Assign value to the data field of the new

node.

3.

Make the next field of the new node point to

NULL.

4.

If the queue is empty, execute the following

steps:

FRONT REAR

310

Ver. 1.0

a.
b.
c.

510

Make FRONT point to the new node

Make REAR point to the new node
Exit

5.

Make the next field of REAR point to the new

node.

6.

Make REAR point to the new node.

Session 11

Data Structures and Algorithms

Inserting an Element in a Linked Queue (Contd.)

Request number generated

FRONT REAR

310

1.

Allocate memory for the new node.

2.

Assign value to the data field of the new

node.

3.

Make the next field of the new node point to

NULL.

4.

If the queue is empty, execute the following

steps:

REAR

510

a.
b.
c.

Make FRONT point to the new node

Make REAR point to the new node
Exit

5.

Make the next field of REAR point to the new

node.

6.

Make REAR point to the new node.

Insert operation complete

Ver. 1.0

Session 11

Data Structures and Algorithms

Deleting an Element from a Linked Queue
Write an algorithm to implement the delete operation on a
linked queue.

Ver. 1.0

Session 11

Data Structures and Algorithms

Deleting an Element from a Linked Queue (Contd.)
Algorithm
to implement delete
One
request processed
operation on a linked queue.

FRONT
310

Ver. 1.0

REAR
5

1.

If the queue is empty: // FRONT = NULL

a.
b.

Display Queue empty

Exit

2.

Mark the node marked FRONT as current

3.

Make FRONT point to the next node in its

sequence

4.

Release the memory for the node marked

as current

10

Session 11

Data Structures and Algorithms

Deleting an Element from a Linked Queue (Contd.)
One request processed

1.

If the queue is empty: // FRONT = NULL

a.
b.

FRONT
310

Ver. 1.0

REAR
5

Display Queue empty

Exit

2.

Mark the node marked FRONT as current

3.

Make FRONT point to the next node in its

sequence

4.

Release the memory for the node marked

as current

10

Session 11

Data Structures and Algorithms

Deleting an Element from a Linked Queue (Contd.)
One request processed

1.

If the queue is empty: // FRONT = NULL

a.
b.

FRONT
310

REAR
5

Display Queue empty

Exit

2.

Mark the node marked FRONT as current

3.

Make FRONT point to the next node in its

sequence

4.

Release the memory for the node marked

as current

10

current

Ver. 1.0

Session 11

Data Structures and Algorithms

Deleting an Element from a Linked Queue (Contd.)
One request processed

1.

If the queue is empty: // FRONT = NULL

a.
b.

FRONT
310

FRONT
5

REAR
7

Display Queue empty

Exit

2.

Mark the node marked FRONT as current

3.

Make FRONT point to the next node in its

sequence

4.

Release the memory for the node marked

as current

10

current

Ver. 1.0

Session 11

Data Structures and Algorithms

Deleting an Element from a Linked Queue (Contd.)
One request processed

1.

If the queue is empty: // FRONT = NULL

a.
b.

FRONT
3

current

REAR
7

Display Queue empty

Exit

2.

Mark the node marked FRONT as current

3.

Make FRONT point to the next node in its

sequence

4.

Release the memory for the node marked

as current

10

Delete operation complete

Memory released

Ver. 1.0

Session 11

Data Structures and Algorithms

Just a minute
How does the implementation of a linked list differ from that
of a linked queue?

Answer:
In a linked list, you can insert and delete elements anywhere in
the list. However, in a linked queue, insertion and deletion
takes place only from the ends. More specifically, insertion
takes place at the rear end and deletion takes place at the
front end of the queue.
Ver. 1.0

Session 11

Data Structures and Algorithms

Applications of Queues
Queues offer a lot of practical applications, such as:
Printer Spooling
CPU Scheduling
Mail Service
Keyboard Buffering
Elevator

Ver. 1.0

Session 11

Data Structures and Algorithms

Printer Spooling
A printer may receive multiple print requests in a short span
of time.
The rate at which these requests are received is much
faster than the rate at which they are processed.
Therefore, a temporary storage mechanism is required to
store these requests in the order of their arrival.
A queue is the best choice in this case, which stores the
print requests in such a manner so that they are processed
on a first-come-first-served basis.

Ver. 1.0

Session 11

Data Structures and Algorithms

CPU Scheduling
A CPU can process one request at a time.
The rate at which the CPU receives requests is usually
much greater than the rate at which the CPU processes the
requests.
Therefore, the requests are temporarily stored in a queue in
the order of their arrival.
Whenever CPU becomes free, it obtains the requests from
the queue.
Once a request is processed, its reference is deleted from
the queue.
The CPU then obtains the next request in sequence and the
process continues.
In a time sharing system, CPU is allocated to each request
for a fixed time period.
Ver. 1.0

Session 11

Data Structures and Algorithms

CPU Scheduling (Contd.)
All these requests are temporarily stored in a queue.
CPU processes each request one by one for a fixed time
period.
If the request is processed within that time period, its
reference is deleted from the queue.
If the request is not processed within that specified time
period, the request is shifted to the end of the queue.
CPU then processes the next request in the queue and the
process continues.

Ver. 1.0

Session 11

Data Structures and Algorithms

Mail Service
In various organizations, many transactions are conducted
through mails.
If the mail server goes down, and someone sends you a
mail, the mail is bounced back to the sender.
To avoid any such situation, many organizations implement
a mail backup service.
Whenever there is some problem with the mail server
because of which the messages are not delivered, the mail
is routed to the mails backup server.
The backup server stores the mails temporarily in a queue.
Whenever the mail server is up, all the mails are transferred
to the recipient in the order in which they arrived.

Ver. 1.0

Session 11

Data Structures and Algorithms

Keyboard Buffering
Queues are used for storing the keystrokes as you type
through the keyboard.
Sometimes the data, which you type through the keyboard
is not immediately displayed on the screen.
This is because during that time, the processor might be
busy doing some other task.
In this situation, the data is temporarily stored in a queue, till
the processor reads it.
Once the processor is free, all the keystrokes are read in
the sequence of their arrival and displayed on the screen.

Ver. 1.0

Session 11

Data Structures and Algorithms

Elevator
An elevator makes use of a queue to store the requests
placed by users.
Suppose the elevator is currently on the first floor. A user on
the ground floor presses the elevator button to request for
the elevator. At almost the same time a user on the second
floor also presses the elevator button.
In that case, the elevator would go to the floor on which the
button was pressed earlier, that is, the requests will be
processed on a FCFS basis.
However, if one of the users had been on the ground floor
and the other had been on the ninth floor, then irrespective
of who pressed the button first, the elevator would go to the
ground floor first because the distance to the ground floor is
much less than the distance to the ninth floor. In this case,
some sort of a priority queue would be required.
Ver. 1.0

Session 11

Data Structures and Algorithms

Implementing Hashing
Binary search algorithm has some disadvantages:
It works only on sorted lists.
It requires a way to directly access the middle element of the
list.

An alternate searching algorithm that overcomes these

limitations and provides good efficiency is hashing.

Ver. 1.0

Session 11

Data Structures and Algorithms

Defining Hashing
Suppose you have to search for the record corresponding to
a given key value in a given list of records.
To retrieve the desired record, you have to search
sequentially through the records until a record with the
desired key value is found.
This method is very time consuming, especially if the list is
very large.
An effective solution to search the record would be to
search it with the help of an offset address.
You can calculate the offset address of a record by using a
technique called hashing.

Ver. 1.0

Session 11

Data Structures and Algorithms

Defining Hashing (Contd.)
The fundamental principle of hashing is to convert a key to
an offset address to retrieve a record.
Conversion of the key to an address is done by a relation
(formula), which is known as a hashing function.
The process of searching a record using hashing can be
summarized as:
1. Given a key, the hash function converts it into a hash value (location)
within the range 1 to n, where n is the size of the storage (address)
space that has been allocated for the records.
2. The record is then retrieved at the location generated.

Ver. 1.0

Session 11

Data Structures and Algorithms

Limitations of Hashing
Two limitations of hashing are:
It may result in collision.
It does not allow sequential access.

Ver. 1.0

Session 11

Data Structures and Algorithms

Selecting a Hash Function
Two principal criteria in selecting a hash function are:
It should be quick and easy to compute.
It should achieve a uniform distribution of keys in the address
space.

There are various techniques that can be used to design a

hash function:
Truncation method
Modular method
Mid Square method
Folding method

Ver. 1.0

Session 11

Data Structures and Algorithms

Resolving Collision
A situation in which an attempt is made to store two keys at
the same position is known as collision.
Two records cannot occupy the same position. Therefore, a
collision situation needs to be taken care of.
Collision can be resolved by using a method called separate
chaining.

Ver. 1.0

Session 11

Data Structures and Algorithms

Determining the Efficiency of Hashing
Searching becomes faster using hashing as compared to
any other searching method.
The efficiency of hashing is ideally O(1).
However, because of collision, the efficiency of hashing gets
reduced.
The efficiency of hashing in this case depends on the quality
of the hash function.

Ver. 1.0

Session 11

Data Structures and Algorithms

Summary
In this session, you learned that:
A queue is linear data structure in which the elements are
inserted at the rear end and deleted from the front.
The various operation implemented on a queue are insert and
remove.
A queue can be implemented by using arrays or linked list.
A queue implemented in the form of a circular array overcomes
the problem of unutilized space encountered in queues
implemented by using a linear array.
A queue implemented by using a linked list is called a linked
queue.

Ver. 1.0

Session 11

Data Structures and Algorithms

Summary (Contd.)
Queues offer large number of applications in various fields
such as:
Printer spooling
CPU scheduling
Mail service
Keyboard buffering
Elevator

The fundamental principle of hashing is to convert a given key

value to an offset address to retrieve a record.
In hashing, conversion of the key to an address is done by a
relation (formula), which is known as a hashing function.
The situation in which the hash function generates the same
hash value for two or more keys is called collision.
The occurrence of collision can be minimized by using a good
hash function.
Ver. 1.0

Session 11

Data Structures and Algorithms

Summary (Contd.)
Two principle criteria in selecting a hash function are:
It should be easy and quick to compute.
It should achieve a uniform distribution of keys in the address
space.

There are various techniques that can be used to design a

hash function, some of which are:
Truncation method
Modular method
Mid Square method
Folding method

The problem of collision can be resolved by using a method

called separate chaining.

Ver. 1.0

Session 11