//Implementation of Stack ADT using Array

#include <stdio.h>
#include <stdlib.h>

#define MAX 10

int STACK[MAX],TOP;
/* display stack element*/
void display(int []);

/* push (insert) item into stack*/

void PUSH(int [],int);

/* pop (remove) item from stack*/

void POP (int []);

void main()
{
int ITEM=0;
int choice=0;
TOP=-1;

while(1)
{
/*clrscr();*/
printf("Enter Choice (1: display, 2: insert (PUSH), 3: remove(POP)), 4: Exit..:");
scanf("%d",&choice);

switch(choice)
{
case 1:
display(STACK);
break;
case 2:
printf("Enter Item to be insert :");
scanf("%d",&ITEM);
PUSH(STACK,ITEM);
break;
case 3:
POP(STACK);
break;
case 4:
exit(0);
default:
printf("\nInvalid choice.");
 break;
}
getch();
}// end of while(1)

/* function : display(),
to display stack elements.
*/
void display(int stack[])
{
int i=0;
if(TOP==-1)
{
printf("Stack is Empty .\n");
return;
}

printf("%d <-- TOP ",stack[TOP]);

for(i=TOP-1;i >=0;i--)
{
printf("\n%d",stack[i]);
}
printf("\n\n");
}

/* function : PUSH(),
to push an item into stack.
*/
void PUSH(int stack[],int item)
{
if(TOP==MAX-1)
{
printf("\nSTACK is FULL CAN't ADD ITEM\n");
return;
}
TOP++;
stack[TOP]=item;
}

/* function : POP(),
to pop an item from stack.
*/
void POP(int stack[])
{
 int deletedItem;
if(TOP==-1)
{
printf("STACK is EMPTY.\n");
return;
}

deletedItem=stack[TOP];
TOP--;
printf("%d deleted successfully\n",deletedItem);
return;
}

//Balanced Parenthesis Checker

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define MAX 30
int top=-1;
int stack[MAX];

void push(char);
char pop();
int match(char a,char b);
int check(char []);

int main()
{
char exp[MAX];
int valid;
printf("Enter an algebraic expression : ");
gets(exp);
valid=check(exp);
if(valid==1)
printf("Valid expression\n");
else
printf("Invalid expression\n");

return 0;

}
int check(char exp[] )
{
int i;
char temp;
 for(i=0;i<strlen(exp);i++)
{
if(exp[i]=='(' || exp[i]=='{' || exp[i]=='[')
push(exp[i]);
if(exp[i]==')' || exp[i]=='}' || exp[i]==']')
if(top==-1) /*stack empty*/
{
printf("Right parentheses are more than left parentheses\n");
return 0;
}
else
{
temp=pop();
if(!match(temp, exp[i]))
{
printf("Mismatched parentheses are : ");
printf("%c and %c\n",temp,exp[i]);
return 0;
}
}
}
if(top==-1) /*stack empty*/
{
printf("Balanced Parentheses\n");
return 1;
}
else
{
printf("Left parentheses more than right parentheses\n");
return 0;
}
}/*End of main()*/
int match(char a,char b)
{
if(a=='[' && b==']')
return 1;
if(a=='{' && b=='}')
return 1;
if(a=='(' && b==')')
return 1;
return 0;
}/*End of match()*/

void push(char item)

{
if(top==(MAX-1))
{
printf("Stack Overflow\n");
return;
}
 top=top+1;
stack[top]=item;
}/*End of push()*/

char pop()
{
if(top==-1)
{
printf("Stack Underflow\n");
exit(1);
}
return(stack[top--]);
}/*End of pop()*/

//Infix to Postfix
#include<stdio.h>
char stack[20];
int top = -1;
void push(char x)
{
stack[++top] = x;
}

char pop()
{
if(top == -1)
return -1;
else
return stack[top--];
}

int priority(char x)
{
if(x == '(')
return 0;
if(x == '+' || x == '-')
return 1;
if(x == '*' || x == '/'||x== '%')
return 2;
if(x=='^')
return 3;
}
main()
{
char exp[20];
char *e, x;
printf("Enter the expression :: ");
scanf("%s",exp);
e = exp;
while(*e != '\0')
{
if(isalnum(*e))
printf("%c",*e);
else if(*e == '(')
push(*e);
else if(*e == ')')
{
while((x = pop()) != '(')
printf("%c", x);
}
else
{
while(priority(stack[top]) >= priority(*e))
printf("%c",pop());
push(*e);
}
e++;
}
// while(top != -1)
// {
// printf("%c",pop());
// }
}

//Evaluation of Postfix Expression

#include<stdio.h>
int stack[20];
int top = -1;

void push(int x)
{
stack[++top] = x;
}
int pop()
{
if(top == -1)
return -1;
else
return stack[top--];
}

int main()
{
char exp[20];
char *e;
int n1,n2,n3,num;
printf("Enter the expression :: ");
scanf("%s",exp);
e = exp;
while(*e != '\0')
{
if(isdigit(*e))
{
num = *e - 48;
push(num);
}
else
{
n1 = pop();
n2 = pop();
switch(*e)
{
case '+':
{
n3 = n1 + n2;
break;
}
case '-':
{
n3 = n2 - n1;
break;
}
case '*':
{
n3 = n1 * n2;
break;
}
case '/':
{
 n3 = n2 / n1;
break;
}
}
push(n3);
}
e++;
}
printf("\nThe result of expression %s = %d\n\n",exp,pop());
return 0;
}

\\Implementation of Queue using ARRAY Menu Driven Program

#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

#define MAX 5

void main ()

int queue[MAX], ch , front = -1, rear = -1, i, num ;

printf ("QUEUE USING ARRAY");

printf ("\n1:INSERTION\n2:DELETION\n3:DISPLAY\n4:EXIT\n");

while (1)

printf ("Enter the choice:");

scanf ("%d",&ch);

switch (ch)

case 1 :
 if (rear == MAX -1)

printf ("\n Queue is full ");

else

if (front == -1)

front = 0 ;

printf ("Enter the number you want\t");

scanf ("%d",&num);

rear = rear + 1 ;

queue[rear] = num ;

break ;

case 2 :

if (front == -1)

printf ("\nqueue is empty");

else

printf("Deleted item is %d\n", queue[front++]);

}
 break ;

case 3 :

printf ("Queue elements are :");

if (front == -1 )

printf("\nQueue is empty");

else

for (i=front; i<=rear; i++)

printf("\n%d",queue[i]);

printf ("\n");

break ;

case 4 :

exit (0);

default :

printf("\nInvalid choice : Please enter the correct choice\n");

}
 }

\\Implementation of Circular Queue using Array Menudriven

#include<stdio.h>
# define MAX 5
int cqueue_arr[MAX];
int front = -1;
int rear = -1;
void insert(int item)
{
if((front == 0 && rear == MAX-1) || (front == rear+1))
{
printf("Queue Overflow n");
return;
}
if(front == -1)
{
front = 0;
rear = 0;
}
else
{
if(rear == MAX-1)
rear = 0;
else
rear = rear+1;
}
cqueue_arr[rear] = item ;
}
void deletion()
{
if(front == -1)
{
printf("Queue Underflown");
return ;
}
printf("Element deleted from queue is : %dn",cqueue_arr[front]);
if(front == rear)
{
front = -1;
rear=-1;
}
else
{
if(front == MAX-1)
front = 0;
else
front = front+1;
}
}
void display()
{
int front_pos = front,rear_pos = rear;
if(front == -1)
{
printf("Queue is emptyn");
return;
}
printf("Queue elements :n");
if( front_pos <= rear_pos )
while(front_pos <= rear_pos)
{
printf("%d ",cqueue_arr[front_pos]);
front_pos++;
}
else
{
while(front_pos <= MAX-1)
{
printf("%d ",cqueue_arr[front_pos]);
front_pos++;
}
front_pos = 0;
while(front_pos <= rear_pos)
{
printf("%d ",cqueue_arr[front_pos]);
front_pos++;
}
}
printf("n");
}
int main()
{
int choice,item;
do
{
printf("[Link]");
printf("[Link]");
printf("[Link]");
printf("[Link]");
printf("Enter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1 :
printf("Input the element for insertion in queue : ");
scanf("%d", &item);
insert(item);
break;
case 2 :
deletion();
break;
case 3:
display();
break;
case 4:
break;
default:
printf("Wrong choicen");
}
}while(choice!=4);
return 0;
}

\\Create a linked List using for loop

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<malloc.h>
void main()
{
struct node
{
int data;
struct node *next;
 };
struct node *head,*newnode,*temp;
int n,i;
head=0;
printf("\nEnter total no of nodes");
scanf("%d",&n);
for(i=0;i<n;i++)
{
newnode=(struct node*)malloc(sizeof(struct node));
printf("\n enter new node");
scanf("%d",&newnode->data);
newnode->next=0;
if(head==0)
{
head=temp=newnode;
}
else
{
temp->next=newnode;
temp=newnode;
}
//printf("\nDo u want to continue(0/1))");
//scanf("%d",&choice);
}
temp=head;
while(temp!=0)
{
printf("%d\t",temp->data);
temp=temp->next;
}
getch();
}

\\Create linked list using while loop

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<malloc.h>
void main()
{
struct node
{
int data;
struct node *next;
};
 struct node *head,*newnode,*temp;
int choice=1;
head=0;
while(choice)
{
newnode=(struct node*)malloc(sizeof(struct node));
printf("\n enter new node");
scanf("%d",&newnode->data);
newnode->next=0;
if(head==0)
{
head=temp=newnode;
}
else
{
temp->next=newnode;
temp=newnode;
}
printf("\nDo u want to continue(0/1))");
scanf("%d",&choice);
}
temp=head;
while(temp!=0)
{
printf("%d",temp->data);
temp=temp->next;
}
getch();
}

//Program to implement Singly Linked List ADT

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<malloc.h>
struct node
{
int data ;
struct node *next ;
}*head ;

void createList (int n) ;

void insert_after_pos () ;
void insert_before_pos (int) ;
void insert_at_pos(int);
void displayList ();
void insertBeginning ();
void insertEnd (int data) ;
void delete_beginning () ;
void delete_end () ;
void delete_from_pos ();
void delete_before_pos ();
void delete_after_pos ();
void reverse ();
int count=0 ;
void search_element();

int main ()
{
int n ,pos,data,i,choice;
printf ("\nEnter the number of the nodes:\t");
scanf ("%d",&n);
for (i=0;i<=n;i++)
{
count++ ;
}
createList(n);
printf ("\nList is :");
displayList();
printf("\n 1: Enter Beginning\t 2: Enter End\t 3: Enter after position\t 4: Enter Before
Position\t 5: Enter at position");
printf("\n 6: Delete Beginning\t 7: Delete End\t 8: Delete after position\t 9: Delete Before
Position\t 10: Delete at position");
printf("\n 11: Reverse List\t 12: Search number from List");
while(1)
{
printf("\nEnter Your Choice");
scanf("%d",&choice);

switch(choice)
{
case 1:
insertBeginning () ;
printf ("\nList after inserting the begginning :");
displayList();
break;

case 2:
printf ("\nEnter the new node at end");
scanf ("%d",&data);
insertEnd (data);
printf ("\nList after entering at end:");
displayList();
break;

case 3:
insert_after_pos ();
printf ("\nThe new list after entering after given position");
displayList();
break;

case 4:
printf ("\nEnter the pos for entering before");
scanf ("%d",&pos);
insert_before_pos (pos) ;
printf ("\nThe new list after entering before given position");
displayList();
break;

case 5:
printf ("\nEnter the pos for entering at position");
scanf ("%d",&pos);
insert_at_pos (pos) ;
printf ("\nThe new list after entering the element at given position");
displayList();
break;

case 6:
delete_beginning ();
printf ("\nList after deleting at beginning :");
displayList();
break;

case 7:
delete_end ();
printf ("\nList after deleting at end :");
displayList();
break;

case 8:
delete_after_pos ();
printf ("\nList afetr deleting node after the given position :");
displayList();
break;
 case 9:
delete_before_pos ();
printf ("\nList afetr deleting node before the given position :");
displayList();
break;

case 10:
delete_from_pos ();
printf ("\nList afetr deleting node at the given position :");
displayList();
break;

case 11:
reverse();
printf ("\nReversed list is :");
displayList();
break;

case 12:
search_element();
break;

case 13:
exit(0);

default:
printf("\n Wrong Choice");
}

}
void createList (int n)
{
struct node *newnode , *temp ;
int i ;
head = 0 ;

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

{
newnode = (struct node*)malloc(sizeof(struct node));
printf ("\nEnter the new node:");
scanf ("%d",&newnode->data);
newnode->next = 0 ;
if (head == 0)
 {
head = temp = newnode ;
temp = newnode ;
}
else
{
temp->next = newnode ;
temp = newnode ;
}
}
}
void displayList()
{
struct node *temp ;
int count = 0 ;
if (head == NULL)
{
printf("\nList is empty");
}
else
{
temp = head ;
while (temp != NULL)
{
printf("\n%d",temp->data);
printf("\tStored at %u",temp);
temp = temp->next ;
count++ ;

}
printf("\n");
printf("\nCOUNT IS %d",count);

}
}
void insertBeginning ()
{
struct node *temp ;
temp = (struct node*)malloc(sizeof(struct node));
printf ("\nEnter the data at the beginning of the list :");
scanf ("\n%d",&temp->data);
temp->next = head ;
head = temp ;
}
void insertEnd(int data)
{
struct node *newNode, *temp;
newNode = (struct node*)malloc(sizeof(struct node)); //Allocating memory to the node
newNode->data=data;
newNode->next = NULL;
temp = head;
// Traverse to the end of the list
while(temp->next != NULL)
temp = temp->next;
temp->next = newNode; // newNode is made as the last node
}

void insert_after_pos ()
{
int i=1,pos;
struct node *temp,*newnode;
newnode = (struct node*)malloc(sizeof(struct node));
printf ("\nEnter the position after which the new node to be inserted");
scanf("\n%d",&pos) ;
if (pos>count)
{
printf("\nInvalid position");
}
else
{
temp = head ;

while (i < pos)

{
temp = temp->next ;
i++ ;
}
printf ("\nEnter data to insert after position %d of the list :",pos);
scanf("%d",&newnode->data);
newnode->next = temp->next ;
temp->next = newnode ;
}
}

void insert_before_pos (int pos)

{
int i=1;
struct node *temp,*newnode,*prevnode;
newnode = (struct node*)malloc(sizeof(struct node));
//printf ("\nEnter the position after which the new node to be inserted");
 //scanf("\n%d",&pos) ;
if (pos>count)
{
printf("\nInvalid position");
}
else
{
temp = head ;

while (i < pos)

{
prevnode=temp;
temp = temp->next ;
i++ ;
}
printf ("\nEnter data to insert before position %d of the list :",pos);
scanf("%d",&newnode->data);
newnode->next=temp;
prevnode->next=newnode;
// newnode->next = temp->next ;
//temp->next = newnode ;
}
}

void insert_at_pos (int pos)

{
int i=1;
struct node *temp,*newnode,*prevnode;
newnode = (struct node*)malloc(sizeof(struct node));
//printf ("\nEnter the position after which the new node to be inserted");
//scanf("\n%d",&pos) ;
if (pos>count)
{
printf("\nInvalid position");
}
else
{
temp = head ;

while (i < pos)

{
prevnode=temp;
temp = temp->next ;
i++ ;
 }
printf ("\nEnter data to insert at position %d of the list :",pos);
scanf("%d",&newnode->data);
newnode->next=temp;
prevnode->next=newnode;
// newnode->next = temp->next ;
//temp->next = newnode ;
}
}

void delete_beginning ()
{
struct node *temp;
temp=head;
head=head->next;
free(temp);
}

void delete_end ()
{
struct node *temp,*prevnode;
temp=head;
while(temp->next!=0)
{
prevnode=temp;
temp=temp->next;
}
if(temp==head)
{
head=0;
}
else
{
prevnode->next=0;
}
free(temp);
}

void delete_from_pos ()
{
int i=1,pos;
struct node *temp,*nextnode;
temp = head ; //bringing temp at starting
printf("\nEnter position for deleting element at given position");
scanf("\n%d",&pos);
 if (pos > count)
{
printf ("\nInvalid position");
}
else
{
while(i<pos-1)
{
temp=temp->next;
i++;
}
nextnode=temp->next;
temp->next=nextnode->next;
free(nextnode);
}
}

void delete_after_pos ()
{
int i=1,pos;
struct node *temp,*deletednode;
temp = head ; //bringing temp at starting
printf("\nEnter position for deleting after position element");
scanf("\n%d",&pos);
if (pos > count)
{
printf ("\nInvalid position");
}
else
{
while(i<pos)
{
temp=temp->next;
i++;
}
deletednode=temp->next;
temp->next=deletednode->next;
free(deletednode);
}
}

void delete_before_pos ()
{
int i=1,pos;
struct node *temp,*prevnode;
temp = head ; //bringing temp at starting
 printf("\nEnter position for deleting before position element");
scanf("\n%d",&pos);
if (pos > count)
{
printf ("\nInvalid position");
}
else
{
while(i<pos-1)
{
prevnode=temp;
temp=temp->next;
i++;
}
prevnode->next=temp->next;
free(temp);
}
}
void reverse ()
{
struct node *current,*prev,*nextnode;
prev=0;
current=nextnode=head;
while(nextnode!=0)
{
nextnode=nextnode->next;
current->next=prev;
prev=current;
current=nextnode;
}
head=prev;
}

void search_element()
{
int data,i=1;
struct node* temp;
printf("\nEnter data to search");
scanf("\n%d",&data);
temp = head;
while(temp != NULL) // Start traversing from head node
{
if(temp -> data == data)
{
printf("\nElement found at position %d",i);
break;
}
else
{
i=i+1;
temp = temp -> next;
}
}
if(temp==0)
printf("\n Element %d is not found in the list\n",data);
}

//Program to implement Circular Linked List ADT

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<malloc.h>
struct node
{
int data ;
struct node *next ;
}*head, *tail;

void createList (int n) ;

void insert_after_pos () ;
void insert_before_pos (int) ;
void insert_at_pos(int);
void displayList();
void insertBeginning();
void insertEnd() ;
void delete_beginning() ;
void delete_end() ;
void delete_from_pos();
void delete_before_pos();
void delete_after_pos();
void countEvenOdd();
int count=0 ;
void search_element();

int main ()
{
int n ,pos,data,i,choice;
printf ("\nEnter the number of the nodes:\t");
scanf ("%d",&n);
for (i=0;i<=n;i++)
 {
count++ ;
}
createList(n);
printf ("\nList is :");
displayList();
printf("\n 1: Enter Beginning\t 2: Enter End\t 3: Enter after position\t 4: Enter Before
Position\t 5: Enter at position");
printf("\n 6: Delete Beginning\t 7: Delete End\t 8: Delete after position\t 9: Delete Before
Position\t 10: Delete at position");
printf("\n 11: Even Odd\t 12: Search number from List");
while(1)
{
printf("\nEnter Your Choice");
scanf("%d",&choice);

switch(choice)
{
case 1:
insertBeginning () ;
printf ("\nList after inserting the begginning :");
displayList();
break;

case 2:
insertEnd ();
printf ("\nList after entering at end:");
displayList();
break;

case 3:
insert_after_pos ();
printf ("\nThe new list after entering after given position");
displayList();
break;

case 4:
printf ("\nEnter the pos for entering before");
scanf ("%d",&pos);
insert_before_pos (pos) ;
printf ("\nThe new list after entering before given position");
displayList();
break;

case 5:
printf ("\nEnter the pos for entering at position");
scanf ("%d",&pos);
insert_at_pos (pos) ;
printf ("\nThe new list after entering the element at given position");
displayList();
break;

case 6:
delete_beginning ();
printf ("\nList after deleting at beginning :");
displayList();
break;

case 7:
delete_end();
printf ("\nList after deleting at end :");
displayList();
break;

case 8:
delete_after_pos();
printf ("\nList afetr deleting node after the given position :");
displayList();
break;

case 9:
delete_before_pos();
printf ("\nList afetr deleting node before the given position :");
displayList();
break;

case 10:
delete_from_pos();
printf ("\nList afetr deleting node at the given position :");
displayList();
break;

case 11:
countEvenOdd();
//printf ("\nReversed list is :");
// displayList();
break;

case 12:
search_element();
break;
 case 13:
exit(0);

default:
printf("\n Wrong Choice");
}

}
void createList(int n)
{
struct node *newnode;
int i;
head=0;

for(i=0;i<n;i++)
{
newnode=(struct node*)malloc(sizeof(struct node));
printf("\nEnter new node");
scanf("%d",&newnode->data);
newnode->next=0;
if(head==0)
{
head=tail=newnode;
tail->next=head;
}
else
{
tail->next=newnode;
tail=newnode;
tail->next=head;
}

void displayList()
{
struct node *temp;
if(head == NULL)
 {
printf("\nList is empty.");
}
else
{
temp = head;
while(temp -> next != head)
{
printf("%d\t", temp->data);
temp = temp->next;
}
printf("%d\t", temp->data);
}
printf("Circular Print %d",tail->next->data);
}

void insertBeginning()
{
struct node *newNode ;
newNode = (struct node*)malloc(sizeof(struct node));
printf ("\nEnter the data at the beginning of the list :");
scanf ("\n%d",&newNode->data);
newNode->next = head ;
head = newNode ;
tail->next=head;
}

void insertEnd()
{
//Create new node
struct node *newNode, *temp;
newNode = (struct node*)malloc(sizeof(struct node));
printf("\n Enter data to insert at end\n");
scanf("%d",&newNode->data);
tail->next=newNode;
tail=newNode;
tail->next=head;
}

void insert_after_pos()
{
int i=1,pos;
struct node *temp,*newnode;
 newnode = (struct node*)malloc(sizeof(struct node));
printf ("\nEnter the position after which the new node to be inserted");
scanf("\n%d",&pos) ;
if (pos>count)
{
printf("\nInvalid position");
}
else
{
temp = head ;

while (i < pos)

{
temp = temp->next ;
i++ ;
}
printf ("\nEnter data to insert after position %d of the list :",pos);
scanf("%d",&newnode->data);
newnode->next = temp->next ;
temp->next = newnode ;
tail->next=head;
}
}

void insert_before_pos(int pos)

{
int i=1;
struct node *temp,*newnode,*prevnode;
newnode = (struct node*)malloc(sizeof(struct node));
//printf ("\nEnter the position after which the new node to be inserted");
//scanf("\n%d",&pos) ;
if (pos>count)
{
printf("\nInvalid position");
}
else
{
temp = head ;

while (i < pos-1)

{
temp = temp->next ;
i++ ;
}
 printf ("\nEnter data to insert after position %d of the list :",pos);
scanf("%d",&newnode->data);
newnode->next = temp->next ;
temp->next = newnode ;
tail->next=head;
}
}

void insert_at_pos(int pos)

{
int i=1;
struct node *temp,*newnode,*prevnode;
newnode = (struct node*)malloc(sizeof(struct node));
//printf ("\nEnter the position after which the new node to be inserted");
//scanf("\n%d",&pos) ;
if (pos>count)
{
printf("\nInvalid position");
}
else
{
temp = head ;

while (i < pos-1)

{
temp = temp->next ;
i++ ;
}
printf ("\nEnter data to insert at position %d of the list :",pos);
scanf("%d",&newnode->data);
newnode->next = temp->next ;
temp->next = newnode ;
tail->next=head;
}
}

void delete_beginning()
{
struct node *temp;
temp=head;
head=head->next;
free(temp);
tail->next=head;
}
void delete_end()
{
struct node *temp,*prev;
temp=head;
while(temp -> next != head)
{
prev = temp;
temp = temp -> next;
}

free(temp);
tail=prev;
tail -> next = head;
}

void delete_from_pos()
{
int i=1,pos;
struct node *temp,*nextnode;
temp = head ; //bringing temp at starting
printf("\nEnter position for deleting element at given position");
scanf("\n%d",&pos);
if (pos==1)
{
delete_beginning();
}
else
{
while(i<pos-1)
{
temp=temp->next;
i++;
}
nextnode=temp->next;
temp->next=nextnode->next;
free(nextnode);

}
}

void delete_after_pos()
{
int i=1,pos;
struct node *temp,*deletednode;
temp = head ; //bringing temp at starting
 printf("\nEnter position for deleting after position element");
scanf("\n%d",&pos);
if (pos > count)
{
printf ("\nInvalid position");
}
else
{
while(i<pos)
{
temp=temp->next;
i++;
}
deletednode=temp->next;
temp->next=deletednode->next;
free(deletednode);
}
}

void delete_before_pos ()
{
int i=1,pos;
struct node *temp,*prevnode;
temp = head ; //bringing temp at starting
printf("\nEnter position for deleting before position element");
scanf("\n%d",&pos);
if (pos > count)
{
printf ("\nInvalid position");
}
else
{
while(i<pos-1)
{
prevnode=temp;
temp=temp->next;
i++;
}
prevnode->next=temp->next;
free(temp);
}
}

void search_element()
{
 int data,i=1;
struct node* temp;
printf("\nEnter data to search");
scanf("\n%d",&data);
temp = head;
while(temp != NULL) // Start traversing from head node
{
if(temp -> data == data)
{
printf("\nElement found at position %d",i);
break;
}
else
{
i=i+1;
temp = temp -> next;
}
}
if(temp==0)
printf("\n Element %d is not found in the list\n",data);
}

void countEvenOdd()
{
struct node *temp;
int count=0,evencount=0,oddcount=0;
temp = head ;
while (temp->next!= head)
{
if(temp->data%2==0)
{
printf("\n%d is Even Number",temp->data);
printf("\tStored at %u",temp);
evencount++;
}
else
{
printf("\n%d is Odd Number",temp->data);
printf("\tStored at %u",temp);
oddcount++;
}
temp = temp->next ;
count++ ;

}
if(temp->data%2==0)
 {
printf("\n%d is Even Number",temp->data);
printf("\tStored at %u",temp);
evencount++;
}
else
{
printf("\n%d is Odd Number",temp->data);
printf("\tStored at %u",temp);
oddcount++;
}
count++;
printf("\n");
printf("\nEven COUNT IS %d",evencount);
printf("\nOdd COUNT IS %d",oddcount);
printf("\nCOUNT IS %d",count);

//Program to implement Doubly Linked List ADT

#include<stdio.h>
#include<conio.h>
#include<malloc.h>
#include<stdlib.h>

struct node
{
struct node *prev ;
int data ;
struct node *next ;
};
struct node *head , *tail ;
static int count ;
void createList (int n) ;
void display() ;
void insert_at_beginning () ;
void insert_at_end () ;
void insert_after_pos () ;
void insert_before_pos(); //Or insert at position
void delete_beginning () ;
void delete_end () ;
void delete_from_pos () ;
void reverse_list();
void search_element();
int main ()
{
int n,i ;
printf("\nCreating the list");
printf("\nEnter the total no of nodes\t") ;
scanf("\n%d",&n) ;
for (i=0;i<=n;i++)
{
count++ ;
}
createList (n) ;

printf ("\nThe list is :") ;

display() ;

insert_at_beginning () ;
printf ("\nThe list is :") ;
display() ;

insert_at_end () ;
printf ("\nThe list is :") ;
display() ;

insert_after_pos () ;
printf ("\nThe list is :") ;
display() ;

insert_before_pos () ;
printf ("\nThe list is :") ;
display() ;

delete_beginning () ;
printf ("\nThe list after deleting from beginning :") ;
display() ;

delete_end () ;
printf ("\nThe list after deleting from the end :") ;
display() ;

delete_from_pos () ;
printf ("\nThe list after deleted at given position :") ;
display() ;
 reverse_list();
display();

search_element();

}
void createList(int n)
{
struct node *newnode ;

int i ;
head = 0 ;
for (i=1; i<=n ;i++)
{
newnode = (struct node*)malloc(sizeof(struct node));
printf ("\nEnter the new node ") ;
scanf("\n%d",&newnode->data) ;
newnode->next = 0 ;
newnode->prev = 0 ;
if (head == 0)
{
head = tail = newnode ;
}
else
{
tail->next = newnode ;
newnode->prev = tail ;
tail = newnode ;
}
}
}
void display()
{
struct node *temp ;
int count = 0 ;
if (head == NULL)
{
printf("\nList is empty");
}
else
{
temp = head ;
while (temp != NULL)
{
printf("\n%d",temp->data);
temp = temp->next ;
 count++ ;

}
printf("\n");
printf("\nCOUNT IS %d",count);

}
}
void insert_at_beginning ()
{
struct node *newnode = (struct node*)malloc(sizeof(struct node)) ;
printf("\nInsert the data to insert at the beginning of the list :") ;
scanf("\n%d",&newnode->data) ;

newnode->prev = 0 ;
head->prev = newnode ;
newnode->next = head ;
head = newnode ;
//Newnode is now the front node i.e. head node

}
void insert_at_end ()
{
struct node *newnode = (struct node*)malloc(sizeof(struct node));
printf("\nEnter data at the end : ") ;
scanf ("\n%d",&newnode->data) ;
newnode->next = 0 ;
newnode->prev = 0 ;
tail->next = newnode ;
newnode->prev = tail ; //prev of newnode becaomes the value of tail
tail = newnode ; //Tail is at now last position
}
void insert_after_pos ()
{
struct node *newnode , *temp ;
int i=1, pos ;
printf ("\nEnter the position after which the newnode to be inserted :") ;
scanf("\n%d",&pos) ;
//printf("Count=%d",count);
if (pos > count)
{
printf ("\nInavalid position entered please enter valid position ") ;
}

else
 {
temp = head ;
newnode = (struct node*)malloc(sizeof(struct node)) ; //allocationg the memory location
printf ("\nInsert the data at given position");
scanf("%d",&newnode->data) ;
newnode->next = 0 ;
newnode->prev = 0 ;
while (i < pos)
{
temp = temp->next ;
i++ ;
}
newnode->next = temp->next ;
temp->next->prev=newnode;
newnode->prev = temp ;
temp->next = newnode ;

}
void insert_before_pos () //Or at position
{
struct node *newnode , *temp ;
int i=1, pos ;
newnode = (struct node*)malloc(sizeof(struct node));
printf ("\nEnter the position before which the newnode to be inserted :") ;
scanf("\n%d",&pos) ;
if (pos > count)
{
printf ("\nInavalid position entered please enter valid position ") ;
}
else
{
if (pos == 1 )
{
insert_at_beginning () ;
}

else
{
temp = head ;

printf ("\nInsert data before position");

scanf("%d",&newnode->data) ;
newnode->next = 0 ;
newnode->prev = 0 ;
 while (i < pos-1)
{
temp = temp->next ;
i++ ;
}
newnode->next = temp->next ;
newnode->prev = temp ;
temp->next = newnode ;
newnode->next->prev = newnode ;
printf("\nNode inserted") ;
}
}
}
void delete_beginning ()
{
struct node *temp ;
temp = head ;
head = head->next ; //link between head and second node
head->prev = 0 ;
free(temp) ; //release memory
}
void delete_end ()
{
struct node *temp ;
temp = tail ; //bringing temp at end
tail = tail->prev ;
tail->next = 0 ;
free(temp) ; //release memory
}
void delete_from_pos ()
{
struct node *temp ;
int pos , i=1 ;
temp = head ; //get temp at the starting
printf("\nEnter the position to delete the elelment from the list :") ;
scanf("\n%d",&pos);
if (pos>count)
{
printf("\nInvalid Position Entered") ;
}
else
{
while (i<pos)
{
temp = temp->next ;
i++ ;
 }
temp->prev->next = temp->next ;
temp->next->prev = temp->prev ;
free(temp) ;

}
void reverse_list()
{
//Creating temporary node
struct node *temp;
struct node *current;
current=head;
/* swapping next and previous pointers until all nodes are reversed */
while (current!= NULL)
{ //swapping
temp= current->prev;
current->prev = current->next;
current->next = temp;
current= current->prev;
}
if(temp!= NULL ) //update head_ptr
head= temp->prev;
}

void search_element()
{
int data,i=1;
struct node* temp;
printf("\nEnter data to search");
scanf("\n%d",&data);
temp = head;
while(temp != NULL) // Start traversing from head node
{
if(temp -> data == data)
{
printf("\nElement found at position %d",i);
break;
}
else
{
i=i+1;
temp = temp -> next;
}
}
if(temp==0)
printf("\n Element %d is not found in the list\n",data);
}

//Program To Implement Stack / Linear Queue ADT using Linked List.

1) Implement Queue using Linked List

#include<stdio.h>
#include<conio.h>
#include<malloc.h>
#include<stdlib.h>

struct node
{
int data;
struct node*next;
};
struct node *front=0,*rear=0;

void enqueue(int n);

void dequeue();
void display();

int main()
{
int i=1,select,item;
while(i)
{
printf("\nMainMenu");
printf("\n1:ENQUEUE");
printf("\n2:DEQUEUE");
printf("\n3:DISPLAY");
printf("\n4:EXIT");

printf("\nEnteryourchoice");
scanf("\n%d",&select);

switch(select)
{
case 1:
printf("\nEnter the data to insert in the Queue from rear:");
scanf("\n%d",&item);
enqueue(item);
break;
case 2:
printf("\nDeletingfromthefront:");
dequeue();
break;
case 3:
printf("\nThelistis:");
display();
break;
case 4:
exit(0);
break;
default:
printf("\nInvalid Choice");
break;
}
printf("\n Do u want to contineu, please enter 1 or 0\n");
scanf("%d", &i);
}
return 0;
}
void enqueue(int n)
{
struct node *newnode;
newnode=(struct node*)malloc(sizeof(struct node));
newnode->data=n;
newnode->next=0;
if(front==0&&rear==0)
{
front=rear=newnode;
}
else
{
rear->next=newnode;
rear=newnode;

}
void dequeue()
{
struct node *temp;
if(front==0&&rear==0)
{
printf("\nUnderflow");

}
else
{
temp=front;
printf("\nDeleted item is %d",front->data);
front=front->next;
free(temp);
}
}
void display()
{
struct node *temp;
temp=front;
if(front==NULL)
{
printf("\nUnderflow");
}
else
{
while(temp!=NULL)
{
printf("\t%d",temp->data);
temp=temp->next;
}
}
}

2) Implement Stack using SLL

#include<stdio.h>
#include<stdlib.h>

/* Structure to create a node with data and pointer */

struct Node
{
int data;
struct Node *next;
}*top = NULL; // Initially the list is empty

void push(int);
void pop();
void display();

int main()
{
int choice, value;
printf("\nIMPLEMENTING STACKS USING LINKED LISTS\n");
while(1){
printf("1. Push\n2. Pop\n3. Display\n4. Exit\n");
printf("\nEnter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1: printf("\nEnter the value to insert: ");
scanf("%d", &value);
push(value);
break;

case 2: pop();
break;

case 3: display();
break;

case 4: exit(0);
break;

default: printf("\nInvalid Choice\n");

}}}

void push(int value)

{
struct Node *newNode;
newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value; // get value for the node
if(top == NULL)
newNode->next = NULL;
else
newNode->next = top; // Make the node as TOP
top = newNode;
printf("Node is Inserted\n\n");
}

void pop()
{
if(top == NULL)
printf("\nEMPTY STACK\n");
else{
struct Node *temp = top;
printf("\nPopped Element : %d", temp->data);
printf("\n");
top = temp->next; // After popping, make the next node as TOP
free(temp);
}}

void display()
{
// Print the stack
if(top == NULL)
 printf("\nEMPTY STACK\n");
else
{
printf("The stack is \n");
struct Node *temp = top;
while(temp->next != NULL){
printf("%d--->",temp->data);
temp = temp -> next;
}
printf("%d--->NULL\n\n",temp->data);
}}

//Program to implement BFS and DFS

#include<stdlib.h>
#include<stdio.h>
int q[20],top=-1,front=-1,rear=-1,a[20][20],vis[20],stack[20];
int delete();
void add(int item);
void bfs(int s,int n);
void dfs(int s,int n);
void push(int item);
int pop();

void main()
{
int n,i,s,ch,j;
char c,dummy;
printf("ENTER THE NUMBER VERTICES" );
scanf("%d",&n);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("ENTER 1 IF %d HAS A NODE WITH %d ELSE 0 ",i,j);
scanf("%d",&a[i][j]);
}
}
printf("THE ADJACENCY MATRIX IS\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("%d",a[i][j]);
}
printf("\n");
}
while(1)
{
for(i=1;i<=n;i++)
vis[i]=0;
printf("\nMENU");
printf("\n1.B.F.S");
printf("\n2.D.F.S");
printf("\nENTER YOUR CHOICE");
scanf("%d",&ch);
printf("ENTER THE SOURCE VERTEX :");
scanf("%d",&s);

switch(ch)
{
case 1:bfs(s,n);
break;
case 2:
dfs(s,n);
break;
}
}
}//main exit

void bfs(int s,int n)

{
int p,i;
add(s);
vis[s]=1;
p=delete();
if(p!=0)
printf("%d ",p);
while(p!=0)
{
for(i=1;i<=n;i++)
{

if((a[p][i]!=0)&&(vis[i]==0))
{
add(i);
vis[i]=1;
}
}
p=delete();
if(p!=0)
printf("%d",p);
}
for(i=1;i<=n;i++)
if(vis[i]==0)
bfs(i,n);
}

void add(int item)

{
if(rear==19)
printf("QUEUE FULL");
else
{
if(rear==-1)
{
q[++rear]=item;
front++;
}
else
q[++rear]=item;
}
}

int delete()
{
int k;
if((front>rear)||(front==-1))
return(0);
else
{
k=q[front++];
return(k);
}
}

void dfs(int s,int n)

{
int i,k;
push(s);
vis[s]=1;
k=pop();
if(k!=0)
printf(" %d ",k);
while(k!=0)
{
for(i=1;i<=n;i++)
if((a[k][i]!=0)&&(vis[i]==0))
{
push(i);
vis[i]=1;
break;
}
k=pop();
if(k!=0)
printf("%d",k);
}
for(i=1;i<=n;i++)
if(vis[i]==0)
dfs(i,n);
}

void push(int item)

{
if(top==19)
printf("Stack overflow ");
else
stack[++top]=item;
}

int pop()
{
int k;
if(top==-1)
return(0);
else
{
k=stack[top--];
return(k);
}
}

//Implementation of Binary Tree

#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

typedef struct node

int data;

struct node *left;

struct node *right;

}node;

node *create()
{

node *p;

int x;

printf("Enter data(-1 for no data):");

scanf("%d",&x);

if(x==-1)

return NULL;

p=(node*)malloc(sizeof(node));

p->data=x;

printf("Enter left child of %d:\n",x);

p->left=create();

printf("Enter right child of %d:\n",x);

p->right=create();

return p;

void preorder(node *t) //address of root node is passed in t

if(t!=NULL)

printf("\n%d",t->data); //visit the root

 preorder(t->left); //preorder traversal on left subtree

preorder(t->right); //preorder traversal om right subtree

void inorder(node *t) //address of root node is passed in t

if(t!=NULL)

inorder(t->left);

printf("\n%d",t->data); //preorder traversal on left subtree

inorder(t->right); //preorder traversal om right subtree

void postorder(node *t) //address of root node is passed in t

if(t!=NULL)

postorder(t->left);

postorder(t->right);

printf("\n%d",t->data); //preorder traversal om right subtree

int main()

{
 node *root;

root=create();

printf("\nThe preorder traversal of tree is:\n");

preorder(root);

printf("\nThe Inorder traversal of tree is:\n");

inorder(root);

printf("\nThe Postorder traversal of tree is:\n");

postorder(root);

return 0;

//Implementation of BST
#include <stdio.h>

#include <stdlib.h>

struct node

int data; //node will store an integer

struct node *right_child; // right child

struct node *left_child; // left child

};

void search(int i, struct node *n) {

if (n == NULL)

printf("\nValue does not exist in tree!");

else if(n->data == i)

printf("\nValue found!");

else if(i > n->data)

search(i, n->right_child);
 else

search(i, n->left_child);

void mirror(struct node* node)

if (node==NULL)

return;

else

struct node* temp;

/* do the subtrees */

//mirror(node->left_child);

//mirror(node->right_child);

/* swap the pointers in this node */

temp = node->left_child;

node->left_child = node->right_child;

node->right_child = temp;

struct node* smallest(struct node *root)

while(root != NULL && root->left_child != NULL)

root = root->left_child;

//printf("\nSmallest value is %d\n", root->data);

 return root;

struct node* largest(struct node *root)

while (root != NULL && root->right_child != NULL)

root = root->right_child;

// printf("\nLargest value is %d", root->data);

return root;

//function to create a node

struct node* new_node(int x)

struct node *p;

p = malloc(sizeof(struct node));

p->data = x;

p->left_child = NULL;

p->right_child = NULL;

return p;

struct node* insert(struct node *root, int x)

//searching for the place to insert

if(root==NULL)

return new_node(x);

else if(x>root->data) // x is greater. Should be inserted to right

 root->right_child = insert(root->right_child, x);

else // x is smaller should be inserted to left

root->left_child = insert(root->left_child,x);

return root;

// funnction to delete a node

struct node* delete(struct node *root, int x)

//searching for the item to be deleted

if(root==NULL)

return NULL;

if (x>root->data)

root->right_child = delete(root->right_child, x);

else if(x<root->data)

root->left_child = delete(root->left_child, x);

else

//No Children

if(root->left_child==NULL && root->right_child==NULL)

free(root);

return NULL;

//One Child

else if(root->left_child==NULL || root->right_child==NULL)

{
 struct node *temp;

if(root->left_child==NULL)

temp = root->right_child;

else

temp = root->left_child;

free(root);

return temp;

//Two Children

else

struct node *temp = smallest(root->right_child);

root->data = temp->data;

root->right_child = delete(root->right_child, temp->data);

return root;

void inorder(struct node *root)

if(root!=NULL) // checking if the root is not null

inorder(root->left_child); // visiting left child

printf(" %d ", root->data); // printing data at root

inorder(root->right_child);// visiting right child

}
}

int main()

/*

20

/ \

/ \

5 30

/ \ /\

/ \ / \

1 15 25 40

/ \

/ \

9 45

/ \ /

/ \ /

7 12 42

*/

struct node *root,*min,*max;

int x;

//struct node *min;

root = new_node(20);

insert(root,5);

insert(root,1);

insert(root,15);

insert(root,9);

insert(root,7);
 insert(root,12);

insert(root,30);

insert(root,25);

insert(root,40);

insert(root, 45);

insert(root, 42);

inorder(root);

printf("\n");

root = delete(root, 1);

root = delete(root, 40);

root = delete(root, 45);

root = delete(root, 20);

inorder(root);

//postorder(root)

printf("\n");

min=smallest(root);

printf("\nSmallest value is %d\n", min->data);

max=largest(root);

printf("\nlargest value is %d\n", max->data);

printf("\n enetr element to search\n");

scanf("%d",&x);

search(x,root);

mirror(root);

inorder(root);

return 0;

}
//Program to apply Binary Search Algorithm on the given array (Iterative)
#include<stdio.h>

#include<conio.h>

int binary(int low,int high,int key,int a[100])

int mid,flag=0;

while(low<=high)

mid=(low+high)/2;

if(a[mid]==key)

flag=1;

return mid;

else if(key<a[mid])

flag=0; high=mid-1;

binary(low,high,key,a);

else

flag=0; low=mid+1;

binary(low,high,key,a);

if(flag==0) return-1;

void main()
{

int a[100],high,low,i,n,key,result;

//clrscr();

printf("\n How many array elements?=");

scanf("%d",&n);

printf("\n Enter array element in ascending order=");

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

scanf("%d",&a[i]);

printf("\n Enter the number that you have to search=");

scanf("%d",&key);

low=0;high=n-1;

result=binary(low,high,key,a);

if(result==-1)

printf("Element %d is not present",key);

else

printf("Element %d is at index=%d",key,result); getch();

// Program to apply Binary Search Algorithm on the given array (Recursive)

#include<stdio.h>

#include<stdlib.h>

#define size 10

int binsearch(int[], int, int, int);

int main() {

int num, i, key, position;

int low, high, list[size];

 printf("\nEnter the total number of elements");

scanf("%d", &num);

printf("\nEnter the elements of list :")

for (i = 0; i < num; i++) {

scanf("%d", &list[i]);

low = 0;

high = num - 1;

printf("\nEnter element to be searched : ");

scanf("%d", &key);

position = binsearch(list, key, low, high);

if (position != -1) {

printf("\nNumber present at %d", (position + 1));

} else

printf("\n The number is not present in the list");

return (0);

// Binary search function for binary search

int binsearch(int a[], int x, int low, int high) {

int mid;

if (low > high)

return -1;

mid = (low + high) / 2;

if (x == a[mid]) {

return (mid);

} else if (x < a[mid]) {

 binsearch(a, x, low, mid - 1);

} else {

binsearch(a, x, mid + 1, high);