Data Structure

A particular organization of data by the logical or mathematical model is called "Data Structure".
Data Structure is not a language. Simply data structrure is the concept of set of algorithms used to
structure the information. It is not a programming language like C, C++, Java etc. So, these are just a
set of algorithms. We are implementing these algorithms using any programming language.

Topics :-

 Arrays
 Linked List
 Stack
 Queue
 Tree
 Graph
 Sorting
 Searching

Data Structures are divided into two types :-

Data
Structure

Non-
Linear
Linear

 Linear Data Structure – The arrangement of elements are in sequential manner.

Eg.- Arrays, Stacks, Queues, Linked Lists.

 Non-Linear Data Structure – The arrangement of elements are not in sequential manner.

Eg.- Trees, Graphs

Before starting Data Structure, we should have good knowledge on following topics :-

1. Arrays
2. Functions (Recursive function also)
3. Structure
4. Pointer
5. DMA (Dynamic Memory Allocation)
 Arrays
Introduction

An array is a collection of similar type of elements ie. all the elements of an array must be of same
type.

The elements of an array are identified and accessed by a single name with the help of an
index number / subscript number. Due to the subscript number an array is also called "Subscripted
Variables".

Array always occupy contiguous memory locations.

Declaring An Array

int n[10];

Initializing an array

int n[5]={10,20,30,40,50};

or

int n[ ]={10,20,30,40,50}; - in this case the size is automatically

assumes as the number of elements.

Linear Search ( Array A, Size n, Value x)

Step 1: Set i to 0
Step 2: if i > n-1 then go to step 7
Step 3: if A[i] = x then go to step 6
Step 4: Set i to i + 1
Step 5: Go to Step 2
Step 6: Print Element x Found at index i and go to step 8
Step 7: Print element not found
Step 8: Exit

or

LinearSearch(a,n,item)

Begin
for i=0 to (n-1) by 1 do
if(a[i]=item) then
 return i
endif
endfor
return -1
End

Binary Search(Array A, Size n, Value x)

Begin
Set low=0
Set high=n-1
while (low<=high) do
mid=(low+high)/2
if(x=A[mid]) then
Print Number is found at location mid
exit
else if(x>A[mid]) then
Set low=mid+1
else
Set high=mid-1
endif
endwhile
if low>high then
Print Number is not found
endif
End

RECURSIVE FUNCTION
It is like a normal function but it has an extra feature that it can be called by itself. In another word we can
say, if a function is called by itself then it is known as "Recursive Function".

There are two types of recursion / recursive function :-

 Direct Recursion – If a function is called by itself then it is known as "Direct Recursion".

Eg.-

Void display( )
{
…………
…………
display( );
 }
 Indirect Recursion – If a function calls another function and the called function agains calls the
previous one then it is known as "Indirect Recursion".
Eg.-

Void display( )
{
……….
……….
show( );
}
void show( )
{
…………
display( );
}
Note – Recursive function is mainly used to solve repetitive problems (looping problems). In recursive
function, loop is not used.

A Recursive Function should have following properties :-

 There must be a certain criteria, called base criteria, for which the function does not call
itself.
 Each time the function does call iteslef (directly or indirectly), it must be closer to the base
criteria, i.e. it uses an argument closer than the one it was given.

DYNAMIC MEMORY ALLOCATION (DMA)

Memory Allocation

The memory allocation may be classified into two categories :-

1. Static Allocation
2. Dynamic Allocation

Static Allocation

In Static Allocation, the required memory size must be defined before loading and executing the program.
Dynamic Allocation

In Dynamic Allocation, the required memory size is allocated while program is getting executed. (at run time
/ during program execution).

There are three dynamic memory allocation functions and one memory deallocation functions. These are :-

malloc ( ) –

The malloc() function stands for memory allocation. It is a function which is used to allocate a block of
memory dynamically. It reserves memory space of specified size and returns pointer of type void which can
be converted to any other type. If allocation fails, it returns NULL.

Syntax :- pointer variable = (cast type *) malloc (size in bytes);

Ex.- ptr=(int *) malloc(10);

ptr=(int *) malloc(10*sizeof(int));

calloc( ) –

The calloc() function stands for contiguous allocation. This function is used to allocate multiple blocks of
memory. It is a dynamic memory allocation function which is used to allocate the memory to complex data
structures such as arrays and structures.

Malloc() function is used to allocate a single block of memory space while the calloc() function is used to
allocate multiple blocks of memory space. Each block allocated by the calloc function is of the same size.

Syntax:

ptr = (cast_type *) calloc (n, size);

 The above statement is used to allocate n memory blocks of the same size.

 After the memory space is allocated, then all the bytes are initialized to zero.

 The pointer which is currently at the first byte of the allocated memory space is returned.

Whenever there is an error allocating memory space then a null pointer is returned.

Ex.- ptr=(int *) calloc(5,sizeof(int));

realloc( ) –
realloc stands for reallocation of memory. Using the realloc() function, you can add more memory size to
already allocated memory. It expands the current block while leaving the original content as it is. realloc can
also be used to reduce the size of the previously allocated memory.

Syntax

ptr = realloc (ptr,newsize);

The above statement allocates a new memory space with a specified size in the variable newsize. After
executing the function, the pointer will be returned to the first byte of the memory block. The new size can
be larger or smaller than the previous memory. We cannot be sure that if the newly allocated block will
point to the same location as that of the previous memory block. This function will copy all the previous data
in the new region. It makes sure that data will remain safe.

Free ( ) –

The memory for variables is automatically deallocated at compile time. In dynamic memory allocation, you
have to deallocate memory explicitly. If not done, you may encounter out of memory error.

The free() function is called to release/deallocate memory. By freeing memory in your program, you make
more available for use later.

(It releases the memory dynamically allocated.)

Syntax :- free(pointer);

Eg.- free(ptr);

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
int main()
{
int n,i;
int *ptr;
printf("Enter the number of elements ");
scanf("%d",&n);
ptr=(int *)malloc(n*sizeof(int));
if(ptr==NULL)
{
printf("Allocation Fail..");
exit(1);
}
printf("\nEnter %d numbers ",n);
for(i=0;i<n;i++)
 {
scanf("%d",(ptr+i));
}
printf("The elements are \n");
for(i=0;i<n;i++)
{
printf("\n%d",*(ptr+i));
}
free(ptr);
}

SELF – REFERENTIAL STRUCTURE

Self Referential Structures are those structures that have one or more pointers which points to the
same type of structure, as their member.

In other words, structures pointing to the same type of structures are self-referential structure. It
used in the many of the data structures like in Linked List, Trees, Graphs etc.

Ex: In Singly Linked List

struct node

int data;

struct node *next; // self-referential

};

In the above declaration next is the pointer to the structure of type node. Here next is the pointer
which will contains the address of the structure of the same type (i.e address of next node) and
data will contain the actual data.

LINKED LIST
A linked list is a linear collection of data elements, called nodes. The linear order is maintained by
pointers. Each node is divided into two or more parts.

Types of Linked List :-

 Linear Linked List or One-way list or Singly Linked List

 Doubly Linked List or Two-way list
 Circular Linked List
 Header Linked List
Advantages of Linked List over Arrays :

 Items can be added or removed from the middle of the list without taking extra burden to
shifting the elements.

 There is no need to define an initial size.

Disadvantages of Linked List :

 There is no "random" access - it is impossible to reach the nth item in the array without first
iterating over all items up until that item. This means we have to start from the beginning of
the list and count how many times we advance in the list until we get to the desired item.

 Dynamic memory allocation and pointers are required, which complicates the code and
increases the risk of memory leaks. (memory leaks - memory occupied but not released)

 Linked lists have a much larger overhead over arrays, since linked list items are dynamically
allocated (which is less efficient in memory usage) and each item in the list also must store
an additional pointer.

Linear Linked List / Singly Linked List

In a linear linked list also called singly linked list or one-way list, each node divided in two parts :-

 first part contains the information of the element and

 second part, called the link field or nextpointer field or address field contains the address of
the next node in the list.

In addition, another pointer variable i.e. head, is used that contains the address of the first element
of the list. The last element of the linked list have NULL value in the address field to mark the end of
the list.

Representation of Singly Linked List

struct node
{
int val;
 struct node *next;
};
node *head;

Operations on Linked List

 Create an Empty List

 Add
 Delete
 Update
 Print / Traverse

Program on Linked List

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<malloc.h>
struct node
{
int val;
struct node *next;
};
void createlist(node **);
void add(node **,int);
void display(node **);
void update(node **,int,int);
void deleteno(node **,int);
void main()
{
node *head;
int ch,n,n1;
createlist(&head);
while(1)
{
clrscr();
printf("\n1. Add");
printf("\n2. Delete");
printf("\n3. Update");
printf("\n4. Display");
printf("\n5. Exit");
printf("\n\nEnter Your Choice : ");
scanf("%d",&ch);
switch(ch)
{
case 1: // Add
printf("\nEnter the no. to add : ");
scanf("%d",&n);
add(&head,n);
break;
case 2: // Delete
if(head==NULL)
printf("\nList is empty...");
else
{
printf("\nEnter the Number to Delete : ");
scanf("%d",&n);
deleteno(&head,n);
}
getch();
break;

case 3: // update
if(head==NULL)
printf("\nList is empty...");
else
{
printf("\nEnter the Old Number : ");
scanf("%d",&n);
printf("\nEnter the New Number to Update : ");
scanf("%d",&n1);
update(&head,n,n1);
}
getch();
break;
case 4: // Display
if(head==NULL)
printf("\nList is empty...");
else
display(&head);
getch();
break;

case 5:
exit(1);
default :
printf("\nInvalid Choice...");
 }
}
}
void createlist(node **head)
{
*head=NULL;
}
void add(node **head,int n)
{
node *ptr,*tmp;
ptr=(node *)malloc(sizeof(node));
ptr->val=n;
ptr->next=NULL;
if(*head==NULL)
*head=ptr;
else
{
tmp=*head;
while(tmp->next!=NULL)
tmp=tmp->next;
tmp->next=ptr;
}
printf("\nSuccessfully Added...");
getch();
}
void display(node **head)
{
node *tmp;
tmp=*head;
while(tmp->next!=NULL)
{
printf("\n%d",tmp->val);
tmp=tmp->next;
}
printf("\n%d",tmp->val);
}
void update(node **head,int n,int n1)
{
node *tmp;
tmp=*head;
int f=0;
while(tmp->next!=NULL)
{
 if(tmp->val==n)
{
tmp->val=n1;
f=1;
break;
}
tmp=tmp->next;
}
if(tmp->val==n)
{
tmp->val=n1;
f=1;
}
if(f==1)
printf("\nSuccessfully Updated...");
else
printf("\nNumber does not exist...");
}
void deleteno(node **head,int n)
{
node *tmp,*tmp1;
tmp=*head;
int f=0;
if(tmp->val==n)
{
*head=tmp->next;
free(tmp);
f=1;
}
else
{
tmp1=tmp;
while(tmp->next!=NULL)
{
if(tmp->val==n)
{
tmp1->next=tmp->next;
free(tmp);
f=1;
break;
}
tmp1=tmp;
tmp=tmp->next;
 }
if(tmp->val==n)
{
tmp1->next=tmp->next;
free(tmp);
f=1;
}
}
if(f==1)
printf("\nSuccessfully Deleted...");
else
printf("\nNumber does not exist...");
}

Doubly Linked List

In a Doubly Linked List also called Two Way List , each node divided in three parts :-

 The first part, called previouspointer field, contains the address of the preceeding element in
the list
 The second part contains the information of the element, and
 The third part, called nextpointer field, contains the address of the succeeding element in
the list.

In addition, two pointer variables, head and tail, are used that contains the address of the first
element and the address of the last element in the list respectively. The first element contains NULL
value in the previouspointer to indicate there is no element preceding it in the list, and the last
element have the NULL value in the nextpointer field to indicate that there is no element
succeeding in the list. Doubly linked list can be traversed in both directions.

Representation of Doubly Linked List

struct node
{
struct node *prev;
int val;
struct node *next;
};
 node *head,*tail;
Operations on Doubly Linked List

 Create an Empty List

 Add
 Delete
 Update
 Print / Traverse
 Print / Traverse in Reverse Order

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<malloc.h>
struct node
{
struct node *prev;
int val;
struct node *next;
};
void createlist(node **,node **);
void add(node **,node **,int);
void display(node **);
void display_reverse(node **);
void update(node **,int,int);
void deleteno(node **,node **,int);
void main()
{
node *head,*tail;
int ch,n,n1;
createlist(&head,&tail);
while(1)
{
clrscr();
printf("\n1. Add");
printf("\n2. Delete");
printf("\n3. Update");
printf("\n4. Display");
printf("\n5. Display in Reverse Order");
printf("\n6. Exit");
printf("\n\nEnter Your Choice : ");
scanf("%d",&ch);
switch(ch)
{
case 1: // Add
printf("\nEnter the no. to add : ");
scanf("%d",&n);
add(&head,&tail,n);
break;
case 2: // Delete
if(head==NULL)
printf("\nList is empty...");
else
{
printf("\nEnter the Number to Delete : ");
scanf("%d",&n);
deleteno(&head,&tail,n);
}
getch();
break;

case 3: // update
if(head==NULL)
printf("\nList is empty...");
else
{
printf("\nEnter the Old Number : ");
scanf("%d",&n);
printf("\nEnter the New Number to Update : ");
scanf("%d",&n1);
update(&head,n,n1);
}
getch();
break;
case 4: // Display
if(head==NULL)
printf("\nList is empty...");
else
display(&head);
getch();
break;

case 5: // Display in Reverse order

if(tail==NULL)
printf("\nList is empty...");
else
display_reverse(&tail);
 getch();
break;

case 6:
exit(1);
default :
printf("\nInvalid Choice...");
}
}
}
void createlist(node **head,node **tail)
{
*head=NULL;
*tail=NULL;
}
void add(node **head,node **tail,int n)
{
node *ptr,*tmp;
ptr=(node *)malloc(sizeof(node));
ptr->val=n;
ptr->next=NULL;
*tail=ptr;
if(*head==NULL)
{
ptr->prev=NULL;
*head=ptr;
}
else
{
tmp=*head;
while(tmp->next!=NULL)
tmp=tmp->next;
tmp->next=ptr;
ptr->prev=tmp;
}
printf("\nSuccessfully Added...");
getch();
}
void display(node **head)
{
node *tmp;
tmp=*head;
while(tmp->next!=NULL)
 {
//printf("\n%u-%u-%d-%u",tmp,tmp->prev,tmp->val,tmp->next);
printf("\n%d",tmp->val);
tmp=tmp->next;
}
//printf("\n%u-%u-%d-%u",tmp,tmp->prev,tmp->val,tmp->next);
printf("\n%d",tmp->val);
}
void display_reverse(node **tail)
{
node *tmp;
tmp=*tail;
while(tmp->prev!=NULL)
{
printf("\n%d",tmp->val);
tmp=tmp->prev;
}
printf("\n%d",tmp->val);
}
void update(node **head,int n,int n1)
{
node *tmp;
tmp=*head;
int f=0;
while(tmp->next!=NULL)
{
if(tmp->val==n)
{
tmp->val=n1;
f=1;
break;
}
tmp=tmp->next;
}
if(tmp->val==n)
{
tmp->val=n1;
f=1;
}
if(f==1)
printf("\nSuccessfully Updated...");
else
printf("\nNumber does not exist...");
}
void deleteno(node **head,node **tail,int n)
{
node *tmp;
tmp=*head;
int f=0;
if(tmp->val==n)
{
*head=tmp->next;
tmp->next->prev=NULL;
free(tmp);
f=1;
}
else
{
while(tmp->next!=NULL)
{
if(tmp->val==n)
{
tmp->prev->next=tmp->next;
tmp->next->prev=tmp->prev;
free(tmp);
f=1;
break;
}
tmp=tmp->next;
}
if(tmp->val==n)
{
tmp->prev->next=NULL;
*tail=tmp->prev;
free(tmp);
f=1;
}
}
if(f==1)
printf("\nSuccessfully Deleted...");
else
printf("\nNumber does not exist...");
}
Circular Linked List
A Circular Linked List is a Linear Linked List, except that the last element points to the first element.
The memory declarations for representing Circular Linked Lists are the same as for Linear Linked
Lists.

All operations performed on Linear Linked Lists can be easily extended for Circular Linked
Lists with following exceptions :-

 While inserting new node at the end of the lists, its next pointer field is made to point to the
first node.
 While testing for end of the lists, we compare the next pointer field with the address of the
first node.

Header Linked List

A Header Linked List is a Linked List, which always contains a special node, called header node, at
the beginning of the linked list. This header node usually contains vital information about the linked
list such as the number of nodes in the lists, whether the list is sorted or not etc. It is also known as
Grounded Header List.

Applications of Linked List

Linked lists are used in a wide variety of applications. Some of the applications of the linked lists
are:-
  To implement other data structures such as stacks, queues, trees and graphs.
 To maintain a directory of names.
 To manipulate polynomials.
 To represent sparce matrices. etc.

Polynomial Manipulation
Take an example of a polynomial –

It can be represented using following linked list –

In the above list, each node has the following structure –

The required memory declarations for the representation are :-

struct poly
{
int coeff;
int power;
struct poly *next;
};
poly *head;

Addition of Polynomials
For adding two polynomials, we write the polynomial terms with same power under each other and
then we add the coefficients. For example – the addition of –
To produce the sum following steps are to be performed :-

1. The term of the polynomials are scanned from left to right.

2. The terms with powers that occur only in one polynomial are simply copied into the
resulting polynomial.
3. The coefficients of terms with same powers are added and then the new term is copied into
the resulting polynomial.

/* Adding two polynomials Using Linked List */

#include<stdio.h>
#include<stdlib.h>
typedef struct link
{
int coeff;
int pow;
struct link * next;
} my_poly;

void my_create_poly(my_poly **);

void my_show_poly(my_poly *);
void my_add_poly(my_poly **, my_poly *, my_poly *);

int main(void)
{
int ch;
my_poly * poly1, * poly2, * poly3;
printf("\nCreate 1st expression\n");
my_create_poly(&poly1);
printf("\nStored the 1st expression");
my_show_poly(poly1);

printf("\nCreate 2nd expression\n");

my_create_poly(&poly2);
printf("\nStored the 2nd expression");
my_show_poly(poly2);

my_add_poly(&poly3, poly1, poly2);

 my_show_poly(poly3);

return 0;
}

void my_create_poly(my_poly **node)

{
int flag; //A flag to control the menu
int coeff, pow;
my_poly *tmp_node; //To hold the temporary last address
tmp_node = (my_poly *) malloc(sizeof(my_poly)); //create the first node
*node = tmp_node; //Store the head address to the reference variable
do {
printf("\nEnter Coeff:");
scanf("%d", &coeff);
printf("\nEnter Pow:");
scanf("%d", &pow);
tmp_node->coeff = coeff;
tmp_node->pow = pow;

//Now increase the Linked on user condition

tmp_node->next = NULL;

//Ask user for continuation

printf("\nContinue adding more terms to the polynomial list?(1-Yes,0-No): ");
scanf("%d", &flag);
if(flag==1)
{
tmp_node->next = (my_poly *) malloc(sizeof(my_poly)); //Grow the list
tmp_node = tmp_node->next;
tmp_node->next = NULL;
}
} while (flag);
}

void my_show_poly(my_poly *node)

{
printf("\nThe polynomial expression is:\n");
while(node != NULL)
{
printf("%dx^%d", node->coeff, node->pow);
node = node->next;
if(node != NULL)
 printf(" + ");
}
}

void my_add_poly(my_poly **result, my_poly *poly1, my_poly *poly2)

{
my_poly *tmp_node; //Temporary storage for the linked list
tmp_node = (my_poly *) malloc(sizeof(my_poly));
tmp_node->next = NULL;
*result = tmp_node; //Copy the head address to the result linked list

//Loop while both of the linked lists have value

while(poly1 && poly2)
{
if (poly1->pow > poly2->pow)
{
tmp_node->pow = poly1->pow;
tmp_node->coeff = poly1->coeff;
poly1 = poly1->next;
}
else if (poly1->pow < poly2->pow)
{
tmp_node->pow = poly2->pow;
tmp_node->coeff = poly2->coeff;
poly2 = poly2->next;
}
else
{
tmp_node->pow = poly1->pow;
tmp_node->coeff = poly1->coeff + poly2->coeff;
poly1 = poly1->next;
poly2 = poly2->next;
}

//Grow the linked list on condition

if(poly1 && poly2)
{
tmp_node->next = (my_poly *) malloc(sizeof(my_poly));
tmp_node = tmp_node->next;
tmp_node->next = NULL;
}
}
 //Loop while either of the linked lists has value
while(poly1 || poly2)
{
//We have to create the list at beginning
//As the last while loop will not create any unnecessary node
tmp_node->next = (my_poly *) malloc(sizeof(my_poly));
tmp_node = tmp_node->next;
tmp_node->next = NULL;

if(poly1)
{
tmp_node->pow = poly1->pow;
tmp_node->coeff = poly1->coeff;
poly1 = poly1->next;
}
if(poly2)
{
tmp_node->pow = poly2->pow;
tmp_node->coeff = poly2->coeff;
poly2 = poly2->next;
}
}

printf("\nAddition Complete");
}

Sparse Matrix
In computer programming, a matrix can be defined with a 2-dimensional array. Any array with ‘m’
columns and ‘n’ rows represents a mxn matrix. There may be a situation in which a matrix contains
more number of ZERO values than NON-ZERO values. Such matrix is known as sparse matrix. So, we
can say a Sparse matrix is a matrix which contains very few non-zero elements.

When a sparse matrix is represented with 2-dimensional array, we waste lot of space to represent
that matrix. For example, consider a matrix of size 100 X 100 containing only 10 non-zero elements.
In this matrix, only 10 spaces are filled with non-zero values and remaining spaces of matrix are
filled with zero. That means, totally we allocate 100 X 100 X 2 = 20000 bytes of space to store this
integer matrix. And to access these 10 non-zero elements we have to make scanning for 10000
times.

Representing Sparse Matrix

A sparse matrix can be represented in two ways :-
 1. Array representation (an array of triplets)
2. Linked representation

Array Representation
In array representation, an array of triplets of type <row, column, element> is used to store non-
zero elements. Where first field of the triplet is used to record row position, second to record
column position and the third one to record the nonzero element of the sparse matrix.

In addition, we need to record the size of the matrix (i.e. number of rows and columns) and non-
zero elements. For this purpose, the first element of array of triplets is used, where first field stores
number of rows, the second field the number of columns and third field stores the number of
nonzero elements. The remaining elements of the array store nonzero elements of the sparse
matrix on row-major order.

eg.-

0 0 0 2 0 0 5 6 5
0 0 1 0 0 5 0 3 2
0 4 0 0 0 0 1 2 1
0 0 0 0 0 0 1 5 5
0 0 0 0 7 0 2 1 4
4 4 7
(Sparse Matrix) (Array representation of Sparse Matrix)

Linked Representation
In Linked List, each node has four fields. These four fields are :-

 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

struct sparse
{
int row;
int column;
 float value;
struct sparse *next;
};
sparse *head;

STACKS
A Stack is one of the most commonly used data structures. A stack, also called Last In First Out
(LIFO) system, is a linear list in which insertions and deletions can take place only at one end, called
the top .

There are many real-life examples of a stack. Consider an example of plates stacked over
one another in the canteen. The plate which is at the top is the first one to be removed, i.e. the
plate which has been placed at the bottommost position remains in the stack for the longest period
of time.

Operations on Stack

 Push - to insert/add an element in stack

 Pop - to delete/remove an element from stack
 Peek - to access the top element of the stack without removing it
 Display - to display all the elements of stack

Representation of Stack in Memory

A stack can be represented in memory by using :-

 A linear array
 A linear linked list

Representing a Stack using an Array

To implement a stack we need a variable, called top (or tos i.e. top of stack) that holds the index of
the top element of the stack and an array to hold the element of the stack.

#define MAX 10
struct stack
{
int top;
int element[MAX];
};
stack s;
or
#define MAX 10
int stack[MAX];
int top=-1;
A Program to Implement Stack
/* Stack */
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define MAX 10
int stack[MAX];
int tos=-1;
void push(int);
void pop();
void display();
void main()
{
int ch,n,p;
while(1) //infinite loop
{
clrscr();
printf("\n 1. Push ");
printf("\n 2. Pop ");
printf("\n 3. Display ");
printf("\n 4. Exit ");
printf("\n\n Enter your choice : ");
scanf("%d",&ch);
switch(ch)
{
case 1: // push
printf("Enter the Number to push : ");
scanf("%d",&n);
push(n);
getch();
break;
case 2: // pop
pop();
getch();
break;
case 3: // display
display();
getch();
break;
case 4:
printf("\n\n Thank you for using...Press any key to Exit... ");
getch();
exit(1); // exit from program
 default :
printf("\n\n Invalid choice...Press any key..");
getch();
}
}
}
void push(int n)
{
if(tos==MAX-1)
{
printf("Stack is Full...");
}
else
{
stack[++tos]=n;
printf("\nSuccessfully added...");
}
}
void pop()
{
int n;
if(tos==-1)
{
printf("Stack is empty...");
}
else
{
n=stack[tos];
tos--;
printf("\nThe popped element is %d",n);
}
}

void display()
{
int i;
if(tos==-1)
printf("The stack is empty...");
else
{
for(i=0;i<=tos;i++)
{
printf("%d\t",stack[i]);
 }
printf("\n Completed...");
}
}

Infix to Prefix Conversion (Polish Notation)

Step 1: Reverse the infix expression eg. A+B*C will become C*B+A. Note while reversing
each ‘(‘ will become ‘)’ and each ‘)’ becomes ‘(‘.

Step 2: Obtain the postfix expression of the modified expression i.e CB*A+.

Step 3: Reverse the postfix expression. Hence in our example prefix is : +A*BC.

Infix to Postfix Conversion (Reverse Polish Notation)

1. Scan the Infix string from left to right.

2. Initialize an empty stack.

3. If the scanned character is an operand, add it to the Postfix string.

4. If the scanned character is an operator and if the stack is empty push the character to
stack.

5. If the scanned character is an Operator and the stack is not empty, compare the
precedence of the character with the element on top of the stack.

6. If top Stack has higher precedence over the scanned character pop the stack else push the
scanned character to stack. Repeat this step until the stack is not empty and top Stack has
precedence over the character.

7. Repeat 4 and 5 steps till all the characters are scanned.

8. After all characters are scanned, we have to add any character that the stack may have to
the Postfix string.

9. If stack is not empty add top Stack to Postfix string and Pop the stack.

10. Repeat this step as long as stack is not empty.

Priority
^ - 1st
*, / - 2nd

+, - - 3rd

Evaluating Postfix Expression

Step 1 : Add ) to postfix expression.

Step 2 : Read postfix expression Left to Right until ) encountered

Step 3 : If operand is encountered, push it onto Stack

Step 4 : If operator is encountered, Pop two elements

A -> Top element

B-> Next to Top element

Evaluate B operator A

push B operator A onto Stack

Step 5 : Set result = pop

Step 6 : END

QUEUES
A Queue is a linear structure which follows a particular order in which the operations are performed. The
order is First In First Out (FIFO). In a Queue items are inserted one end (rear end) known
as enqueue operation and deleted from the other end (front end) known as dequeue operation.

A good example of a queue is any queue of consumers for a resource where the consumer that came
first is served first. The difference between stacks and queues is in removing. In a stack we remove the item
the most recently added; in a queue, we remove the item the least recently added.

Operations on Queue

 Enqueue - to insert/add an element in queue

 Dequeue - to delete/remove an element from queue
 Peek - to access the top element of the queue without removing it
 Display - to display all the elements of queue
Representation of Stack in Memory

A queue can be represented by using :-

 A linear array (Static Queue)

 A linear linked list (Dynamic Queue)

Representing a Queue using an Array

To implement a queue we need two variables, called front and rear that holds the index of the first
and last elements of the queue and an array to hold the element of the queue.
#define MAX 10

struct queue

int data[MAX];

int front, rear ;

};

queue q;

Or,

#define MAX 10

int queue[MAX];

A Program to implement Queue

# include <stdio.h>
# include <conio.h>
# include <stdlib.h>
# define MAX 10
int queue[MAX];
int front=-1,rear=-1;
void add(int);
void del();
void display();
void main ()
{
int n,ch;
while(1)
{
clrscr();
printf("\n1. Add ");
printf("\n2. Delete");
printf("\n3. Update");
printf("\n4. Display");
printf("\n5. Exit");
printf("\nEnter Your Choice ");
scanf("%d",&ch);
switch(ch)
{
 case 1:
printf("\nEnter the number to add ");
scanf("%d",&n);
add(n);
break;
case 2:
del();
break;
case 3:
break;
case 4:
display();
break;
case 5:
printf("\n\nThank You...");
getch();
exit(1);
default:
printf("\nInvalid Choice...");
}
}
}

void add(int n)
{
if(rear==MAX-1)
{
printf("\nQueue is full...");
}
else
{
queue[++rear]=n;
if(front==-1)
front++;

printf("\nSuccessfully added...");
}
getch();
}
void del()
{
int x;
 if(front==-1 && rear==-1)
{
printf("\nQueue is empty...");
}
else
{
x=queue[front];
front++;
if(front>rear)
{
front=-1;
rear=-1;
}
printf("\nDeleted element is %d",x);
}
getch();
}
void display()
{
int i;
if(front==-1 && rear==-1)
{
printf("\nQueue is empty...");
getch();
return;
}
for(i=front;i<=rear;i++)
{
printf("%d\t",queue[i]);
}
getch();
}

TREE
A Tree is data structure which is used to represent hierarchical data. For example, we want to show
employees in an organization and their positions in organizational hierarchy, then we can show it
something like this :-
This above particular logical structure is a Tree. If we look at this structure upside down then it will
look like a real tree. The root here is at top and we are branching out in downward direction.

So, Tree data structure can be defined as a collection of entities called nodes linked together to
simulate hierarchy. Tree is a non-linear data structure. Its a hierarchical structure. The topmost
node in the tree is called root of the tree. Each node will contain some data and this can be data of
any type.

Tree Terminologies
Consider the following tree :-

The topmost node in the tree is called root. Root would be the only node without a parent. If a
node has a direct link to some other node, then we have a parent child relationship between the
nodes.

In this tree, 1 is parent of 2 and 3. 2 is child of 1. And now, 4 , 5 and 6 are children of 2. So, node 2 is
child of node 1, but parent of nodes 4, 5 and 6. Children of same parent are called sibling. Here, 2
and 3 are sibling, then 4, 5 and 6 are sibling, then 7,8 are sibling and finally 9 and 10 are also sibling.
Any node in the tree that does not have a child is called leaf node. So, 4, 6, 8, 9, 10 and 11 are leaf
nodes. All other nodes with at least one child can be called internal nodes. So, 1, 2, 3, 5 and 7 are
internal nodes.

We can have some more relationships like parent of parent can be called grand-parent. So, 1 is
grand-parent of 4 and 4 is grand-child of 1.

In general, if we can go from node A to B walking through the links and remember these links are
not bidirectional. We have a link from 1 to 2, so we can go from 1 to 2, but we cannot go from 2 to
1. When we are walking the tree, we can walk in only one direction. So if we can go from node A to
node B, then A can be called ancestor of B and B can be called descendant of A. Lets pick up this
node numbered 10. 1, 2 and 5 are all ancestors of 10 and 10 is a descendant of all of these nodes.

Level of an element/node – The root of the tree is at level 1, its children, if any, are at level 2, their
children, if any, are at level 3, and so on.

Degree of a node – The degree of a node is the number of children it has. The degree of a leaf is
zero.

Degree of a tree – The degree of a tree is the maximum of its element degrees. Here, the degree of
tree is 3.

Level of tree - The root node is always considering at level zero, and then its adjacent children are
supposed to be at level 1 and so on. To understand the concept of level, see the above figure,
the node 1 is at level 0, the node 2 and 3 are at level 1, the nodes 4,5, 6, 7 and 8 are at level 2, the
nodes 9, 10 and 11 are at level 3..

Height of the tree / Depth of the tree - The maximum level is the height of the tree. Here the
height of the tree is 4. The other terminology used for the height of the tree is depth of the tree.

Forest - A tree may be defined as a forest in which only a single node (root) has no predecessor Any
forest is consist of collection of trees.

There are different kinds of trees that are used in different scenarios. Binary tree is most famous
and mostly used tree. The most common way of implementing tree is dynamically created nodes
linked using pointers just the way we do for linked list. We can look at the tree like this :-
Applications of Trees :-

 Storing naturally hierarchical data. eg. – File System

 Organize data for quick search, insertion, deletion etc. eg. – Binary Search Tree
 Trie Data Structure – Used for dictionary.
 Network Routing Algorithm etc.