DATA STRUCTURES

CST201
Module 2 - Part 2 ,Final Version

Shiney Thomas,
CSE ,AJCE

1
CO# COs Module/s
mapped
CO1 Design an algorithm for a computational task and calculate the time/space M1
complexities of that algorithm

CO2 Use appropriate linear data structures to represent a data item required to be M2, M3
processed to solve real world problems effectively

CO3 Choose and manipulate data using non-linear data structures to design M4
solutions for various applications

CO4 Appreciate various hashing techniques to enable efficient access of data in M5

the given set.

CO5 Illustrate and compare various techniques for sorting to be used in specific M5
circumstances
2
 Module 2 Syllabus
Arrays and Searching
•Polynomial representation using Arrays
•Sparse matrix
•Stacks
•Queues-Circular Queues, Priority Queues,
Double Ended Queues
•Evaluation of Expressions
•Linear Search and Binary Search 3
QUEUES

4
 Queue
• A queue
• ordered list,
• linear structure
• insertions take place at one end, the rear,
• deletions take place at the other end, the front.
• Two operations on the queue are
• Insertion (ENQUEUE): Take place at the end called REAR
• Deletion (DEQUEUE): Take place at the other end called FRONT
• Restrictions on queue
• the first element which is inserted into the queue will be the first one to
be removed.
• queues are known as First In First Out (FIFO) lists.

5
6
 Representation of Queues
• Two ways to represent a queue in memory
– Using an Array
– Using Linked List

7
 Queue using Array
• One dimensional array, say Q[0 … n-1] can be
used to represent a Queue.
• Two pointers, FRONT and REAR indicate two
end of the queue.
• Insertion to the REAR end and deletion from
FRONT end. front rear

1 2 3 4 5 6 7
deletion insertion
8
 QUEUE
front=-1
Three states of Queue rear=-1
• Empty:
– FRONT= -1
– REAR= -1 front=0 rear=N-1
• Full:
– REAR=N-1 1 2 3 4 5

– FRONT=0
• Queue contains elements >=1
front=1
– FRONT<REAR rear=3
– Number of Elements=REAR-FRONT+1
2 3 4
9
 Operations on Queue
Insertion(ENQUEUE)
– Initially the queue will be initialized as Front= -1 and Rear =
-1
– Before inserting check whether the queue is full or not.
– If not full, then insert the element to location (Rear+1)
– Make sure that the Front always points to the first element
by incrementing the Front pointer when the first element
is inserted.

10
 Insertion(ENQUEUE)

Initially, Front = Rear =-1

Front = Rear =-1

11
 Insertion(ENQUEUE)

• Insert 1
Front = -1

Rear=0

12
 Insertion(ENQUEUE)

• Insert 1
Front = -1

1
Rear=0

13
 Insertion(ENQUEUE)

• Insert 1
Front = -1

1
Rear=0

• Change Front, so that it points to the first element

14
 Insertion(ENQUEUE)

• Insert 1

Front = 0
1
Rear=0

• Change Front, so that it points to the first element

15
 Insertion(ENQUEUE)

• Insert 2

Front=0 1
Rear=1

16
 Insertion(ENQUEUE)

• Insert 2

Front=0 1

Rear=1 2

17
 Insertion(ENQUEUE)

• Insert 3

Front=0 1
2
Rear=2

18
 Insertion(ENQUEUE)

• Insert 3

Front=0 1
2
Rear=2 3

19
 Insertion(ENQUEUE)

• Insert 4

Front=0 1
2
3
Rear=3

20
 Insertion(ENQUEUE)

• Insert 4

Front=0 1
2
3
Rear=3 4

21
 Insertion(ENQUEUE)

• Insert 5

Front=0 1 If Rear = N-1

2 Then queue
is full.
3 Insertion is
Rear=3 4 not possible

22
 Operations on Queue :Insertion(ENQUEUE)
Algorithm ENQUEUE Steps:
(ITEM) 1. If(REAR==N-1) then
Input: ITEM has to be inserted 1. print “ Queue is full”
into the REAR end of the 2. Else
queue. 1. If(REAR==-1 AND FRONT==-1)
Output: Queue is enriched //Queue is empty
with new element ITEM. 1. Set FRONT=0
Data Structure: Queue is 2. EndIf
implemented using 3. REAR=REAR+1
[Link] pointers FRONT 4. Q[REAR]=ITEM
and REAR are known 3. EndIf
4. Stop
23
 Operations on Queue
Deletion(DEQUEUE)
– Before deleting, check whether the queue is
empty or not.
– If not empty, then delete the element
– Make sure that the FRONT and REAR always
points to -1 by decrementing the pointers
when the last element is deleted.

24
 Deletion(DEQUEUE)

• Check whether queue is empty ?

– Rear>=Front and Front != -1 NOT EMPTY !!
– Or Front==-1 Front=0 1
2
3
Rear=3 4

25
 Deletion(DEQUEUE)

• Dequeue
1
Front=0
2
3
Rear=3 4

26
 Deletion(DEQUEUE)

• Dequeue

Front=1 2
3
Rear=3 4

27
 Deletion(DEQUEUE)

• Dequeue

Front=1
3
Rear=3 4

28
 Deletion(DEQUEUE)

• Dequeue

Front=2 3
Rear=3 4

29
 Deletion(DEQUEUE)

• Dequeue

Front=2
Rear=3 4

30
 Deletion(DEQUEUE)

• Dequeue

Front=3
Rear=3 4

31
 Deletion(DEQUEUE)

• Dequeue

Front=3
Rear=3
If (FRONT==REAR)
Set FRONT = -1
Set REAR = -1

32
 Deletion(DEQUEUE)

• Dequeue
Front= -1
Rear= -1

If (FRONT==REAR)
Set FRONT = -1
Set REAR = -1

33
 Operations on Queue :Deletion(DEQUEUE)
Steps:
Algorithm DEQUEUE() 1. If(FRONT==-1)
Input: A Queue with elements 1. Print “ Queue is empty”
and two pointers FRONT 2. Else
and REAR 1. ITEM=Q[FRONT]
2. If(FRONT==REAR)
Output: The deleted element
1. REAR=-1
is stored in the ITEM. 2. FRONT=-1
Data Structure: Queue is 3. Else
implemented by using array. 1. FRONT=FRONT+1
4. EndIf
3. EndIf
4. Stop 34
 Limitation
Disadvantages:
As we delete element from the queue, the queue moves down array.
So the storage space in the beginning is discarded and never used again.
Solution:
(1) Keep FRONT always at the zero index position.
To maintain the front at zero index position, every delete operation would
require shifting of all succeeding elements in the array by one position
Advantages: It enables us to utilize all the empty positions in an array i.e.
no wastage of space.
Disadvantages: Every delete operation requires shift all the succeeding
elements in the queue by one position . If the queue is lengthy, this can be
very time consuming
35
 Deletion(Modified DEQUEUE)

• Check whether queue is empty ?

• Rear>=front and front != -1 NOT EMPTY !!

Front= 1
0
2
3
Rear= 4
3

36
 Deletion(Modified DEQUEUE)

• M DEQUEUE
1

Front=
0
2
3
Rear= 4
3

37
 Deletion(Modified DEQUEUE)

• M DEQUEUE
1

Front= 2
0

3
Rear= 4
3

38
 Deletion(Modified DEQUEUE)

• M DEQUEUE
1

Front= 2
0
3

Rear= 4
3

39
 Deletion(Modified DEQUEUE)

• M DEQUEUE
1

Front= 2
0
3
4
Rear=
3

40
 Deletion(Modified DEQUEUE)

• M DEQUEUE
1

Front= 2
0
3
Rear= 4
2

41
 Modified Dequeue

3. Else
Algorithm MDEQUEUE() 1. ITEM=Q[FRONT]
Input: A Queue with elements and 2. If(FRONT==REAR)
two pointers FRONT and REAR 1. REAR=-1
Output: The deleted element is 2. FRONT=-1
stored in the ITEM. 3. Else
Data Structure: Queue is 1. While(i<REAR)
implemented by using array. 1. Q[i]=Q[i+1]
Steps: 2. I=i+1
2. EndWhile
1. Set i=0 3. REAR=REAR-1
2. If(FRONT==-1) 4. EndIf
1. Print “Queue is empty” 4. EndIf
5. Stop
42
 Different Queue Structures

1. Circular Queue
2. DEQUE
3. Priority Queue

43
 Circular Queue
• Problem with linear queue
– insertion will denied even if room is available at the front.
• Solution - Use circular queue

Physical Representation Logical representation

front
front rear rear

Q[0] Q[1] Q[2] Q[3] Q[3] Q[0]

Q[2] Q[1]
44
 Circular Queue
 Physically circular array same as ordinary array, say Q[0..N-1],
 Q[0] comes in between Q[1] and Q[N] .
 Both pointers will move in same direction.

Example:
• If the current pointer is at position i, then the next location will be
i=( i+1) MOD SIZE.
• i.e, if Queue size =8
– Current position = 1 then next position = 2
– Current position = 7 then next position = (7+1) MOD 8 =0

45
 Circular Queue rear front

States of the Queue

– Circular Queue is empty
FRONT=-1
REAR=-1
– Circular Queue is full front
rear
FRONT==(REAR+1) MOD SIZE
Q[3] Q[0]
i.E 0=(3+1) MOD 4  Q[0]

Queue FULL
Q[1] Q[2] Q[1]
Q[2]
46
 Circular Queue operations
(1) Insertion(C-ENQUEUE)
– Initially the queue will be initialized as front= -1 and rear =
-1
– Before inserting check whether the queue is full or not.
– If not full, then insert the element to (Rear+1) MOD SIZE
– Make sure that the front always points to the first element
by incrementing the front pointer when the first element is
inserted.

47
 Insertion – C-ENQUEUE(ITEM)

• Initially
Front= -1
Rear = -1

Front= -1
Rear = -1

Q[0] Q[1] Q[2] Q[3]

48
 insertion – C-ENQUEUE(ITEM)

• C-Enqueue (1)
Front= -1
Rear =0

49
 insertion – C-ENQUEUE(ITEM)

• C-Enqueue (1)
Front= -1

Rear =0
1

50
 insertion – C-ENQUEUE(ITEM)

• C-Enqueue (1)
Front= 0

Rear =0
1

51
 insertion – C-ENQUEUE(ITEM)

• C-Enqueue (2)
Front= 0

Rear =1

52
 insertion – C-ENQUEUE(ITEM)

• C-Enqueue (2)
Front= 0

2 Rear =1

53
 insertion – C-ENQUEUE(ITEM)

• C-Enqueue (3)
Front= 0

Rear =2

54
 insertion – C-ENQUEUE(ITEM)

• C-Enqueue (3)
Front= 0

3 2

Rear =2

55
 insertion – C-ENQUEUE(ITEM)

• C-Enqueue (4)
Front= 0

Rear =3 1

3 2

56
 insertion – C-ENQUEUE(ITEM)

• C-Enqueue (4)
Front= 0

Rear =3 4 1

3 2

57
 insertion – C-ENQUEUE(ITEM)

• C-Enqueue (5) Next location = (Rear +1) mod SIZE

Front= 0 =(3+1) mod 4)
=0
But next location ==front
Rear =3 4 1  Queue is full, insertion not
possible

3 2

58
 Circular Queue operations :
insertion – C-ENQUEUE(ITEM)
Steps:
1. Location=(REAR+1) mod SIZE
Algorithm C-ENQUEUE(ITEM)
2. If Location==FRONT
1. Print “Queue is full”
Input: An element ITEM to be inserted
into the circular queue (CQ) 3. Else
1. REAR=Location
Output: Circular queue with the ITEM 2. Q[REAR]=ITEM
at FRONT, if not full 3. If FRONT== -1 then
1. FRONT=0
Data Structure: CQ is implemented by 4. EndIf
using array
4. EndIf
5. Stop 59
 Think !!!!
• Delete an element from FRONT of the queue
Front= 0

Rear =3 4 1

3 2

60
 Think !!!!
• Delete an element from FRONT of the queue
Front= 0
1

Rear =3 4

3 2

61
 Think !!!!
• Deleted an element

Rear =3 4

Front= 1
3 2

62
 Think !!!!
Is it possible to add another element into this
empty space ??

Rear =3 4

Front= 1
3 2

63
 Think !!!!
• Insert (5)

Rear =3 4

Front= 1
3 2

64
 Think !!!!
Location = (Rear+1) mod SIZE
=(3+1) mod 4)
• Insert (5) =0
Location != Front  queue
not full
Rear =3 4

Front= 1
3 2

65
 Think !!!!
• Insert (5)
Rear = Location =0

Front= 1
3 2

66
 Think !!!!
• Insert (5)
Rear = Location =0

4 5

Front= 1
3 2

67
 Think !!!!
• Insert (6)
Rear =0
Now,
(Rear+1) mod SIZE== Front 4 5
Queue is full
Insertion impossible Front= 1
Location = 1
3 2

68
 Circular Queue operations :
Deletion(C- DEQUEUE)

– Before deleting, check whether the circular queue

is empty or not.
– If not empty, then delete the element
– Make sure that the FRONT and REAR always
points to -1 when the last element is deleted.

69
Deletion(C- DEQUEUE)

Rear =0
Front != -1
5
Q[3]
 CQ not empty
4 Q[0]

Q[2] 2 Front= 1
3 Q[1]

70
 Deletion(C- DEQUEUE)

• C-dequeue
Rear =0

Q[3] 5
4 Q[0] 2

Q[2]
Front= 1
3 Q[1]

71
Deletion(C- DEQUEUE)

Rear =0

Q[3] 5
4 Q[0]

Q[2]

3 Q[1]

Front= 2

72
 Deletion(C- DEQUEUE)

• C-dequeue
Rear =0

Q[3] 5
4 Q[0]

Q[2]
3
Q[1]

Front= 2

73
 Deletion(C- DEQUEUE)

Rear =0

Front= 3 Q[3] 5
4 Q[0]

Q[2]

Q[1]

74
 Deletion(C- DEQUEUE)

• C-dequeue
Rear =0

Front= 3 Q[3] 5 4
Q[0]

Q[2]

Q[1]

75
Deletion(C- DEQUEUE)

Front= 0
Rear =0

Q[3] 5 Front == rear

Q[0]
Last element
Q[2]
Set front and rear
Q[1]
to -1, as CQ is
empty

76
 Deletion(C- DEQUEUE)

• C-dequeue Front= 0
Rear =0
5
Q[3]

Q[0]
Front = rear
Q[2]
Last element
Q[1]
Set front and
rear to -1, as CQ is
empty

77
Deletion(C- DEQUEUE)

Front= -1
Rear =-1

Q[3]

Q[0]

Q[2]

Q[1]

78
 Deletion(C- DEQUEUE)

• C-dequeue Front= -1
Rear =-1

Q[3]
CQ empty
 Deletion not
Q[0]

Q[2] possible
Q[1]

79
 Circular Queue operations :
Deletion (C-DEQUEUE)
Steps:
1. If FRONT==-1 then
Algorithm DECQUEUE()
1. Print “Queue is Empty”
Input: A Queue with n 2. Else
elements
1. ITEM=Q[FRONT]
Output: The deleted
2. If FRONT==REAR
element is ITEM if
the Queue is not 1. FRONT=-1
empty. 2. REAR=-1
Data Structure: CQ is 3. Else
implemented using 1. FRONT=(FRONT+1) mod SIZE
array. 4. EndIf
3. EndIf
80
4. Stop
 DEQUE - Double Ended Queue

• It is also a homogeneous list of elements in which insertion

and deletion operations are performed from both the ends.
• That is, we can insert elements from the rear end or from the
front ends.
• Hence it is called double-ended queue. It is commonly
referred as a Deque.
• Both insertion and deletion can be made at either end of the
queue.
• DEQUE can be used as a stack as well as a queue.

81
 Types of DEQUE
deletion insertion
insertion deletion
Q[0] Q[1] Q[2] Q[3] Q[4]

Two types of DEQUE

1. Input restricted deque
2. Output restricted deque

82
 Double Ended Queue (Deque)
• There are:
– Input-restricted Deque: An input restricted Deque

restricts the insertion of the elements at one end

only, the deletion of elements can be done at
both the end of a queue.

deletion 10 20 30 40 50 insertion
deletion
Q[0] Q[1] Q[2] Q[3] Q[4]
F R
Fig: A representation of an input-restricted Deque 83
 Double Ended Queue (Deque)
• There are:
– Output-restricted Deque: on the contrary, an

Output-restricted Deque, restricts the deletion of

elements at one end only, and allows insertion to
be done at both the ends of a Deque.

insertion 10 20 30 40 50 insertion
deletion
Q[0] Q[1] Q[2] Q[3] Q[4]
F R
Fig: A representation of an Output-restricted Deque 84
 Deque Operations
• Insertion at beginning(Front)
– addqatbeg()/ addFront()
• Insertion at end(Rear)
– addqatend()/addRear()
• Deletion from beginning(Front)
– delatbeg()/deleteFront()
• Deletion at end(Rear)
– delatend()/deleteRear()
85
 Double Ended Queue (Deque)
• The programs for input-restricted Deque and
output-restricted Deque would be similar except
for a small difference.
• The program for the input-restricted Deque
would not contain the function addqatbeg().
• Similarly the program for the output-restricted
Deque would not contain the function delatbeg().

86
90
 Priority Queues
A priority queue is a
– collection of elements such that
• each element has been assigned a priority and
• the order in which elements are deleted and processed comes from
the following rules;
1. An element of higher priority is processed before any element of
lower priority.
2. Two elements with same priority are processed according to the order
in which they are added to the queue.
Application : time-sharing system
– programs of higher priority are processed first, and programs
with the same priority from a standard queue.
108
 Priority Queue representations
1. Using Array
2. Multi Queue implementation
3. Using Linked List
4. Heap tree

109
 Priority Queues using Arrays
• By using two dimensional array, we can represent priority
queue.
• Example: PQ[2][20] , first rows is used to stores the queue
elements, Second row is used to store the priority of the
elements.
• Two pointers FRONT and REAR are used to represent two
ends of the queue.
Item 56 78 12 5 98 65
Priority 9 7 6 4 3 2

front rear 110

 Priority Queues
Array representation of priority queue
Operations
• ENQPRIORITY (Enqueue at rear)
• DEQPRIORITY (Dequeue at front)

Item 56 78 12 5 98 65
Priority 9 7 6 4 3 2

front rear 111

 Priority Queues:
Algorithm:
insertion
ENQPRIORITY
Steps:
(item,priority)
1. If(REAR==N-1) then
Input: item and priority are
1. print “ Queue is full”
to be inserted at rear
2. Else
pointer of priority
1. If(REAR==-1 AND FRONT==-1)
queue //Queue is empty
Output: One item is 1. Set FRONT=0
inserted at the rear end 2. EndIf
of the priority queue 3. REAR=REAR+1
Data Structure: Priority 4. PQ[0][REAR]=item
queue is implemented 5. PQ[1][REAR]=priority
by using Array 6. Sort_Descending(PQ)
3. EndIf
4. Stop 112
 Priority Queues: insertion modified
Steps:

Algorithm: 1. If(front==0) AND (rear==size-1) 4. If(front==-1)

ENQPRIORITY 1. Print(“Priority queue is full”) 1. front=0
(item,priority) 2. Exit
5. EndIf
Input: item and priority 2. ElseIf(front>0 AND rear==size-1)
are to be inserted at 1. Temp=front 6. rear=rear+1
rear pointer of priority
queue 2. While(temp<=rear) 7. PQ[0][rear]=item
Output: One item is 1. PQ[0][temp-1]=PQ[0][temp] 8. PQ[1][rear]=priority
inserted at the rear
end of the priority 2. PQ[1][temp-1]=PQ[1][temp]
queue
9. SORT_ASC(PQ[ ])
3. Temp=temp+1
Data Structure: Priority 10. EndIf
queue is implemented 3. EndWhile
by using Array 4. rear=rear-1 11. Stop
5. front=front-1
3. EndIf 113
 Priority Queues: deletion
Algorithm: Steps:
DEQPRIORITY() 1. If(FRONT==-1) and(REAR==-1)
1. Printf(“Priority Queue is empty”)
Input: priority queue 2. Exit
with two pointer 2. Else
front and rear 1. Item=PQ[0][FRONT]
Output: One item is 2. Priority=PQ[1][FRONT] //return Item & Priority
deleted from the 3. If(FRONT==REAR)
front end of the 1. FRONT=-1
priority queue 2. REAR=-1
Data Structure: 4. Else
Priority queue is 1. FRONT=FRONT+1
implemented by 5. EndIf
using Array
3. EndIf
114
4. Stop
Practice in lab –
Display function of Deque, Priority Queue

115