1 of 167

Data Structures and Algorithms

2 of 167

ROAD MAP

What is an algorithm ?
What is a data structure ?
Analysis of An Algorithm
Asymptotic Notations

Big Oh Notation
Omega Notation
Theta Notation
Little o Notation

Rules about Asymptotic Notations

3 of 167

What is An Algorithm ?

Definition :

A finite, clearly specified sequence of instructions to be followed to solve a problem.

Example:

A Recipe is an algorithm which is followed to prepare a particular dish.
Your morning routine you follow as you wakeup in morning.
Driving directions you follow to reach to your destination is also an algorithm.

4 of 167

Properties of an Algorithm

Effectiveness

simple
can be carried out by pen and paper

Definiteness

clear
meaning is unique

Correctness

give the right answer for all possible cases

Finiteness

stop in reasonable time

5 of 167

What is a Data Structure ?

Definition :

An organization and representation of data

representation

data can be stored variously according to their type

signed, unsigned, etc.

example : integer representation in memory

organization

the way of storing data changes according to the organization

ordered, inordered, tree

example : if you have more then one integer ?

6 of 167

Concept of Data Structure ?

Manipulation of user data requires following essential tasks:

7 of 167

Properties of a Data Structure ?

Efficient utilization of medium
Efficient algorithms for

creation
manipulation (insertion/deletion)
data retrieval (Find)

A well-designed data structure allows using little

resources
execution time
memory space

8 of 167

Classification of Data Structure

9 of 167

Classification of Data Structure

10 of 167

Analysis of Algorithm

Analysis investigates

What are the properties of the algorithm?

in terms of time and space

How good is the algorithm ?

according to the properties

How it compares with others?

not always exact

Is it the best that can be done?

difficult !

11 of 167

Mathematical Background

Assume the functions for running times of two algorthms are found !

For input size N

Running time of Algorithm A = T_A(N) = 1000 N

Running time of Algorithm B = T_B(N) = N²

Which one is faster ?

12 of 167

N	T_A	T_B
10	10^-2 sec	10^-4 sec
100	10^-1 sec	10^-2 sec
1000	1 sec	1 sec
10000	10 sec	100 sec
100000	100 sec	10000 sec

If the unit of running time of algorithms A and B is µsec

So which algorithm is faster ?

13 of 167

If N<1000 T_A(N) > T_B(N)

o/w T_B(N) > T_A(N)

Compare their relative growth ?

14 of 167

Big Oh Notation (O)

Provides an “upper bound” for the function f

Definition :

T(N) = O (f(N)) if there are positive constants c and n₀ such that

T(N) ≤ cf(N) when N ≥ n₀

T(N) grows no faster than f(N)
growth rate of T(N) is less than or equal to growth rate of f(N) for large N
f(N) is an upper bound on T(N)

not fully correct !

15 of 167

Big Oh Notation (O)

Analysis of Algorithm A

1000 N ≤ cN

if c= 2000 and n₀ = 1 for all N

is right

16 of 167

Examples

7n+5 = O(n)

for c=8 and n₀=5

7n+5 ≤ 8n n>5 = n₀

7n+5 = O(n²)

for c=7 and n₀=2

7n+5 ≤ 7n² n≥n₀

7n²+3n = O(n) ?

17 of 167

Advantages of O Notation

It is possible to compare of two algorithms with running times
Constants can be ignored.

Units are not important

O(7n²) = O(n²)

Lower order terms are ignored

O(n³+7n²+3) = O(n³)

18 of 167

Omega Notation (Ω)

Definition :

T(N) = Ω (f(N)) if there are positive constants c and n₀such that T(N) ≥ c f(N) when N≥ n₀

T(N) grows no slower than f(N)
growth rate of T(N) is greater than or equal to growth rate of f(N) for large N
f(N) is a lower bound on T(N)

not fully correct !

19 of 167

Theta Notation (θ)

Definition :

T(N) = θ (h(N)) if and only if

T(N) = O(h(N)) and T(N) = Ω(h(N))

T(N) grows as fast as h(N)
growth rate of T(N) and h(N) are equal for large N
h(N) is a tight bound on T(N)

not fully correct !

20 of 167

Theta Notation (θ)

Example :

T(N) = 3N²

T(N) = O(N⁴)

T(N) = O(N³)

T(N) = θ(N²) 🡪 best

21 of 167

Little O Notation (o)

Definition :

T(N) = o(p(N)) if

T(N) = O(p(N)) and T(N)≠θ(p(N))

f(N) grows strictly faster than T(N)
growth rate of T(N) is less than the growth rate of f(N) for large N
f(N) is an upperbound on T(N) (but not tight)

not fully correct !

22 of 167

Little O Notation (o)

Example :

T(N) = 3N²

T(N) = o(N⁴)

T(N) = o(N³)

T(N) = θ(N²)

23 of 167

What is Data Abstraction?

Concept of “Abstraction”

Allows us to consider the high-level characteristics of something without getting bogged down in the details
For example: Process abstraction in procedural programming like C, we can use (pre-defined) functions without concern how they really works inside.

Data Abstraction

We know what a data type can do
How it is done is hidden

24 of 167

What is an Abstract Data Type?

Abstract Data Type (ADT)

Defines a particular data structure in terms of data and operations
Offers an interface of the objects (instances of an ADT)

An ADT consists of

Declaration of data
Declaration of operations
Encapsulation of data and operations : data is hidden from user and can be manipulated only by means of operations

25 of 167

ADT Implementation

Implementaion of an Abstract Data Type (ADT)

Hidden from the user
Same ADT may be implemented in different ways in different languages
Some languages offer built-in ADTs and/or features to be used to implement ADTs (user-define types)

ADTs support modular design which is very important in software development

26 of 167

ARRAYS

27 of 167

An array is a collection of similar data elements.
These data elements have the same data type.
Elements of arrays are stored in consecutive memory locations and are referenced by an index (also known as the subscript).
Declaring an array means specifying three things:

Data type - what kind of values it can store. For example, int, char, float

Name - to identify the array

Size - the maximum number of values that the array can hold

Arrays are declared using the following syntax:

type name[size];

1^st element	2^nd element	3^rd element	4^th element	5^thelement	6^th element	7^th element	8^thelement	9^th element	10^th element

marks[0] marks[1] marks[2] marks[3] marks[4] marks[5] marks[6] marks[7] marks[8] marks[9]

Introduction

28 of 167

Accessing Elements of an Array

To access all the elements of an array, we must use a loop.
That is, we can access all the elements of an array by varying the value of the subscript into the array.
But note that the subscript must be an integral value or an expression that evaluates to an integral value.

int i, marks[10];

for(i=0;i<10;i++)

marks[i] = -1;

29 of 167

Calculating the Address of Array Elements

Address of data element, A[k] = BA(A) + w( k – lower_bound)

where

A is the array

k is the index of the element whose address we have to calculate

BA is the base address of the array A

w is the word size of one element in memory. For example, size of int is 2

99	67	78	56	88	90	34	85

marks[0] marks[1] marks[2] marks[3] marks[4] marks[5] marks[6] marks[7]

1000 1002 1004 1006 1008 1010 1012 1014

marks[4] = 1000 + 2(4 – 0)

= 1000 + 2(4) = 1008

30 of 167

Storing Values in Arrays

Store values in the array

Initialize the elements

Input values for the elements

Assign values to the elements

int i, marks[10];

for(i=0;i<10;i++)

scanf(“%d”, &marks[i]);

int i, arr1[10], arr2[10];

for(i=0;i<10;i++)

arr2[i] = arr1[i];

Inputting Values from Keyboard

Assigning Values to Individual Elements

Initializing Arrays during declaration

int marks [5] = {90, 98, 78, 56, 23};

31 of 167

Calculating the Length of an Array

Length = upper_bound – lower_bound + 1

where

upper_bound is the index of the last element

lower_bound is the index of the first element in the array

99	67	78	56	88	90	34	85

marks[0] marks[1] marks[2] marks[3] marks[4] marks[5] marks[6 marks[7]]

Here, lower_bound = 0, upper_bound = 7

Therefore, length = 7 – 0 + 1 = 8

32 of 167

WAP to Read and Display N Numbers using an Array

#include<stdio.h>

#include<conio.h>

int main()

{

int i=0, n, arr[20];

clrscr();

printf(“\n Enter the number of elements : ”);

scanf(“%d”, &n);

printf(“\n Enter the elements : ”);

33 of 167

WAP to Read and Display N Numbers using an Array

for(i=0;i<n;i++)

{

printf(“\n arr[%d] = ”, i);

scanf(“%d”, &num[i]);

}

printf(“\n The array elements are ”);

for(i=0;i<n;i++)

printf(“arr[%d] = %d\t”, i, arr[i]);

return 0;

}

34 of 167

Inserting an Element in an Array

Algorithm to insert a new element to the end of an array

Step 1: Set upper_bound = upper_bound + 1

Step 2: Set A[upper_bound] = VAL

Step 3; EXIT

Algorithm INSERT( A, N, POS, VAL) to insert an element VAL at position POS

Step 1: [INITIALIZATION] SET I = N

Step 2: Repeat Steps 3 and 4 while I >= POS

Step 3: SET A[I + 1] = A[I]

Step 4: SET I = I – 1

[End of Loop]

Step 5: SET N = N + 1

Step 6: SET A[POS] = VAL

Step 7: EXIT

35 of 167

Deleting an Element from an Array

Algorithm to delete an element from the end of the array

Step 1: Set upper_bound = upper_bound - 1

Step 2: EXIT

Algorithm DELETE( A, N, POS) to delete an element at POS

Step 1: [INITIALIZATION] SET I = POS

Step 2: Repeat Steps 3 and 4 while I <= N-1

Step 3: SET A[I] = A[I + 1]

Step 4: SET I = I + 1

[End of Loop]

Step 5: SET N = N - 1

Step 6: EXIT

36 of 167

Pointers and Arrays

Concept of array is very much bound to the concept of pointer.
Name of an array is actually a pointer that points to the first element of the array.

int *ptr;

ptr = &arr[0];

If pointer variable ptr holds the address of the first element in the array, then the address of the successive elements can be calculated by writing ptr++.

int *ptr = &arr[0];

ptr++;

printf (“The value of the second element in the array is %d”, *ptr);

37 of 167

Arrays of Pointers

An array of pointers can be declared as:

int *ptr[10];

The above statement declares an array of 10 pointers where each of the pointer points to an integer variable. For example, look at the code given below.

int *ptr[10];

int p=1, q=2, r=3, s=4, t=5;

ptr[0]=&p;

ptr[1]=&q;

38 of 167

Arrays of Pointers

ptr[2]=&r;

ptr[3]=&s;

ptr[4]=&t

Can you tell what will be the output of the following statement?

printf(“\n %d”, *ptr[3]);

39 of 167

Arrays of Pointers

The output will be 4 because ptr[3] stores the address of integer variable s and *ptr[3] will therefore print the value of s that is 4.

40 of 167

Two-dimensional Arrays

A two-dimensional array is specified using two subscripts where one subscript denotes row and the other denotes column.

C looks at a two-dimensional array as an array of one-dimensional arrays.

A two-dimensional array is declared as:

data_type array_name[row_size][column_size];

Second Dimension

First Dimension

41 of 167

Two-dimensional Arrays

Therefore, a two dimensional m×n array is an array that contains m×n data elements and each element is accessed using two subscripts, i and j, where i<=m and j<=n

int marks[3][5];

Rows/Columns	Col 0	Col 1	Col2	Col 3	Col 4
Row 0	Marks[0][0]	Marks[0][1]	Marks[0][2]	Marks[0][3]	Marks[0][4]
Row 1	Marks[1][0]	Marks[1][1]	Marks[1][2]	Marks[1][3]	Marks[1][4]
Row 2	Marks[2][0]	Marks[2][1]	Marks[2][2]	Marks[2][3]	Marks[2][4]

Two Dimensional Array

42 of 167

Memory Representation of a 2D Array

There are two ways of storing a 2-D array in memory. The first way is row-major order and the second is column-major order.

In the row-major order the elements of the first row are stored before the elements of the second and third rows. That is, the elements of the array are stored row by row where n elements of the first row will occupy the first nth locations.

(0,0) (0, 1) (0,2) (0,3) (1,0) (1,1) (1,2) (1,3) (2,0) (2,1) (2,2) (2,3)

43 of 167

Memory Representation of a 2D Array

However, when we store the elements in a column major order, the elements of the first column are stored before the elements of the second and third columns. That is, the elements of the array are stored column by column where n elements of the first column will occupy the first nth locations.

(0,0) (1,0) (2,0) (3,0) (0,1) (1,1) (2,1) (3,1) (0,2) (1,2) (2,2) (3,2)

44 of 167

Initializing Two-dimensional Arrays

A two-dimensional array is initialized in the same was as a single dimensional array is initialized. For example,

int marks[2][3]={90, 87, 78, 68, 62, 71};

int marks[2][3]={{90,87,78},{68, 62, 71}};

45 of 167

Calculating the Address of Array Elements

A is a 2D array of M*N

Row Major Order

LOC(A[J,K])=Base(A)+w[M(K-1)+(J-1)]

Column Major Order

LOC(A[J,K])=Base(A)+w[N(J-1)+(K-1)]

46 of 167

Multi-dimensional Arrays

A multi-dimensional array is an array of arrays.
Like we have one index in a single dimensional array, two indices in a two-dimensional array, in the same way we have n indices in a n-dimensional array or multi-dimensional array.
Conversely, an n dimensional array is specified using n indices.
An n dimensional m1 x m2 x m3 x ….. mn array is a collection of m1×m2×m3× ….. ×mn elements.
In a multi-dimensional array, a particular element is specified by using n subscripts as A[I₁][I₂][I₃]…[I_n], where

I₁<=M₁ I₂<=M₂ I₃ <= M₃ ……… I_n <= M_n

47 of 167

Multi-dimensional Arrays

48 of 167

Multi-dimensional Arrays

Suppose the array is of n-dimension having the size/length of each dimension as L1,L2,L3, . .. Ln .Base Address is BA.Index number of the element to find the address is given as i1, i2, i3, . . . .in

Then the formula for column major order will be:

Address of A[i1][ i2]. . . [ in] = BA(A) + W*[((…E_NL_N-1+ E_N-1 )L_N-2 +... E₃ )L₂+ E₂ )L₁ +E₁]

Then the formula for row major order will be:

Address of A[i1][ i2][ i3]. . . .[ in] = BA(A) + W*[(E₁L₂ + E₂ )L₃ +E₃ )L₄ ….. + E_N-1 )L_N + E_N ]

_Where E(effective index)

Ei= Ki-(lower bound)i

Example: An int array A[50][40][30] is stored at the address 1000. Find the address of A[40][20][10].

49 of 167

Sparse Matrix

A matrix is a two-dimensional data object made of m rows and n columns, therefore having total m x n values. If most of the elements of the matrix have 0 value, then it is called a sparse matrix.

Why to use Sparse Matrix instead of simple matrix ?

Storage: There are lesser non-zero elements than zeros and thus lesser memory can be used to store only those elements.

Computing time: Computing time can be saved by logically designing a data structure traversing only non-zero elements..

Example:

0 0 3 0

4 0 0 5

7 0 0 0

0 0 0 0

2 6 0 0

50 of 167

Sparse Matrix

Representing a sparse matrix by a 2D array leads to wastage of lots of memory as zeroes in the matrix are of no use in most of the cases. So, instead of storing zeroes with non-zero elements, we only store non-zero elements. This means storing non-zero elements with triples- (Row, Column, value).

Sparse Matrix Representations can be done in many ways following are two common representations:

Array representation
Linked list representation

51 of 167

Sparse Matrix

Method 1: Using Arrays

2D array is used to represent a sparse matrix in which there are three rows named as

Row: Index of row, where non-zero element is located

Column: Index of column, where non-zero element is located

Value: Value of the non zero element located at index – (row,column)

52 of 167

Sparse Matrix

Method 2: Using Linked Lists

In linked list, each node has four fields. These four fields are defined as:

Row: Index of row, where non-zero element is located

Column: Index of column, where non-zero element is located

Value: Value of the non zero element located at index – (row,column)

Next node: Address of the next node

53 of 167

Applications of Arrays

Arrays are widely used to implement mathematical vectors, matrices and other kinds of rectangular tables.
Many databases include one-dimensional arrays whose elements are records.
Arrays are also used to implement other data structures like heaps, hash tables, deques, queues, stacks and string. We will read about these data structures in the subsequent chapters.
Arrays can be used for dynamic memory allocation.

54 of 167

Operations On Arrays

1.Traversing

2.Insertion

3.Deletion

4.Searching

a)linear search

b)binary search

5.Sorting

a)bubble sort[O(n²)]

b)merge sort[(O(n)]

c)quick sort etc[(nlog(n)]

55 of 167

Traversing Linear Arrays

Traversing is accessing and processing (aka visiting ) each element of the data structure exactly ones

55

•••

Linear Array

56 of 167

Traversing Linear Arrays

Traversing is accessing and processing (aka visiting ) each element of the data structure exactly ones

56

•••

Linear Array

57 of 167

Traversing Linear Arrays

Traversing is accessing and processing (aka visiting ) each element of the data structure exactly ones

57

•••

Linear Array

58 of 167

Traversing Linear Arrays

Traversing is accessing and processing (aka visiting ) each element of the data structure exactly ones

58

•••

Linear Array

Repeat for K = LB to UB

Apply PROCESS to LA[K]

[End of Loop]

2. Exit

59 of 167

Inserting and Deleting

Insertion: Adding an element

Beginning
Middle
End

Deletion: Removing an element

Beginning
Middle
End

59

60 of 167

Insertion

60

1	Brown
2	Davis
3	Johnson
4	Smith
5	Wagner
6
7
8

1	Brown
2	Davis
3	Johnson
4	Smith
5	Wagner
6	Ford
7
8

Insert Ford at the End of Array

61 of 167

Insertion

61

1	Brown
2	Davis
3	Johnson
4	Smith
5	Wagner
6
7
8

1	Brown
2	Davis
3	Johnson
4	Smith
5	Wagner
6	Wagner
7
8

Insert Ford as the 3^rd Element of Array

1	Brown
2	Davis
3	Johnson
4	Smith
5	Smith
6	Wagner
7
8

1	Brown
2	Davis
3
4	Johnson
5	Smith
6	Wagner
7
8

Ford

Insertion is not Possible without loss of data if the array is FULL

62 of 167

Deletion

62

1	Brown
2	Davis
3	Ford
4	Johnson
5	Smith
6	Taylor
7	Wagner
8

1	Brown
2	Davis
3	Ford
4	Johnson
5	Smith
6	Taylor
7
8

Deletion of Wagner at the End of Array

63 of 167

Deletion

63

1	Brown
2	Davis
3	Ford
4	Johnson
5	Smith
6	Taylor
7	Wagner
8

1	Brown
2	Ford
3	Ford
4	Johnson
5	Smith
6	Taylor
7	Wagner
8

Deletion of Davis from the Array

1	Brown
2	Ford
3	Johnson
4	Johnson
5	Smith
6	Taylor
7	Wagner
8

1	Brown
2	Ford
3	Johnson
4	Smith
5	Smith
6	Taylor
7	Wagner
8

64 of 167

Deletion

64

1	Brown
2	Ford
3	Johnson
4	Smith
5	Taylor
6	Wagner
7
8

No data item can be deleted from an empty array

65 of 167

Insertion Algorithm

INSERT (LA, N , K , ITEM) [LA is a linear array with N elements and K is a positive integers such that K ≤ N. This algorithm insert an element ITEM into the K^th position in LA ]

1. [Initialize Counter] Set J := N

2. Repeat Steps 3 and 4 while J ≥ K

3. [Move the J^th element downward ] Set LA[J + 1] := LA[J]

4. [Decrease Counter] Set J := J -1

5 [Insert Element] Set LA[K] := ITEM

6. [Reset N] Set N := N +1;

7. Exit

65

66 of 167

Deletion Algorithm

DELETE (LA, N , K , ITEM) [LA is a linear array with N elements and K is a positive integers such that K ≤ N. This algorithm deletes K^th element from LA ]

1. Set ITEM := LA[K]

2. Repeat for J = K to N -1:

[Move the J + 1^st element upward] Set LA[J] := LA[J + 1]

3. [Reset the number N of elements] Set N := N - 1;

4. Exit

66

67 of 167

Sorting takes an unordered collection and makes it an ordered one.

5

12

35

42

77

101

1 2 3 4 5 6

5

12

35

42

77

101

1 2 3 4 5 6

Sorting

68 of 167

"Bubbling Up" the Largest Element

Traverse a collection of elements

Move from the front to the end
“Bubble” the largest value to the end using pair-wise comparisons and swapping

5

12

35

42

77

101

1 2 3 4 5 6

Contd…

69 of 167

"Bubbling Up" the Largest Element

Traverse a collection of elements

Move from the front to the end
“Bubble” the largest value to the end using pair-wise comparisons and swapping

5

12

35

42

77

101

1 2 3 4 5 6

Swap

42

77

Contd…

70 of 167

"Bubbling Up" the Largest Element

Traverse a collection of elements

Move from the front to the end
“Bubble” the largest value to the end using pair-wise comparisons and swapping

5

12

35

77

42

101

1 2 3 4 5 6

Swap

35

77

Contd…

71 of 167

"Bubbling Up" the Largest Element

Traverse a collection of elements

Move from the front to the end
“Bubble” the largest value to the end using pair-wise comparisons and swapping

5

12

77

35

42

101

1 2 3 4 5 6

Swap

12

77

Contd…

72 of 167

"Bubbling Up" the Largest Element

Traverse a collection of elements

Move from the front to the end
“Bubble” the largest value to the end using pair-wise comparisons and swapping

5

77

12

35

42

101

1 2 3 4 5 6

No need to swap

Contd…

73 of 167

"Bubbling Up" the Largest Element

Traverse a collection of elements

Move from the front to the end
“Bubble” the largest value to the end using pair-wise comparisons and swapping

5

77

12

35

42

101

1 2 3 4 5 6

Swap

5

101

Contd…

74 of 167

LINKED LIST

75 of 167

Introduction

A linked list is a linear collection of data elements called nodes in which linear representation is given by links from one node to the next node.
Linked list is a data structure which in turn can be used to implement other data structures. Thus, it acts as building block to implement data structures like stacks, queues and their variations.
A linked list can be perceived as a train or a sequence of nodes in which each node contains one or more data fields and a pointer to the next node.

76 of 167

List of advantages :

Linked List is Dynamic data Structure .
Linked List can grow and shrink during run time.
Insertion and Deletion Operations are Easier
Efficient Memory Utilization ,i.e no need to pre-allocate memory
Linear Data Structures such as Stack,Queue can be easily implemeted using Linked list.

77 of 167

List of Disadvantages :

Wastage of Memory
No random access
Time consuming
Reverse traversing is difficult.

Types of Linked List

1.Simple/Single linked list

2.Doubly linked list

3.Circular linked list

4.Doubly circular linked list.

78 of 167

Simple Linked List

1

2

3

4

5

6

7

X

START

In the above linked list, every node contains two parts - one integer and the other a pointer to the next node.
The left part of the node which contains data may include a simple data type, an array or a structure.
The right part of the node contains a pointer to the next node (or address of the next node in sequence).
The last node will have no next node connected to it, so it will store a special value called NULL.

79 of 167

Traversing Linked Lists

We can traverse the entire linked list using a single pointer variable called START.
The START node contains the address of the first node; the next part of the first node in turn stores the address of its succeeding node.
Using this technique the individual nodes of the list will form a chain of nodes.
If START = NULL, this means that the linked list is empty and contains no nodes.
In C, we can implement a linked list using the following code:

struct node

{

int data;

struct node *next;

};

80 of 167

START Pointer

1

DATA	NEXT
H	4


E	7


L	8
L	10

O	-1

1 2 3 4 5 6 7 8 9 10

START

START pointing to the first element of the linked list in memory

9

AVAIL

81 of 167

Singly Linked Lists

A singly linked list is the simplest type of linked list in which every node contains some data and a pointer to the next node of the same data type.

1

2

3

4

5

6

7

X

START

ALGORITHM FOR TRAVERSING A LINKED LIST

Step 1: [INITIALIZE] SET PTR = START

Step 2: Repeat Steps 3 and 4 while PTR != NULL

Step 3: Apply Process to PTR->DATA

Step 4: SET PTR = PTR->NEXT

[END OF LOOP]

Step 5: EXIT

82 of 167

Searching a Linked List

ALGORITHM TO SEARCH A LINKED LIST

Step 1: [INITIALIZE] SET PTR = START

Step 2: Repeat Step 3 while PTR != NULL

Step 3: IF VAL = PTR->DATA

SET POS = PTR

Go To Step 5

ELSE

SET PTR = PTR->NEXT

[END OF IF]

[END OF LOOP]

Step 4: SET POS = NULL

Step 5: EXIT

83 of 167

Searching for Val 4 in Linked List

1

7

3

4

2

6

5

X

PTR

1

7

3

4

2

6

5

X

PTR

1

7

3

4

2

6

5

X

PTR

1

7

3

4

2

6

5

X

PTR

84 of 167

Inserting a Node at the Beginning

1

7

3

4

2

6

5

X

START

9

1

7

3

4

2

6

5

X

ALGORITHM TO INSERT A NEW NODE IN THE BEGINNING OF THE LINKED LIST

Step 1: IF AVAIL = NULL, then

Write OVERFLOW

Go to Step 7

[END OF IF]

Step 2: SET New_Node = AVAIL

Step 3: SET AVAIL = AVAIL->NEXT

Step 4: SET New_Node->DATA = VAL

Step 5: SET New_Node->Next = START

Step 6: SET START = New_Node

Step 7: EXIT

85 of 167

Inserting a Node at the End

1

7

3

4

2

6

5

X

START, PTR

1

7

3

4

2

6

5

9

X

START

ALGORITHM TO INSERT A NEW NODE AT THE END OF THE LINKED LIST

Step 1: IF AVAIL = NULL, then

Write OVERFLOW

Go to Step 10

[END OF IF]

Step 2: SET New_Node = AVAIL

Step 3: SET AVAIL = AVAIL->NEXT

Step 4: SET New_Node->DATA = VAL

Step 5: SET New_Node->Next = NULL

Step 6: SET PTR = START

Step 7: Repeat Step 8 while PTR->NEXT != NULL

Step 8: SET PTR = PTR ->NEXT

[END OF LOOP]

Step 9: SET PTR->NEXT = New_Node

Step 10: EXIT

86 of 167

Inserting a Node after Node that has Value NUM

ALGORITHM TO INSERT A NEW NODE AFTER A NODE THAT HAS VALUE NUM

Step 1: IF AVAIL = NULL, then

Write OVERFLOW

Go to Step 12

[END OF IF]

Step 2: SET New_Node = AVAIL

Step 3: SET AVAIL = AVAIL->NEXT

Step 4: SET New_Node->DATA = VAL

Step 5: SET PTR = START

Step 6: SET PREPTR = PTR

Step 7: Repeat Steps 8 and 9 while PREPTR->DATA != NUM

Step 8: SET PREPTR = PTR

Step 9: SET PTR = PTR->NEXT

[END OF LOOP]

Step 10: PREPTR->NEXT = New_Node

Step 11: SET New_Node->NEXT = PTR

Step 12: EXIT

87 of 167

Deleting the First Node

Algorithm to delete the first node from the linked list

Step 1: IF START = NULL, then

Write UNDERFLOW

Go to Step 5

[END OF IF]

Step 2: SET PTR = START

Step 3: SET START = START->NEXT

Step 4: FREE PTR

Step 5: EXIT

1

7

3

4

2

6

5

X

7

3

4

2

6

5

X

START

88 of 167

Deleting the Last Node

ALGORITHM TO DELETE THE LAST NODE OF THE LINKED LIST

Step 1: IF START = NULL, then

Write UNDERFLOW

Go to Step 8

[END OF IF]

Step 2: SET PTR = START

Step 3: Repeat Steps 4 and 5 while PTR->NEXT != NULL

Step 4: SET PREPTR = PTR

Step 5: SET PTR = PTR->NEXT

[END OF LOOP]

Step 6: SET PREPTR->NEXT = NULL

Step 7: FREE PTR

Step 8: EXIT

1

7

3

4

2

6

5

X

START, PREPTR, PTR

1

7

3

4

2

6

X

5

X

PREPTR PTR

START

89 of 167

Deleting the Node After a Given Node

ALGORITHM TO DELETE THE NODE AFTER A GIVEN NODE FROM THE LINKED LIST

Step 1: IF START = NULL, then

Write UNDERFLOW

Go to Step 10

[END OF IF]

Step 2: SET PTR = START

Step 3: SET PREPTR = PTR

Step 4: Repeat Step 5 and 6 while PRETR->DATA != NUM

Step 5: SET PREPTR = PTR

Step 6: SET PTR = PTR->NEXT

[END OF LOOP]

Step7: SET TEMP = PTR->NEXT

Step 8: SET PREPTR->NEXT = TEMP->NEXT

Step 9: FREE TEMP

Step 10: EXIT

90 of 167

Singly Linked List

1

7

3

4

2

6

5

X

START, PREPTR, PTR

1

7

3

4

2

6

5

X

PREPTR PTR

START

1

7

3

4

2

6

5

X

START

1

7

3

4

6

5

X

91 of 167

Circular Linked List

In a circular linked list, the last node contains a pointer to the first node of the list. We can have a circular singly listed list as well as circular doubly linked list. While traversing a circular linked list, we can begin at any node and traverse the list in any direction forward or backward until we reach the same node where we had started. Thus, a circular linked list has no beginning and no ending.

1

2

3

4

5

6

7

START

92 of 167

Circular Linked List

Algorithm to insert a new node in the beginning of circular the linked list

Step 1: IF AVAIL = NULL, then

Write OVERFLOW

Go to Step 7

[END OF IF]

Step 2: SET New_Node = AVAIL

Step 3: SET AVAIL = AVAIL->NEXT

Step 4: SET New_Node->DATA = VAL

Step 5: SET PTR = START

Step 6: Repeat Step 7 while PTR->NEXT != START

Step 7: PTR = PTR->NEXT

Step 8: SET New_Node->Next = START

Step 8: SET PTR->NEXT = New_Node

Step 6: SET START = New_Node

Step 7: EXIT

93 of 167

Circular Linked List

1

7

3

4

2

6

5

START, PTR

1

7

3

4

2

6

5

START

PTR

9

1

7

3

4

2

6

5

START

94 of 167

Circular Linked List

Algorithm to insert a new node at the end of the circular linked list

Step 1: IF AVAIL = NULL, then

Write OVERFLOW

Go to Step 7

[END OF IF]

Step 2: SET New_Node = AVAIL

Step 3: SET AVAIL = AVAIL->NEXT

Step 4: SET New_Node->DATA = VAL

Step 5: SET New_Node->Next = START

Step 6: SET PTR = START

Step 7: Repeat Step 8 while PTR->NEXT != START

Step 8: SET PTR = PTR ->NEXT

[END OF LOOP]

Step 9: SET PTR ->NEXT = New_Node

Step 10: EXIT

95 of 167

Circular Linked List

1

7

3

4

2

6

5

START, PTR

1

7

3

4

2

6

5

9

START

PTR

96 of 167

Circular Linked List

Algorithm to insert a new node after a node that has value NUM

Step 1: IF AVAIL = NULL, then

Write OVERFLOW

Go to Step 12

[END OF IF]

Step 2: SET New_Node = AVAIL

Step 3: SET AVAIL = AVAIL->NEXT

Step 4: SET New_Node->DATA = VAL

Step 5: SET PTR = START

Step 6: SET PREPTR = PTR

Step 7: Repeat Step 8 and 9 while PTR->DATA != NUM

Step 8: SET PREPTR = PTR

Step 9: SET PTR = PTR->NEXT

[END OF LOOP]

Step 10: PREPTR->NEXT = New_Node

Step 11: SET New_Node->NEXT = PTR

Step 12: EXIT

97 of 167

Circular Linked List

Algorithm to delete the first node from the circular linked list

Step 1: IF START = NULL, then

Write UNDERFLOW

Go to Step 8

[END OF IF]

Step 2: SET PTR = START

Step 3: Repeat Step 4 while PTR->NEXT != START

Step 4: SET PTR = PTR->NEXT

[END OF IF]

Step 5: SET PTR->NEXT = START->NEXT

Step 6: FREE START

Step 7: SET START = PTR->NEXT

Step 8: EXIT

98 of 167

Circular Linked List

1

7

3

4

2

6

5

START, PTR

1

7

3

4

2

6

5

START

PTR

7

3

4

2

6

5

START

99 of 167

Circular Linked List

Algorithm to delete the last node of the circular linked list

Step 1: IF START = NULL, then

Write UNDERFLOW

Go to Step 8

[END OF IF]

Step 2: SET PTR = START

Step 3: Repeat Step 4 while PTR->NEXT != START

Step 4: SET PREPTR = PTR

Step 5: SET PTR = PTR->NEXT

[END OF LOOP]

Step 6: SET PREPTR->NEXT = START

Step 7: FREE PTR

Step 8: EXIT

100 of 167

Circular Linked List

1

7

3

4

2

6

5

START, PREPTR, PTR

1

7

3

4

2

6

5

START

PTR

PREPTR

1

7

3

4

2

6

START

101 of 167

Circular Linked List

Algorithm to delete the node after a given node from the circular linked list

Step 1: IF START = NULL, then

Write UNDERFLOW

Go to Step 9

[END OF IF]

Step 2: SET PTR = START

Step 3: SET PREPTR = PTR

Step 4: Repeat Step 5 and 6 while PREPTR->DATA != NUM

Step 5: SET PREPTR = PTR

Step 6: SET PTR = PTR->NEXT

[END OF LOOP]

Step 7: SET PREPTR->NEXT = PTR->NEXT

Step 8: FREE PTR

Step 9: EXIT

102 of 167

Circular Linked List

1

7

3

4

2

6

5

START, PREPTR, PTR

1

7

3

4

2

6

5

START

PREPTR PTR

1

7

3

4

6

5

START

103 of 167

Doubly Linked List

A doubly linked list or a two way linked list is a more complex type of linked list which contains a pointer to the next as well as previous node in the sequence. Therefore, it consists of three parts and not just two. The three parts are data, a pointer to the next node and a pointer to the previous node

1

X

1

2

3

4

X

START

104 of 167

Doubly Linked List

In C language, the structure of a doubly linked list is given as,

struct node

{ struct node *prev;

int data;

struct node *next;

};

The prev field of the first node and the next field of the last node will contain NULL. The prev field is used to store the address of the preceding node. This would enable to traverse the list in the backward direction as well.

105 of 167

Doubly Linked List

Algorithm to insert a new node in the beginning of the doubly linked list

Step 1: IF AVAIL = NULL, then

Write OVERFLOW

Go to Step 8

[END OF IF]

Step 2: SET New_Node = AVAIL

Step 3: SET AVAIL = AVAIL->NEXT

Step 4: SET New_Node->DATA = VAL

Step 5: SET New_Node->PREV = NULL

Step 6: SET New_Node->Next = START

Step 7: SET START = New_Node

Step 8: EXIT

1

7

3

4

2

X

9

1

7

3

4

X

2

X

START

106 of 167

Doubly Linked List

Algorithm to insert a new node at the end of the doubly linked list

Step 1: IF AVAIL = NULL, then

Write OVERFLOW

Go to Step 11

[END OF IF]

Step 2: SET New_Node = AVAIL

Step 3: SET AVAIL = AVAIL->NEXT

Step 4: SET New_Node->DATA = VAL

Step 5: SET New_Node->Next = NULL

Step 6: SET PTR = START

Step 7: Repeat Step 8 while PTR->NEXT != NULL

Step 8: SET PTR = PTR->NEXT

[END OF LOOP]

Step 9: SET PTR->NEXT = New_Node

Step 10: New_Node->PREV = PTR

Step 11: EXIT

1

7

3

4

2

X

START, PTR

1

7

3

4

2

X

9

X

PTR

107 of 167

Doubly Linked List

Algorithm to insert a new node after a node that has value NUM

Step 1: IF AVAIL = NULL, then

Write OVERFLOW

Go to Step 11

[END OF IF]

Step 2: SET New_Node = AVAIL

Step 3: SET AVAIL = AVAIL->NEXT

Step 4: SET New_Node->DATA = VAL

Step 5: SET PTR = START

Step 6: Repeat Step 8 while PTR->DATA != NUM

Step 7: SET PTR = PTR->NEXT

[END OF LOOP]

Step 8: New_Node->NEXT = PTR->NEXT

Step 9: SET New_Node->PREV = PTR

Step 10: SET PTR->NEXT = New_Node

Step 11: EXIT

108 of 167

Doubly Linked List

1

7

3

4

2

X

START, PTR

1

7

3

4

2

X

9

1

7

3

9

4

X

2

X

START

PTR

109 of 167

Doubly Linked List

Algorithm to delete the first node from the doubly linked list

Step 1: IF START = NULL, then

Write UNDERFLOW

Go to Step 6

[END OF IF]

Step 2: SET PTR = START

Step 3: SET START = START->NEXT

Step 4: SET START->PREV = NULL

Step 5: FREE PTR

Step 6: EXIT

1

7

3

4

2

X

START, PTR

7

3

4

2

X

110 of 167

Doubly Linked List

Algorithm to delete the last node of the doubly linked list

Step 1: IF START = NULL, then

Write UNDERFLOW

Go to Step 7

[END OF IF]

Step 2: SET PTR = START

Step 3: Repeat Step 4 and 5 while PTR->NEXT != NULL

Step 4: SET PTR = PTR->NEXT

[END OF LOOP]

Step 5: SET PTR->PREV->NEXT = NULL

Step 6: FREE PTR

Step 7: EXIT

1

3

5

7

8

X

91

X

START, PTR

1

3

5

7

8

X

91

X

START

PTR

1

3

5

7

8

X

START

111 of 167

Doubly Linked List

Algorithm to delete the node after a given node from the doubly linked list

Step 1: IF START = NULL, then

Write UNDERFLOW

Go to Step 9

[END OF IF]

Step 2: SET PTR = START

Step 3: Repeat Step 4 while PTR->DATA != NUM

Step 4: SET PTR = PTR->NEXT

[END OF LOOP]

Step 5: SET TEMP = PTR->NEXT

Step 6: SET PTR->NEXT = TEMP->NEXT

Step 7: SET TEMP->NEXT->PREV = PTR

Step 8: FREE TEMP

Step 9: EXIT

112 of 167

Doubly Linked List

1

3

4

7

8

X

91

X

1

3

4

7

8

X

91

X

1

3

4

8

9

X

START, PTR

START

PTR

START

113 of 167

Circular Doubly Linked List

A circular doubly linked list or a circular two way linked list is a more complex type of linked list which contains a pointer to the next as well as previous node in the sequence.

The difference between a doubly linked and a circular doubly linked list is same as that exists between a singly linked list and a circular linked list. The circular doubly linked list does not contain NULL in the previous field of the first node and the next field of the last node. Rather, the next field of the last node stores the address of the first node of the list, i.e; START. Similarly, the previous field of the first field stores the address of the last node.

114 of 167

Circular Doubly Linked List

Since a circular doubly linked list contains three parts in its structure, it calls for more space per node and for more expensive basic operations. However, it provides the ease to manipulate the elements of the list as it maintains pointers to nodes in both the directions . The main advantage of using a circular doubly linked list is that it makes searches twice as efficient.

1

2

3

4

START

115 of 167

Circular Doubly Linked List

Algorithm to insert a new node in the beginning of the circular doubly linked list

Step 1: IF AVAIL = NULL, then

Write OVERFLOW

Go to Step 12

[END OF IF]

Step 2: SET New_Node = AVAIL

Step 3: SET AVAIL = AVAIL->NEXT

Step 4: SET New_Node->DATA = VAL

Step 6: SET START->PREV->NEXT = new_node;

Step 7: SET New_Node->PREV = START->PREV;

Step 8: SET START->PREV= new_Node;

Step 9: SET new_node->next = START;

Step 10: SET START = New_Node

Step 11: EXIT

116 of 167

Circular Doubly Linked List

1

7

3

4

2

START

9

1

7

3

4

2

START

117 of 167

Circular Doubly Linked List

Algorithm to insert a new node at the end of the circular doubly linked list

Step 1: IF AVAIL = NULL, then

Write OVERFLOW

Go to Step 11

[END OF IF]

Step 2: SET New_Node = AVAIL

Step 3: SET AVAIL = AVAIL->NEXT

Step 4: SET New_Node->DATA = VAL

Step 5: SET New_Node->Next = START

Step 6: SET New_Node->PREV = START->PREV

Step 7: EXIT

1

7

3

4

2

1

7

3

4

2

9

START

118 of 167

Circular Doubly Linked List

Algorithm to insert a new node after a node that has value NUM

Step 1: IF AVAIL = NULL, then

Write OVERFLOW

Go to Step 11

[END OF IF]

Step 2: SET New_Node = AVAIL

Step 3: SET AVAIL = AVAIL->NEXT

Step 4: SET New_Node->DATA = VAL

Step 5: SET PTR = START

Step 6: Repeat Step 8 while PTR->DATA != NUM

Step 7: SET PTR = PTR->NEXT

[END OF LOOP]

Step 8: New_Node->NEXT = PTR->NEXT

Step 9: SET PTR->NEXT->PREV = New_Node

Step 9: SET New_Node->PREV = PTR

Step 10: SET PTR->NEXT = New_Node

Step 11: EXIT

119 of 167

Circular Doubly Linked List

1

7

3

4

2

START, PTR

1

7

3

4

2

9

START

PTR

1

7

3

9

4

2

START

120 of 167

Circular Doubly Linked List

Algorithm to delete the first node from the circular doubly linked list

Step 1: IF START = NULL, then

Write UNDERFLOW

Go to Step 8

[END OF IF]

Step 2: SET PTR = START

Step 3: SET PTR->PREV=>NEXT= PTR->NEXT

Step 4: SET PTR->NEXT->PREV = PTR->PREV

Step 5: SET START = START->NEXT

Step 6: FREE PTR

Step 7: EXIT

1

3

5

7

8

91

START, PTR

3

5

7

8

91

START

121 of 167

Circular Doubly Linked List

Algorithm to delete the last node of the circular doubly linked list

Step 1: IF START = NULL, then

Write UNDERFLOW

Go to Step 8

[END OF IF]

Step 2: SET PTR = START->PREV

Step 5: SET PTR->PREV->NEXT = START

Step 6: SET START->PREV = PTR->PREV

Step 7: FREE PTR

Step 8: EXIT

1

3

5

7

8

91

START

PTR

1

3

5

7

8

X

START

122 of 167

Circular Doubly Linked List

Algorithm to delete the node after a given node from the circular doubly linked list

Step 1: IF START = NULL, then

Write UNDERFLOW

Go to Step 9

[END OF IF]

Step 2: SET PTR = START

Step 3: Repeat Step 4 while PTR->DATA != NUM

Step 4: SET PTR = PTR->NEXT

[END OF LOOP]

Step 5: SET TEMP = PTR->NEXT

Step 6: SET PTR->NEXT = TEMP->NEXT

Step 7: SET TEMP->NEXT->PREV = PTR

Step 8: FREE TEMP

Step 9: EXIT

123 of 167

Circular Doubly Linked List

1

3

5

7

8

91

START

1

3

5

7

8

91

START

PTR

1

3

4

8

9

START

124 of 167

STACKS

125 of 167

Introduction

Stack is an important data structure which stores its elements in an ordered manner.
Take an analogy of a pile of plates where one plate is placed on top of the other. A plate can be removed only from the topmost position. Hence, you can add and remove the plate only at/from one position, that is, the topmost position.

The topmost plate will be removed first

Another plate will be added on top of this plate

126 of 167

Stacks

A stack is a linear data structure which uses the same principle, i.e., the elements in a stack are added and removed only from one end, which is called the top.
Hence, a stack is called a LIFO (Last-In, First-Out) data structure as the element that is inserted last is the first one to be taken out.
Stacks can be implemented either using an array or a linked list.

127 of 167

Array Representation of Stacks

In computer’s memory stacks can be represented as a linear array.
Every stack has a variable TOP associated with it.
TOP is used to store the address of the topmost element of the stack. It is this position from where the element will be added or deleted.
There is another variable MAX which will be used to store the maximum number of elements that the stack can hold.
If TOP = NULL, then it indicates that the stack is empty and if TOP = MAX -1, then the stack is full.

128 of 167

Push Operation

The push operation is used to insert an element in to the stack.
The new element is added at the topmost position of the stack.
However, before inserting the value, we must first check if TOP=MAX-1, because if this is the case then it means the stack is full and no more insertions can further be done.
If an attempt is made to insert a value in a stack that is already full, an OVERFLOW message is printed.

A	B	C	D	E

0 1 2 3 TOP = 4 5 6 7 8 9

A	B	C	D	E	F

0 1 2 3 4 TOP =5 6 7 8 9

129 of 167

Pop Operation

The pop operation is used to delete the topmost element from the stack.
However, before deleting the value, we must first check if TOP=NULL, because if this is the case then it means the stack is empty so no more deletions can further be done.
If an attempt is made to delete a value from a stack that is already empty, an UNDERFLOW message is printed.

A	B	C	D	E

0 1 2 3 TOP = 4 5 6 7 8 9

A	B	C	D

0 1 2 TOP = 3 4 5 6 7 8 9

130 of 167

Peek Operation

Peek is an operation that returns the value of the topmost element of the stack without deleting it from the stack.
However, the peep operation first checks if the stack is empty or contains some elements.
If TOP = NULL, then an appropriate message is printed else the value is returned.

A	B	C	D	E

0 1 2 3 TOP = 4 5 6 7 8 9

Here Peep operation will return E, as it is the value of the topmost element of the stack.

131 of 167

Algorithms for Push and Pop Operations

Algorithm to PUSH an element in a stack

Step 1: IF TOP = MAX-1, then

PRINT “OVERFLOW”

Goto Step 4

[END OF IF]

Step 2: SET TOP = TOP + 1

Step 3: SET STACK[TOP] = VALUE

Step 4: END

Algorithm to POP an element from a stack

Step 1: IF TOP = NULL, then

PRINT “UNDERFLOW”

Goto Step 4

[END OF IF]

Step 2: SET VAL = STACK[TOP]

Step 3: SET TOP = TOP - 1

Step 4: END

132 of 167

Algorithm for Peep Operation

Step 1: IF TOP =NULL, then

PRINT “STACK IS EMPTY”

Go TO Step 3

[END OF IF]

Step 2: RETURN STACK[TOP]

Step 3: END

133 of 167

Linear Representation of Stacks

In a linked stack, every node has two parts – one that stores data and another that stores the address of the next node.
The START pointer of the linked list is used as TOP.
If TOP is NULL then it indicates that the stack is empty.

1

7

3

4

2

6

5

X

TOP

134 of 167

Push Operation on a Linked Stack

Algorithm to PUSH an element in a linked stack

Step 1: Allocate memory for the new node and name it as New_Node

Step 2: SET New_Node->DATA = VAL

Step 3: IF TOP = NULL, then

SET New_Node->NEXT = NULL

SET TOP = New_Node

ELSE

SET New_node->NEXT = TOP

SET TOP = New_Node

[END OF IF]

Step 4: END

1

7

3

4

2

6

5

X

TOP

9

1

7

3

4

2

6

5

X

TOP

135 of 167

Pop Operation on a Linked Stack

Algorithm to POP an element from a stack

Step 1: IF TOP = NULL, then

PRINT “UNDERFLOW”

Goto Step 5

[END OF IF]

Step 2: SET PTR = TOP

Step 3: SET TOP = TOP ->NEXT

Step 4: FREE PTR

Step 5: END

9

1

7

3

4

2

6

5

X

TOP

1

7

3

4

2

6

5

X

TOP

136 of 167

Applications of Stacks

Reversing a list
Parentheses checker
Conversion of an infix expression into a postfix expression
Evaluation of a postfix expression
Conversion of an infix expression into a prefix expression
Evaluation of a postfix expression
Recursion
Tower of Hanoi

137 of 167

Infix Notation

Infix, Postfix and Prefix notations are three different but equivalent notations of writing algebraic expressions.
While writing an arithmetic expression using infix notation, the operator is placed between the operands. For example, A+B; here, plus operator is placed between the two operands A and B.
Although it is easy to write expressions using infix notation, computers find it difficult to parse as they need a lot of information to evaluate the expression.
Information is needed about operator precedence, associativity rules, and brackets which overrides these rules.
So, computers work more efficiently with expressions written using prefix and postfix notations.

138 of 167

Postfix Notation

Postfix notation was given by Jan Łukasiewicz who was a Polish logician, mathematician, and philosopher. His aim was to develop a parenthesis-free prefix notation (also known as Polish notation) and a postfix notation which is better known as Reverse Polish Notation or RPN.
In postfix notation, the operator is placed after the operands. For example, if an expression is written as A+B in infix notation, the same expression can be written as AB+ in postfix notation.
The order of evaluation of a postfix expression is always from left to right.

139 of 167

Postfix Notation

The expression (A + B) * C is written as:

AB+C* in the postfix notation.

A postfix operation does not even follow the rules of operator precedence. The operator which occurs first in the expression is operated first on the operands.
For example, given a postfix notation AB+C*. While evaluation, addition will be performed prior to multiplication.

140 of 167

Prefix Notation

In a prefix notation, the operator is placed before the operands.
For example, if A+B is an expression in infix notation, then the corresponding expression in prefix notation is given by +AB.
While evaluating a prefix expression, the operators are applied to the operands that are present immediately on the right of the operator.
Prefix expressions also do not follow the rules of operator precedence, associativity, and even brackets cannot alter the order of evaluation.
The expression (A + B) * C is written as:

*+ABC in the prefix notation

141 of 167

Evaluation of an Infix Expression

Algorithm to convert an Infix notation into postfix notation

Step 1: Add ‘)” to the end of the infix expression

Step 2: Push “(“ on to the stack

Step 3: Repeat until each character in the infix notation is scanned

IF a “(“ is encountered, push it on the stack

IF an operand (whether a digit or an alphabet) is encountered,

add it to the postfix expression.

IF a “)” is encountered, then;

. Repeatedly pop from stack and add it to the postfix expression until a “(” is encountered.

b. Discard the “(“. That is, remove the “(“ from stack and do not

add it to the postfix expression

IF an operator X is encountered, then;

Repeatedly pop from stack and add each operator (popped from the stack) to the postfix expression which has the same precedence or a higher precedence than X

b. Push the operator X to the stack

Step 4: Repeatedly pop from the stack and add it to the postfix expression

until the stack is empty

Step 5: EXIT

STEP 1: Convert the infix expression into its equivalent postfix expression

142 of 167

Evaluation of an Infix Expression

STEP 2: Evaluate the postfix expression

Algorithm to evaluate a postfix expression

Step 1: Add a “)” at the end of the postfix expression

Step 2: Scan every character of the postfix expression and repeat

steps 3 and 4 until “)”is encountered

Step 3: IF an operand is encountered, push it on the stack

IF an operator X is encountered, then

a. pop the top two elements from the stack as A and B

b. Evaluate B X A, where A was the topmost element and B was

the element below A.

c. Push the result of evaluation on the stack

[END OF IF]

Step 4: SET RESULT equal to the topmost element of the stack

Step 5: EXIT

143 of 167

Evaluation of an Infix Expression

Let us now take an example that makes use of this algorithm.
Consider the infix expression given as “9 - (( 3 * 4) + 8) / 4”.
The infix expression "9 - (( 3 * 4) + 8) / 4" can be written as “9 3 4 * 8 + 4 / -“ using postfix notation.
Look at table which shows the procedure.

Character scanned	Stack
9	9
3	9, 3
4	9, 3, 4
*	9, 12
8	9, 12, 8
+	9, 20
4	9, 20, 4
/	9, 5
-	4

144 of 167

Tower of Hanoi

Tower of Hanoi is one of the main applications of a recursion. It says, "if you can solve n-1 cases, then you can easily solve the nth case"

A

B

C

A

B

C

If there is only one ring, then simply move the ring from source to the destination

B

A

B

C

A

C

A

B

C

If there are two rings, then first move ring 1 to the spare pole and then move ring 2 from source to the destination. Finally move ring 1 from the source to the destination

A

B

C

145 of 167

Tower of Hanoi

Consider the working with three rings.

A

B

C

A

B

C

A

B

C

A

B

C

A

B

C

A

B

C

A

B

C

A

B

C

146 of 167

QUEUES

147 of 167

Introduction

Queue is an important data structure which stores its elements in an ordered manner.
We can explain the concept of queues using the following analogy:

People moving on an escalator. The people who got on the escalator first will be the first one to step out of it.

A queue is a FIFO (First-In, First-Out) data structure in which the element that is inserted first is the first one to be taken out.
The elements in a queue are added at one end called the rear and removed from the other one end called the front.

148 of 167

Array Representation of Queues

Queues can be easily represented using linear arrays.
Every queue has front and rear variables that point to the position from where deletions and insertions can be done, respectively.
Consider the queue shown in figure

0 1 2 3 4 5 6 7 8 9

12	9	7	18	14	36

Here, front = 0 and rear = 5.
If we want to add one more value in the list say with value 45, then rear would be incremented by 1 and the value would be stored at the position pointed by rear.

12	9	7	18	14	36	45

0 1 2 3 4 5 6 7 8 9

149 of 167

Array Representation of Queues

Now, front = 0 and rear = 6. Every time a new element has to be added, we will repeat the same procedure.
Now, if we want to delete an element from the queue, then the value of front will be incremented. Deletions are done from only this end of the queue.

	9	7	18	14	36	45

0 1 2 3 4 5 6 7 8 9

Now, front = 1 and rear = 6.

150 of 167

Algorithm for Insertion Operation

Algorithm to insert an element in a queue

Step 1: IF REAR=MAX-1, then;

Write OVERFLOW

Goto Step 4

[END OF IF]

Step 2: IF FRONT == -1 and REAR = -1, then

SET FRONT = REAR = 0

ELSE

SET REAR = REAR + 1

[END OF IF]

Step 3: SET QUEUE[REAR] = NUM

Step 4: Exit

151 of 167

Array Representation of Queues

Before inserting an element in the queue we must check for overflow conditions.
An overflow occurs when we try to insert an element into a queue that is already full, i.e. when rear = MAX – 1, where MAX specifies the maximum number of elements that the queue can hold.
Similarly, before deleting an element from the queue, we must check for underflow condition.
An underflow occurs when we try to delete an element from a queue that is already empty. If front = -1 and rear = -1, this means there is no element in the queue.

152 of 167

Algorithm for Deletion Operation

Algorithm to delete an element from a queue

Step 1: IF FRONT = -1 OR FRONT > REAR, then

Write UNDERFLOW

Goto Step 2

ELSE

SET VAL = QUEUE[FRONT]

SET FRONT = FRONT + 1

[END OF IF]

Step 2: Exit

153 of 167

Linked Representation of Queues

In a linked queue, every element has two parts: one that stores data and the other that stores the address of the next element.
The START pointer of the linked list is used as FRONT.
We will also use another pointer called REAR which will store the address of the last element in the queue.
All insertions will be done at the rear end and all the deletions will be done at the front end.
If FRONT = REAR = NULL, then it indicates that the queue is empty.

1

7

3

4

2

6

5

X

FRONT

REAR

154 of 167

Inserting an Element in a Linked Queue

Algorithm to insert an element in a linked queue

Step 1: Allocate memory for the new node and name it as PTR

Step 2: SET PTR->DATA = VAL

Step 3: IF FRONT = NULL, then

SET FRONT = REAR = PTR

SET FRONT->NEXT = REAR->NEXT = NULL

ELSE

SET REAR->NEXT = PTR

SET PTR->NEXT = NULL

[END OF IF]

Step 4: END

155 of 167

Deleting an Element from a Linked Queue

Algorithm to delete an element from a linked queue

Step 1: IF FRONT = NULL, then

Write “Underflow”

Go to Step 5

[END OF IF]

Step 2: SET PTR = FRONT

Step 3: FRONT = FRONT->NEXT

Step 4: FREE PTR

Step 5: END

156 of 167

Circular Queues

		7	18	14	36	45	21	99	72

0 1 2 3 4 5 6 7 8 9

We will explain the concept of circular queues using an example.
In this queue, front = 2 and rear = 9.
Now, if you want to insert a new element, it cannot be done because the space is available only at the left of the queue.
If rear = MAX – 1, then OVERFLOW condition exists.
This is the major drawback of a linear queue. Even if space is available, no insertions can be done once rear is equal to MAX – 1.
This leads to wastage of space. In order to overcome this problem, we use circular queues.
In a circular queue, the first index comes right after the last index.
A circular queue is full, only when front=0 and rear = Max – 1.

157 of 167

Inserting an Element in a Circular Queue

For insertion we check for three conditions which are as follows:

If front=0 and rear= MAX – 1, then the circular queue is full.

90	49	7	18	14	36	45	21	99	72

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

If rear != MAX – 1, then the rear will be incremented and value will be inserted

90	49	7	18	14	36	45	21	99

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

If front!=0 and rear=MAX -1, then it means that the queue is not full. So, set rear = 0 and insert the new element.

	49	7	18	14	36	45	21	99	72

front=1 2 3 4 5 6 7 8 rear= 9

158 of 167

Algorithm to Insert an Element in a Circular Queue

Step 1: IF FRONT = 0 and Rear = MAX – 1, then

Write “OVERFLOW”

Goto Step 4

[END OF IF]

Step 2: IF FRONT = -1 and REAR = -1, then;

SET FRONT = REAR = 0

ELSE IF REAR = MAX – 1 and FRONT != 0

SET REAR = 0

ELSE

SET REAR = REAR + 1

[END OF IF]

Step 3: SET QUEUE[REAR] = VAL

Step 4: Exit

159 of 167

Deleting an Element from a Circular Queue

To delete an element again we will check for three conditions:
If front = -1, then it means there are no elements in the queue. So an underflow condition will be reported.

0 1 2 3 4 5 6 7 8 9

If the queue is not empty and after returning the value on front, if front = rear, then it means now the queue has become empty and so front and rear are set to -1.

Delete this element and set rear = front = -1

									81

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

If the queue is not empty and after returning the value on front, if front = MAX -1, then front is set to 0.

72	63	9	18	27	39				81

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

160 of 167

_{Algorithm to Delete an Element from a Circular Queue}

Step 1: IF FRONT = -1, then

Write “Underflow”

Goto Step 4

[END OF IF]

Step 2: SET VAL = QUEUE[FRONT]

Step 3: IF FRONT = REAR

SET FRONT = REAR = -1

ELSE

IF FRONT = MAX -1

SET FRONT = 0

ELSE

SET FRONT = FRONT + 1

[END OF IF]

Step 4: EXIT

161 of 167

Deques

A deque is a list in which elements can be inserted or deleted at either end.
It is also known as a head-tail linked list because elements can be added to or removed from the front (head) or back (tail).
A deque can be implemented either using a circular array or a circular doubly linked list.
In a deque, two pointers are maintained, LEFT and RIGHT which point to either end of the deque.
The elements in a deque stretch from LEFT end to the RIGHT and since it is circular, Dequeue[N-1] is followed by Dequeue[0].

162 of 167

Deques

There are two variants of a double-ended queue:
Input restricted deque: In this dequeue insertions can be done only at one of the ends while deletions can be done from both the ends.
Output restricted deque: In this dequeue deletions can be done only at one of the ends while insertions can be done on both the ends.

			29	37	45	54	63

0 1 2 LEFT = 3 4 5 6 RIGHT = 7 8 9

42							63	27	18

RIGHT = 0 1 2 3 4 5 6 LEFT = 7 8 9

163 of 167

Priority Queues

A priority queue is a queue in which each element is assigned a priority.
The priority of elements is used to determine the order in which these elements will be processed.
The general rule of processing elements of a priority queue can be given as:

An element with higher priority is processed before an element with lower priority
Two elements with same priority are processed on a first come first served (FCFS) basis

Priority queues are widely used in operating systems to execute the highest priority process first.
In computer’s memory priority queues can be represented using arrays or linked lists.

164 of 167

Linked Representation of Priority Queues

When a priority queue is implemented using a linked list, then every node of the list contains three parts: (1) the information or data part, (ii) the priority number of the element, (iii) and address of the next element.
If we are using a sorted linked list, then element having higher priority will precede the element with lower priority.

A

1

B

2

C

3

D

3

E

4

X

A

1

B

2

C

3

F

4

D

5

E

6

X

Priority queue after insertion of a new node

165 of 167

Array Representation of Priority Queues

When arrays are used to implement a priority queue, then a separate queue for each priority number is maintained.
Each of these queues will be implemented using circular arrays or circular queues. Every individual queue will have its own FRONT and REAR pointers.
We can use a two-dimensional array for this purpose where each queue will be allocated same amount of space.
Given the front and rear values of each queue, a two dimensional matrix can be formed.

166 of 167

Multiple Queues

When implementing a queue using an array, the size of the array must be known in advance.
If the queue is allocated less space, then frequent OVERFLOW conditions will be encountered.
To deal with this problem, the code will have to be modified to reallocate more space for the array, but this results in sheer wastage of memory. Thus, there lies a tradeoff between the frequency of overflows and the space allocated.
A better solution to deal with this problem is to have multiple queues or to have more than one queue in the same array.
One important point to note is that while queue A will grow from left to right, the queue B on the same time will grow from right to left.

Queue A Queue B

0 1 2 3 4 ………………………………. n-4 n-3 n-2 n-1

167 of 167

Applications of Queues

Queues are widely used as waiting lists for a single shared resource like printer, disk, CPU.
Queues are used to transfer data asynchronously e.g., pipes, file IO, sockets.
Queues are used as buffers on MP3 players and portable CD players, iPod playlist.
Queues are used in Playlist for jukebox to add songs to the end, play from the front of the list.
Queues are used in OS for handling interrupts. When programming a real-time system that can be interrupted, for ex, by a mouse click, it is necessary to process the interrupts immediately before proceeding with the current job. If the interrupts have to be handled in the order of arrival, then a FIFO queue is the appropriate data structure