INTRODUCTION

TO DATA
STRUCTURES
BASIC TERMINOLOGY

Data: Data are simply values or sets of values.

 Data items: Data items refers to a single unit of values.
Data items that are divided into subitems are called
Group items.
 Ex: An Employee Name may be divided into three subitems
first name, middle name, and last name.
 Data items that are not able to divide into sub-items are
called Elementary items.
 Ex: SSN
 Entity: An entity is something that has certain
attributes or properties which may be assigned values.
Ex: Attributes- Names, Age,SSN Values- Gail, 34, 40
 Entity Set: Entities with similar attributes form an
entity set.
 Information: Processed Data
 Field: is a single elementary unit of information
representing an attribute of an entity.
 Record: is the collection of field values of a given
entity.
 File: is the collection of records of the entities in a given
entity set.
WHAT IS DATA STRUCTURE?
 Data structure is representation of the logical relationship
existing between individual elements of data.
 In other words, a data structure is a way of organizing all data
items that considers not only the elements stored but also their
relationship to each other.
 The logical or mathematical model of a particular
organization of data is called a data structure.
The choice of a particular data model depends on the two
considerations:
1. It must be rich enough in structure to mirror the
actual relationships of the data in the real world.
2. The structure should be simple enough that one can
effectively process the data whenever necessary
 Data structure affects the design of both structural & functional
aspects of a program.

Program=algorithm + Data Structure

 You know that a algorithm is a step by step procedure to solve a

particular function.

 That means, algorithm is a set of instruction written to carry out

certain tasks & the data structure is the way of organizing the data
with their logical relationship retained.

 To develop a program of an algorithm, we should select an

appropriate data structure for that algorithm.

 Therefore algorithm and its associated data structures from a program.

CLASSIFICATION OF DATA
STRUCTURE
 Data structure are normally divided into two broad categories:
 Primitive Data Structure
 Non-Primitive Data Structure
PRIMITIVE DATA STRUCTURE
 There are basic structures and directly operated upon by the
machine instructions.
 In general, there are different representation on different
computers.
 For example,
NON-PRIMITIVE DATA STRUCTURE
 There are more sophisticated data structures.
 These are derived from the primitive data structures.

 The non-primitive data structures emphasize on structuring of a

group of homogeneous (same type) or heterogeneous (different
type) data items.
 The design of an efficient data structure must take operations to
be performed on the data structure.
 For example,
Based on the structure and arrangement of data, non-primitive data
structures is further classified into
1. Linear Data Structure:

 A data structure is said to be linear if its elements form a

sequence or a linear list.
 There are basically two ways of representing such linear
structure in memory.
1. One way is to have the linear relationships between the elements
represented by means of sequential memory location- called
arrays.
2. The other way is to have the linear relationship between the
elements represented by means of pointers or links-called linked
lists.
 The common examples of linear data structure are Arrays,
Queues, Stacks, Linked list.
ARRAYS
 An Array is defined as, an ordered set of similar data items.
 All the data items of an array are stored in consecutive memory
locations.
 The data items of an array are of same type and each data items
can be accessed using the same name but different index value.
 An array is a set of pairs, such that each index has a value
associated with it. It can be called as corresponding or a mapping.
 Simply, declaration of array is as follows:

int arr[10];
 Where int specifies the data type or type of elements arrays stores.

 “arr” is the name of array & the number specified inside the
square brackets is the number of elements an array can store, this
is also called sized or length of array.
Example:

Following are some of the concepts to be remembered about

arrays:
• The individual element of an array can be accessed by
specifying name of the array, following by index or subscript
inside square brackets.
• The first element of the array has index zero[0]. It means the
first element and last element will be specified as: arr[0] &
arr[4] respectively.
 The elements of array will always be stored in the consecutive
(continues) memory location.
 The number of elements that can be stored in an array, that is the size
of array or its length is given by the following equation:
(Upperbound- lowerbound)+1
 For the above array it would be
(4-0)+1=5,where 0 is the lower bound of array and 4 is the upper
bound of array.
 Array can always be read or written through loop. If we read a one-
dimensional array it require one loop for reading and other for writing
the array.
 For example: Reading an array
For(i=0;i<10;i++)
scanf(“%d”,&arr[i]);
 For example: Writing an array
For(i=0;i<10;i++)
printf(“%d”,arr[i]);
LISTS
 A lists (Linear linked list) can be defined as a collection of variable
number of data items.
 Lists are the most commonly used non-primitive data structures.
 An element of list must contain at least two fields, one for storing
data or information and other for storing address of next element.
 As you know for storing address we have a special data structure of
list the address must be pointer type.
 Technically each such element is referred to as a node, therefore a
list can be defined as a collection of nodes as show bellow:

 Types of linked lists:

 Single linked list
 Doubly linked list
 Single circular linked list
STACK
 A stack is also an ordered collection of elements like arrays, but it
has a special feature that deletion and insertion of elements can
be done only from one end called the top of the stack (TOP)
 Due to this property it is also called as last in first out type of data
structure (LIFO).
 It could be through of just like a stack of plates placed on table in
a party, a guest always takes off a fresh plate from the top and the
new plates are placed on to the stack at the top.
 It is a non-primitive data structure.

 When an element is inserted into a stack or removed from the

stack, its base remains fixed where the top of stack changes.
 Insertion of element into stack is called PUSH and deletion of
element from stack is called POP.
 The bellow show figure how the operations take place on a stack:
QUEUE
 Queue are first in first out type of data structure (i.e. FIFO)
 In a queue new elements are added to the queue from one end
called REAR end and the element are always removed from
other end called the FRONT end.
 The people standing in a railway reservation row are an example
of queue.
 Each new person comes and stands at the end of the row and
person getting their reservation confirmed get out of the row
from the front end.
 The bellow show figure how the operations take place on a
stack:
2.Non-linear Data Structure:
 A data structure is said to be non-linear if the data are not
arranged in sequence or a linear.
 The insertion and deletion of data is not possible in linear
fashion.
 This structure is mainly used to represent data containing a
hierarchical relationship between elements.
 Trees and graphs are the examples of non-linear data structure.
TREES
 A tree can be defined as finite set of data items (nodes).
 Tree is non-linear type of data structure in which data items are
arranged or stored in a sorted sequence.
 Tree represent the hierarchical relationship between various
elements.
In trees:
 There is a special data item at the top of hierarchy called the Root
of the tree.
 The remaining data items are partitioned into number of mutually
exclusive subset, each of which is itself, a tree which is called the
sub tree.
 The tree always grows in length
towards bottom in data structures,
unlike natural trees which grows upwards.
 The tree structure organizes the

data into branches, which related the information.

GRAPH
 Graph is a mathematical non-linear data structure capable of
representing many kind of physical structures.
 It has found application in Geography, Chemistry and
Engineering sciences.
 Definition: A graph G(V,E) is a set of vertices V and a set of
edges E.
 An edge connects a pair of vertices and many have weight such
as length, cost and another measuring instrument for according
the graph.
 Vertices on the graph are

shown as point or circles

and edges are drawn as
arcs or line segment.
Operations on Data Structure
 Create: The Create operation results in reserving memory for the
program elements. The creation of data structures may take place
either during compile time or during run time.
 Selection: The Selection operation deals with accessing a
particular data within a data Structure.
 Updating: The Update operation updates or modifies the data in
the data structure.
 Searching: The Searching operation finds the presence of the
desired data item in the list of data items.
 Sorting: Sorting is the process of arranging all the data
items in the data structure in a particular order, say for
example, either in ascending order or in descending order.
 Merging:Merging is a process of combing the data items of two
different sorted list into a single list.

 Destroy or Delete:The Destroy operation destroys the memory

space allocated for the specified data structure.
DIFFERENCE BETWEEN PRIMITIVE AND
NON PRIMITIVE
REVIEW OF POINTERS AND DYNAMIC
MEMORY ALLOCATION
 Pointer: A pointer is a special variable which contains
address of a memory location.
 Using this pointer, the data can be accessed.

For example, assume that a program contains four

occurrences of a constant 3.1459. During the compilation
process, four copies of 3.1459 can be created as shown
below:
 However, it is more efficient to use one copy of 3.1459
and three pointers referencing a single copy, since less
space is required for a pointer when compared to floating
point number. This can be represented pictorially as
shown below:

General form of pointer declaration is –

Data_type* name;
Here float *b,*c,*d;
DYNAMIC MEMORY ALLOCATION
 This is process of allocating memory-space during execution-
time (or run-time).
 This is used if there is an unpredictable storage requirement.

 Memory-allocation is done on a heap.

 Dynamic memory management refers to manual memory

management. This allows you to obtain more memory when
required and release it when not necessary.
 There are 4 inbuilt library function in c under <stdlib.h>

Function Use of Function

malloc() Allocates required size of bytes and returns a
pointer first byte of allocated space.
calloc() Allocates required size of bytes and returns a
pointer first byte of allocated space.
free() Deallocates the previously allocated space
realloc() Change the size of previously allocated space.
malloc() function in c:
 malloc () function is used to allocate space in memory during
the runtime of the program.
 malloc () function reserves a block of memory of specified
size and returns a pointer of type void.
 It returns NULL pointer if it couldn’t able to allocate requested
amount of memory.
Syntax:
ptr=(cast_type *) malloc(byte_size);
Here, ptr is a pointer of type cast_type.
 The malloc() will returns a pointer to an area of memory with
size byte_size
Example:
ptr= (int *) malloc(100 * sizeof(int));
 The memory space is equivalent to 100 times the size of an int bytes
and address of the first byte is assigned to pointer x of type of int.
Similarly, c=(char *) malloc (10);
 This allocate 10 bytes of space for the pointer c of type char.
Note:
1. The storage space allocated dynamically has no name and therefore
its contents can be accessed only through a pointer.
2. If allocation fails due to insufficient space in heap it returns NULL,
therefore we should check whether the allocation is successful before
using the memory pointer .
Free() function in C
• Dynamically allocatsed memory created with either calloc() or
malloc() doesn't get freed on its own. You must explicitly use free()
to release the space.
• The release of storage space is important when the storage is
limited.
Syntax:
free(ptr);

 Here, ptr is pointer to memory block, which is already created by

malloc() or calloc().
Note:
1. It is not the pointer that is being released but rather what it points
to.
2.To release an array of memory that was allocated by calloc() we
need only to release the pointer once. It is an error to attempt to
release elements individually.
Program: Dynamic Allocation of one-Dimensional array

#include <stdio.h>
#include <stdlib.h>
printf("Enter elements of array: ");
int main()
{ for(i = 0; i < num; ++i)
int num, i, *ptr; {
printf("enter number of printf("Enter element %d: ", i+1);
elements: "); scanf("%d", ptr+ i);
scanf("%d", &num); }
//allocate memory for nor of
elements dynamically printf ("Array elements are:");
ptr = (int*) malloc( num* for(i=0; i< num; i++)
sizeof(int));
printf ("%d ",*(ptr+i));
if(ptr == NULL)
{ free(ptr);
printf("error! memory not }
allocated.");
exit(0);
}
realloc() in C:
 realloc () function modifies the allocated memory size by
malloc () and calloc () functions to new size.
 If enough space doesn’t exist in memory of current block to
extend, new block is allocated for the full size of reallocation,
then copies the existing data to new block and then frees the
old block.
Syntax:

ptr = realloc(ptr, newsize);

#include <stdio.h>
output
#include <stdlib.h>
address of previously
int main() allocated memory:
{ 12414992
int *ptr, i , n1, n2; 12414996
printf("enter size of array: "); 12415000
scanf("%d", &n1); 12415004
ptr = (int*) malloc(n1 * sizeof(int));
printf("address of previously allocated memory: "); Enter new size of array: 10
12414992
for(i = 0; i < n1; ++i) 12414996
printf("%d\n",ptr + i); 12415000
12415004
printf("\nEnter new size of array: "); 12415008
scanf("%d", &n2); 12415012
ptr = realloc(ptr, n2); 12415016
for(i = 0; i < n2; ++i) 12415020
printf("%d\n", ptr + i); 12415024
return 0; 12415028
}
DYNAMICALLY ALLOCATION OF
ONE-DIMENSIONAL ARRAYS

When writing programs, sometimes we cannot reliably

determine how large an array must be.
• A good solution to this problem is to
→ defer this decision to run-time &
→ allocate the array when we have a good estimate of
required array-size
• Dynamic memory allocation can be performed as
follows:
Program :To sort array elements // Sorting the array using pointer
#include <stdio.h> for (i = 0; i < n; i++) {
for (j = i + 1; j < n; j++)
int main() { {
int *a, i, j, tmp, n; if (*(a + i) > *(a + j))
printf("\n\n Pointer : Sort an array using {
pointer :\n"); tmp = *(a + i);
printf("---------------------------------\n"); *(a + i) = *(a + j);
*(a + j) = tmp;
// Input the number of elements to store in }
the array }
printf(" Input the number of elements to }
store in the array : ");
scanf("%d", &n); // Displaying the sorted array elements
printf("\n The elements in the array after
// Input elements into the array sorting : \n");
printf(" Input %d number of elements in for (i = 0; i < n; i++) {
the array : \n", n); printf(" element - %d : %d \n", i + 1, *(a
for (i = 0; i < n; i++) { + i));
printf(" element - %d : ", i + 1); }
scanf("%d", a + i);
} printf("\n");
}
ALGORITHM SPECIFICATION
 An algorithm is a finite set of instructions that, if followed, accomplishes
a particular task. In

 addition, all algorithms must satisfy the following criteria:

1. Input: There are zero or more quantities that are externally supplied.

2. Output: At least one quantity is produced.

3. Definiteness: Each instruction is clear and unambiguous

4. Finiteness: If we trace out the instructions of an algorithm, then for all

cases, the algorithm terminates after a finite number of steps.

5. Effectiveness: Every instruction must be basic enough to be carried out,

in principle, by a person using only pencil and paper. It is not enough that
each operation be definite as in (3); it also must be feasible.
1.Selection sort
Algorithm: Selection sort
2.Finding the Smallest Element in an Array
Algorithm :Finding the Smallest Element in an Array
3:Binary Search
Algorithm :Binary Search
RECURSIVE ALGORITHMS
• A function calls itself either directly or indirectly during
execution.
• Recursive-algorithms when compared to iterative-
algorithms are normally compact and
easy to understand.
Various types of recursion:
1) Direct recursion: where a recursive-function invokes itself.
2) Indirect recursion: A function which contains a call to
another function which in turn calls another function and so
on and eventually calls the first function.
1:Factorial using recursion
Algorithm 1:Factorial using recursion
2.Algorithm : Binary search using recursion

#include <stdio.h>
int binarySearch(int arr[], int left, int right, int key)
{
if (right >= left)
{
int mid = left + (right - left) / 2;
if (arr[mid] == key)
return mid;
if (arr[mid] > key)
return binarySearch(arr, left, mid - 1, key);
else
return binarySearch(arr, mid + 1, right, key);
}
return -1;
}
Algorithm 3:Tower of Hanoi using recursion
Example 1:Tower of Hanoi when only one disk and towers A, B,
and C are given:
Example 2:Tower of Hanoi when Two disk and towers A, B, and C
are given: Move 1 disc from A to B using C

Move 1 disc from A to C

Move 1 disc from B to C using A

Completed the Move

Example 3:Tower of Hanoi when Three disk and towers A, B, and C
are given:

Move 2 Disc from A to B using C

Move a Disc from A to C

Move 2 Disc from B to C using A

#include <stdio.h>

// Tower of Hanoi program in C using Recursion

void toH(int n, int A, int B int C)
{
if (n == 1)
{
printf("\n Move disk 1 from rod %c to rod %c",A ,C );
return;
}
toH(n-1, A, C, B);
printf("\n Move disk %d from rod %c to rod %c", n, A, C);
toH(n-1, B, A,C);
}

int main()
{
int no_of_disks ;
printf("Enter number of disks: ");
scanf("%d", &no_of_disks);
toH(no_of_disks, A,B,C);
return 0;
}
STRUCTURE AND UNION
Structures:
A structure is a collection of itmes of different data types, where each item is
identified as to its type and name.
Struct Person
{
char name[10];
int age;
float salary;
};
Dot operator(.) is used to access a particular member of the structure.
strcpy(person.name,"james") ;
person.age=35
person.salary = 35000;
 We can create our own structure data types by using the typedef statement as below:
typedef struct students
{
char name[50];
char branch[50];
int ID_no;
} stu;
 Variables can be declared as follows:
Stu stu1,stu2;
 Structures cannot be directly checked for equality or inequality. So, we can
write a function to do this.
 We can embed a structure within a structure.
struct Employee
{
char ename[20];
int ssn;
float salary;
struct date
{
int date;
int month;
int year;
}DATE;
}emp1={“Rahul”,454,120000,{ 12,2,2000}};
 Self-Referential Structures
• A self-referential structure is one in which one or more of
its components is a pointer to itself.
• These require dynamic storage management routines
(malloc & free) to explicitly obtain and release memory.
• They are extensively used to build complex and dynamic
data structures such as linked lists and trees.

Struct Node
{
int data ;
struct node * link ;
};
 Consider three structures and values assigned to their respective
fields:
Node item1,item2,tem3;
Item1.data=‘a’;
Item2.data=‘b’;
Item3.data=‘c’;
Item1.link= Item2.link= Item3.link=NULL;
 We can attach these structures together as follows:

Item1.link=&item2;
Item2.link=&item3;

 This will create the linked list as shown below:

Union
 Unions are a special form of Structures.
 In structures, each member has its own storage location, whereas all the
members of a union use the same location.
union item
{
int m;
float x;
}code c1;
 We could assign values to c1 and c2 as:

c1.m=10;
c1.x= 20

 we first place a value in the tag field. This allows us to determine which
field in the union is active. We then place a value in the appropriate field
of the union.
POLYNOMIAL ABSTRACT DATA TYPE
 A polynomial is a sum of terms, where each term has a form axe , where
x=variable, a=coefficient and e=exponent.
For ex, A(x)=3x20+2x5+4 and B(x)=x4+10x3+3x2+1

 The largest(or leading) exponent of a polynomial is called its degree.

Operations:

 Polynomial(); //construct the polynomial p(x)=0

 Polynomial Addpoly(Polynomial A, Polynomial B); //returns result of

two polynomials.

 Polynomial Subpoly(Polynomial A, Polynomial B);

//returns subtraction of two polynomials

 Polynomial Multpoly(Polynomial A, Polynomial B);

//returns multiplication of two polynomials

Polynomial Representation:
 Polynomial may be represented using array (or) linked
lists.
Polynomial as Array Representation :
 It is resulted that exponent of a expression are arranged
from 0 to highest value(degree) which is represented by
subscripts(index) of respective exponents are placed at
appropriate index in the array.
Representation 1:
Advantage: Easy to Store and Represent
Disadvantage: Huge array size is required, waste of space
Representation 2:

Code for representations:

Addition of two Polynomials:
Let A and B be the two polynomials represented by the array/linked list.
1. while Both A and B are having terms (not null), repeat step
2. If powers of the two terms are equal
then insert the result of the terms into the result Polynomial
 Advance(move to next term) A
 Advance(move to next term) B
 Else if the power of the first polynomial A> power of second
polynomial B
Then insert the term from first polynomial A into result polynomial
 Advance(move to next term) A
 Else insert the term from second polynomial B into result polynomial

 Advance(move to next term) B

3. copy the remaining terms from the non empty polynomial into the
result polynomial
int addPoly(struct poly p1[10], struct else
poly p2[10], int t1, int t2, struct poly {
p3[10]) p3[k].coeff = p2[j].coeff;
{ p3[k].expo = p2[j].expo;
int i, j, k; j++; k++;
i = 0; j = 0; k = 0; }
while (i < t1 && j < t2) }
{ /* for rest over terms of polynomial 1 */
if (p1[i].expo == p2[j].expo) while (i < t1)
{ {
p3[k].coeff = p1[i].coeff + p2[j].coeff; p3[k].coeff = p1[i].coeff;
p3[k].expo = p1[i].expo; p3[k].expo = p1[i].expo;
i++; j++; k++; i++; k++;
} }
else if (p1[i].expo > p2[j].expo) /* for rest over terms of polynomial 2 */
{ while (j < t2)
p3[k].coeff = p1[i].coeff; {
p3[k].expo = p1[i].expo; p3[k].coeff = p2[j].coeff;
i++; k++; p3[k].expo = p2[j].expo;
} j++; k++;
}
Polynomial as Linked Representation:
A Polynomial node has mainly two fields. Exponent and
coefficient.

In each node the exponent field will store the

corresponding exponent and the coefficient field will store
the corresponding coefficient. Link field points to the next
item in the polynomial.
SPARSE MATRIX REPRESENTATION
 We can classify uniquely any element within a matrix by using the triple .
Therefore, we can use an array of triples to represent a sparse matrix.
 A set of triples, <row, col, value>, where row and col are integers and form
a unique combination
 Sparse matrix contains many zero entries.
Operations:
 void create(n);//creates a SparseMatrix that can hold n non-zero
elements information.
 SparseMatrix transpose(SparseMatrix A); //It return the matrix
produced by
 interchanging the row and column value of every triple.

 SparseMatrix add(SparseMatrix A, SparseMatrix B); //if dimensions of

A and B are the same return the matrix else return error.
 SparseMatrix multiply(SparseMatrix A, SparseMatrix B); // if number
of columns in A equals number of rows in B return the matrix C produced
by multiplying A by B according to the formula: C[i][j]= Ʃ(A[i][k]*B[k][j])
where C[i][j] is the (i,j) th element else return error
Representation of Sparse Matrix:

Here,
Row→ index of row, where non-zero element is located
Column→ index of column, where non-zero element is
located
Value→value of non zero element is located at index.
 TRANSPOSING A MATRIX
• To transpose a matrix ,we must interchange the rows and columns.
• Each element a[i][j] in the original matrix becomes element b[j][i]
in the transpose matrix.
• Algorithm To transpose a matrix:
Example:
THE STRING ABSTRACT DATA TYPE
 The string, whose component elements are characters. As an ADT, we
define a string to have the form, S = So, .. . , where Si are characters taken
from the character set of the programming language.
 If n = 0, then S is an empty or null string.
 There are several useful operations we could specify for strings.
 we represent strings as character arrays terminated with the null
character \0.
Copy one string to another string

#include <stdio.h>
int main()
{
char s1[100], s2[100], i;
printf("Enter string s1: ");
gets(s1);
for(i = 0; s1[i] != '\0'; ++i)
{
s2[i] = s1[i];
}
s2[i] = '\0';
puts(s2);
return 0;
}
Concatenation of two Strings
void main()
{
char str1[25],str2[25];
int i=0,j=0;
printf(" Enter First String:\n");
gets(str1);
printf(" Enter Second String:\n");
gets(str2);
while(str1[i]!='\0’)
i++;
while(str2[j]!='\0')
{
str1[i]=str2[j];
j++;
i++;
}
str1[i]='\0’; //optional
printf("Concatenated String”);
puts(str1);
}
Program :To compare 2 strings
#include<stdio.h>
main()
{
char str1[5],str2[5];
int i,temp = 0;
printf("Enter the string1 value: ");
gets(str1);
printf(" Enter the String2 value: ");
gets(str2);
for(i=0; str1[i]!='\0’ ||str2[i]!=‘\0’;i++)
{
if(str1[i] == str2[i])
temp = 1;
else
temp = 0;
}
if(temp == 1)
printf("Both strings are same.");
else
printf("Both string not same."); }
String insertion:
Assume that we have two strings, say string 1 and string 2, and that
we want to insert string 2 into string 1 starting at the ith position of
string 1. We begin with the declarations:
Inserting substring into the given string without built in
function
#include <stdio.h>
#include <string.h>
int main()
{
char S1[50], S2[15];
int pos, i, l1, l2;
printf("Enter String :--> ");
gets(S1);
printf("Enter Substring :--> ");
gets(S2);
printf("Enter position from where do wish to insert :--> ");
scanf("%d", &pos);
l1 = strlen(S1);
l2 = strlen(S2)
for(i = pos; i <l1; i++)
S1[pos+l2] = S1[i];
for(i = 0;i < l2; i++)
S1[pos + i] = S2[i];
puts(S1);
}
Pattern Matching:
KMP(Knuth, Morris, Pratt ) Algorithm for Pattern Searching

 Input: txt= “AABAACAADAABAABA”

pat = “AABA”
Output: Pattern found at index 0, Pattern found at index 9, Pattern found at
index 12
Def KMPSearch(pat,txt) void ComputeLPS(pat, M, lps)
{ {
M = strlen(pat); int len = 0
N = strlen(txt); int i;
LPS[M]; lps[0] = 0; // lps[0] is always 0
ComputeLPS(pat, M, lps); i = 1;
while (i < N) while (i < M)
{ {
if (pattern[j] == text[i]) if (pat[i] == pat[len]) {
{ len++;
j++; lps[i] = len;
i++; i++;
} }
if (j == M) else
{ {
printf("Found pattern at index %d",i j); if (len != 0)
j = LPS[j - 1]; {
} len = lps[len - 1];
else if (j != 0) }
j = LPS[j - 1]; else
else {
i = i + 1; lps[i] = 0;
} i++;
}
THE STACK ABSTRACT DATA TYPE
STACK:
 Stack is a linear data structure in which insertion and

deletion can perform at the same end called top of stack.

 When an item is added to a stack, the operation is called

push, and when an item is removed from the stack the

operation is called pop.
 When a stack is completely full,

it is said to be -Stack is Overflow.

 If stack is completely empty,

it is said to be -Stack is Underflow

 As shown in above figure, the elements are added in the stack
in the order A, B, C, D, E, then E is the first element that is
deleted from the stack and the last element is deleted from
stack is A. Figure illustrates this sequence of operations.
 Since the last element inserted into a stack is the first
element removed, a stack is also known as a Last-In-First-Out
(LIFO) list.
Stack Abstract Data Type:
 Elements are stored in array called STACK, insertion and
deletions can perform at TOP end.

Operations:

 Stack( int size) - initialize STACK with size and

TOP= -1

 isEmpty() – returns true if stack is empty otherwise false

 isFull() – returns true if stack is full otherwise false

 push(x) – add element x at the top of the stack

 pop() – remove top element from the stack

 peek() – get top element of the stack without removing it

Create() stack:

The element which is used to insert or delete is specified as a

structure that consists of only a key field.
1.Boolean IsEmpty(Stack)::= top < 0;

2.Boolean IsFull(Stack)::= top >= MAX_STACK_SIZE-1;

The IsEmpty and IsFull operations are simple, and is implemented
directly in the program push and pop functions. Each of these
functions assumes that the variables stack and top are global.
Add an item to a stack

•Function push() checks to see if the stack is full. If it is, it calls

stackFull, which prints an error message and terminates execution.
•When the stack is not full, we increment top and assign item to
stack[top].
Delete an item in a stack

For deletion, the stack-empty function should print an error

message and return an item of type element with a key field that
contains an error code.
Stack representation using array
push():
The steps involved in the PUSH operation is given below:
• Before inserting an element in a stack, we check whether the
stack is full.
• If we try to insert the element in a stack, and the stack is full,
then the overflow condition occurs.
• When we initialize a stack, we set the value of top as -1 to
check that the stack is empty.
• When the new element is pushed in a stack, first, the value of
the top gets incremented, i.e., top=top+1, and the element
will be placed at the new position of the top.
• The elements will be inserted until we reach the max size of
the stack.
Code:
#define SIZE 3
void push()
{
int x;
{
if(top == SIZE -1) //When stack is full
{
print("Overflow");
return;
}
top = top+1; //Incrementing top by 1
stack[top] = x; //Inserting the element
}
Pop():
The steps involved in the POP operation is given below:

• Before deleting the element from the stack, we check whether

the stack is empty.

• If we try to delete the element from the empty stack, then

the underflow condition occurs.

• If the stack is not empty, we first access the element which is

pointed by the top

• Once the pop operation is performed, the top is decremented

by 1, i.e., top=top-1.
Code:
void pop()
{
if (top == -1)
{
printf("\nUnderflow!!");
}
else
{
printf("\nPopped element: %d", stack[top]);
top = top - 1;
}
}
Peek():
This operation prints the topmost element of the stack.

int peek()
{
return stack[top]; //prints the value to which the 'top' points
}
Write a program in C to implement push, pop and display operations for stacks
using arrays.
void Display()
#include <stdlib.h> {
#define SIZE 4 if (top == -1)
int top = -1, { printf("\nUnderflow!!"); }
int stack[SIZE]; else {
void push()
{ int x;
printf("\nElements present
if (top == SIZE - 1) in the stack: \n");
{ for (int i = top; i >= 0; --i)
printf("\nOverflow!!"); printf("%d\n", stack[i]); }
} }
else
{ int main()
printf("\nEnter the element: "); {
scanf("%d", &x);
top = top + 1;
push(6);
stack[top] = x; Push(8);
}} Push(10);
void pop() Push(12);
{ Display();
if (top == -1) Pop();
{ Pop();
printf("\nUnderflow!!"); Display();
}
else { printf("\nPopped element: %d", stack[top]);
Return 0;
top = top - 1; } } }
STACK APPLICATIONS: POLISH NOTATION
Expressions: It is sequence of operators and operands that reduces to a single value after
evaluation is called an expression.
X=a/b–c+d*e–a*c
In above expression contains operators (+, –, /, *) operands (a, b, c, d, e).
Expression can be represented in in different format such as
•Prefix Expression or Polish notation
•Infix Expression
•Postfix Expression or Reverse Polish notation
Infix Expression: In this expression, the binary operator is placed in-between the operand.
The expression can be parenthesized or un- parenthesized.
Example: A + B

Here, A & B are operands and + is operand

Prefix or Polish Expression: In this expression, the operator appears before its operand.
Example: + A B

Here, A & B are operands and + is operand

Postfix or Reverse Polish Expression: In this expression, the operator appears after its
operand.
Example: A B +

Here, A & B are operands and + is operand

Precedence of the operators
In the algebraic expression, the order of the operator
precedence is given in the below table:

Operators Symbols

Parenthesis ( ), {}, [ ]

Exponents ^

Multiplication and Division *, /

Addition and Subtraction +,-

 The first preference is given to the parenthesis;

 The next preference is given to the exponents.

 In the case of multiple exponent operators, then the operation

will be applied from right to left.
INFIX TO POSTFIX CONVERSION
Rules for the conversion from infix to postfix expression:
1. Print the operand as they arrive.

2. If the stack is empty or contains a left parenthesis on top, push the

incoming operator on to the stack.
3. If the incoming symbol is '(', push it on to the stack.

4. If the incoming symbol is ')', pop the stack and print the operators until
the left parenthesis is found.
5. If the incoming symbol has higher precedence than the top of the stack,
push it on the stack.
6. If the incoming symbol has lower precedence than the top of the stack,
pop and print the top of the stack. Then test the incoming operator
against the new top of the stack.
7. If the incoming operator has the same precedence with the top of the
stack then use the associativity rules. If the associativity is from left to
right then pop and print the top of the stack then push the incoming
operator. If the associativity is from right to left then push the incoming
operator.
8. At the end of the expression, pop and print all the operators of the stack.
Consider the following Infix Expression...
(A+B)*(C-D)
The final Postfix Expression is as follows...
AB+CD-*
Example 2: A*(B*C+D*E)+F:
Program to convert infix to postfix expression
#include <limits.h> void push(char oper)
#include <stdio.h> {
#include <stdlib.h> if(isFull())
#define MAX 20 printf("Stack Full!!!!");
char stk[20]; else{
int top = -1; top++;
int isEmpty() stk[top] = oper;
{ }
return top == -1; }
} int checkIfOperand(char ch)
int isFull() {
{ return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z')
return top == MAX - 1; }
} int precedence(char ch)
char peek() {
{ switch (ch)
return stk[top]; {
} case '+':
char pop() case '-': return 1;
{
if(isEmpty()) case '*':
return -1; case '/': return 2;
char ch = stk[top];
top--; case '^': return 3;
return(ch); }
} return -1;
}
int covertInfixToPostfix(char* expression)
while (!isEmpty())
{
expression[++j] = pop();
int i, j;
for (i = 0, j = -1; expression[i]; ++i)
expression[++j] = '\0';
{
printf( "%s", expression);
if (checkIfOperand(expression[i]))
}
expression[++j] = expression[i];
else if (expression[i] == '(')
int main()
push(expression[i]);
{
else if (expression[i] == ')')
char expression[] = "((x+(y*z))-w)";
{
covertInfixToPostfix(expression);
while (!isEmpty( ) && peek() != '(')
return 0;
expression[++j] = pop();
}
if (!isEmpty( ) && peek( ) != '(')
return -1;
else
pop();
}
else
{
while (!isEmpty() &&
precedence(expression[i]) <= precedence(peek()))
expression[++j] = pop();
push(expression[i]);
}
EVALUATION OF POSTFIX EXPRESSION
 The evaluation process of postfix expression is simpler than the evaluation
of infix expressions because there are no parentheses to consider.
 To evaluate an expression, make a single left-to-right scan of it.

The algorithm for evaluation of postfix expression is as follows -

 Create a stack that holds integer type data to store the operands of the
given postfix expression. Let it be st.
 Iterate over the string from left to right and do the following –

 If the current element is an operand, push it into the stack.

 Otherwise, if the current element is an operator (say /)do the following -
• Pop an element from st, let it be op1.

• Pop another element from st, let it be op2.

• Computer the result of op2 / op1, and push it into the stack. Note
the order i.e.i.e. op2 / op1 should not be changed otherwise it will
affect the final result in some cases.
 At last, st will consist of a single element i.e. the result after evaluating the
postfix expression.
Example 1:Consider the expression: exp= “2 3 1 * + 9 -“
 Scan 2, it’s a number,

So push it into stack.

Stack contains ‘2’.

 Scan 3, again a number,

push it to stack, stack now
contains ‘2 3’ (from bottom to top)

 Scan 1, again a number,

push it to stack, stack
now contains ‘2 3 1’
 Scan *, it’s an operator.
Pop two operands from stack,
apply the * operator on operands.
We get 3*1 which results in 3.
We push the result 3 to stack.
The stack now becomes ‘2 3’.

 Scan +, it’s an operator.

Pop two operands from stack,
apply the + operator on operands.
We get 3 + 2 which results in 5.
We push the result 5 to stack.
The stack now becomes ‘5’.
 Scan 9, it’s a number.
So we push it to the stack.
The stack now becomes ‘5 9’.

 Scan -, it’s an operator,

pop two operands from stack,
apply the – operator on operands,
we get 5 – 9 which results in -4.
We push the result -4 to the stack.
The stack now becomes ‘-4’.

 There are no more elements to scan, we return the top element from
the stack (which is the only element left in a stack).
 So the result becomes -4.
Example 2:Evaluate the postfix expression:456*+
Example 3: Evaluate the postfix expression:5 3+8 2 -*
Program to evaluate postfix expression.
#include <stdio.h> int evaluate(char* expression) {
#include <stdlib.h> int i = 0;
#define MAX_SIZE 100 char symbol = expression[i];
// Stack implementation int operand1, operand2, result;
int stack[MAX_SIZE]; while (symbol != '\0') {
int top = -1; if (symbol >= '0' && symbol <= '9') {
void push(int item) { int num = symbol - '0';
if (top >= MAX_SIZE - 1) { push(num);
printf("Stack Overflow\n"); }
return; else if (is_operator(symbol)) {
} operand2 = pop();
top++; operand1 = pop();
stack[top] = item; switch(symbol) {
} case '+': result = operand1 + operand2; break;
int pop() { case '-': result = operand1 - operand2; break;
if (top < 0) { case '*': result = operand1 * operand2; break;
printf("Stack Underflow\n"); case '/': result = operand1 / operand2; break;
return -1; }
} push(result); }
int item = stack[top]; i++;
top--; symbol = expression[i]; }
return item; } result = pop();
int is_operator(char symbol) { return result; }
if (symbol == '+' || symbol == '-' || int main() {
symbol == '*' || symbol == '/') { char expression[] = “2 3 1 * + 9 –”;
return 1; } int result = evaluate(expression);
printf("Result= %d\n", result); return 0; }