Monday, April 19, 2010

Data Strutcher Programs(stack &amd; queue)

/* Program of circular queue using array*/
# include<stdio.h>
computer science tutorial
seminar topic
newidea
computer science engineering
power of computer
magic of computer
computerinformation
# define MAX 5

int cqueue_arr[MAX];
int front = -1;
int rear = -1;

main()
{
int choice;
while(1)
{
printf("1.Insert\n");
printf("2.Delete\n");
printf("3.Display\n");
printf("4.Quit\n");
printf("Enter your choice : ");
scanf("%d",&choice);

switch(choice)
{
case 1 :
insert();
break;
case 2 :
del();
break;
case 3:
display();
break;
case 4:
exit(1);
default:
printf("Wrong choice\n");
}/*End of switch*/
}
/*End of while */
}/*End of main()*/

insert()
{
int added_item;
if((front == 0 && rear == MAX-1) || (front == rear+1))
{
printf("Queue Overflow \n");
return;
}
if (front == -1) /*If queue is empty */
{
front = 0;
rear = 0;
}
else
if(rear == MAX-1)/*rear is at last position of queue */
rear = 0;
else
rear = rear+1;
printf("Input the element for insertion in queue : ");
scanf("%d", &added_item);
cqueue_arr[rear] = added_item ;
}/*End of insert()*/

del()
{
if (front == -1)
{
printf("Queue Underflow\n");
return ;
}
printf("Element deleted from queue is : %d\n",cqueue_arr[front]);
if(front == rear) /* queue has only one element */
{
front = -1;
rear=-1;
}
else
if(front == MAX-1)
front = 0;
else
front = front+1;
}/*End of del() */

display()
{
int front_pos = front,rear_pos = rear;
if(front == -1)
{
printf("Queue is empty\n");
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++;
}/*End of else */
printf("\n");
}/*End of display() */

/* Program of input and output restricted dequeue using array*/
# include<stdio.h>
# define MAX 5

int deque_arr[MAX];
int left = -1;
int right = -1;

main()
{
int choice;

printf("1.Input restricted dequeue\n");
printf("2.Output restricted dequeue\n");
printf("Enter your choice : ");
scanf("%d",&choice);

switch(choice)
{
case 1 :
input_que();
break;
case 2:
output_que();
break;
default:
printf("Wrong choice\n");
}/*End of switch*/
}/*End of main()*/

input_que()
{
int choice;
while(1)
{
printf("1.Insert at right\n");
printf("2.Delete from left\n");
printf("3.Delete from right\n");
printf("4.Display\n");
printf("5.Quit\n");
printf("Enter your choice : ");
scanf("%d",&choice);

switch(choice)
{
case 1:
insert_right();
break;
case 2:
delete_left();
break;
case 3:
delete_right();
break;
case 4:
display_queue();
break;
case 5:
exit();
default:
printf("Wrong choice\n");
}
/*End of switch*/
}
}/*End of input_que() */

output_que()
{
int choice;
while(1)
{
printf("1.Insert at right\n");
printf("2.Insert at left\n");
printf("3.Delete from left\n");
printf("4.Display\n");
printf("5.Quit\n");
printf("Enter your choice : ");
scanf("%d",&choice);

switch(choice)
{
case 1:
insert_right();
break;
case 2:
insert_left();
break;
case 3:
delete_left();
break;
case 4:
display_queue();
break;
case 5:
exit();
default:
printf("Wrong choice\n");
}/*End of switch*/
}/*End of while*/
}/*End of output_que() */

insert_right()
{
int added_item;
if((left == 0 && right == MAX-1) || (left == right+1))
{
printf("Queue Overflow\n");
return;
}
if (left == -1) /* if queue is initially empty */
{
left = 0;
right = 0;
}
else
if(right == MAX-1) /*right is at last position of queue */
right = 0;
else
right = right+1;
printf("Input the element for adding in queue : ");
scanf("%d", &added_item);
deque_arr[right] = added_item ;
}/*End of insert_right()*/

insert_left()
{
int added_item;
if((left == 0 && right == MAX-1) || (left == right+1))
{
printf("Queue Overflow \n");
return;
}
if (left == -1)/*If queue is initially empty*/
{
left = 0;
right = 0;
}
else
if(left== 0)
left=MAX-1;
else
left=left-1;
printf("Input the element for adding in queue : ");
scanf("%d", &added_item);
deque_arr[left] = added_item ;
}/*End of insert_left()*/

delete_left()
{
if (left == -1)
{
printf("Queue Underflow\n");
return ;
}
printf("Element deleted from queue is : %d\n",deque_arr[left]);
if(left == right) /*Queue has only one element */
{
left = -1;
right=-1;
}
else
if(left == MAX-1)
left = 0;
else
left = left+1;
}/*End of delete_left()*/

delete_right()
{
if (left == -1)
{
printf("Queue Underflow\n");
return ;
}
printf("Element deleted from queue is : %d\n",deque_arr[right]);
if(left == right) /*queue has only one element*/
{
left = -1;
right=-1;
}
else
if(right == 0)
right=MAX-1;
else
right=right-1;
}/*End of delete_right() */

display_queue()
{
int front_pos = left,rear_pos = right;
if(left == -1)
{
printf("Queue is empty\n");
return;
}
printf("Queue elements :\n");
if( front_pos <= rear_pos )
{
while(front_pos <= rear_pos)
{
printf("%d ",deque_arr[front_pos]);
front_pos++;
}
}
else
{
while(front_pos <= MAX-1)
{
printf("%d ",deque_arr[front_pos]);
front_pos++;
}
front_pos = 0;
while(front_pos <= rear_pos)
{
printf("%d ",deque_arr[front_pos]);
front_pos++;
}
}/*End of else */
printf("\n");
}/*End of display_queue() */

/* Program to check nesting of parentheses using stack */
#include<stdio.h>
#define MAX 20
#define true 1
#define false 0
int top = -1;
int stack[MAX];

push(char);
char pop();

main()
{
char exp[MAX],temp;
int i,valid=true;
printf("Enter an algebraic expression : ");
gets(exp);

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 */
valid=false;
else
{
temp=pop();
if( exp[i]==')' && (temp=='{' || temp=='[') )
valid=false;
if( exp[i]=='}' && (temp=='(' || temp=='[') )
valid=false;
if( exp[i]==']' && (temp=='(' || temp=='{') )
valid=false;
}/*End of else */
}/*End of for*/
if(top>=0) /*stack not empty*/
valid=false;

if( valid==true )
printf("Valid expression\n");
else
printf("Invalid expression\n");
}/*End of main()*/

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

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

/* Program for conversion of infix to postfix and evaluation of postfix.
It will take only single digit in expression */
#include<stdio.h>
#include<string.h>
#include<math.h>
#define Blank ' '
#define Tab '\t'
#define MAX 50

long int pop ();
long int eval_post();
char infix[MAX], postfix[MAX];
long int stack[MAX];
int top;
main()
{
long int value;
char choice='y';
while(choice == 'y')
{
top = 0;
printf("Enter infix : ");
fflush(stdin);
gets(infix);
infix_to_postfix();
printf("Postfix : %s\n",postfix);
value=eval_post();
printf("Value of expression : %ld\n",value);
printf("Want to continue(y/n) : ");
scanf("%c",&choice);
}
}/*End of main()*/

infix_to_postfix()
{
int i,p=0,type,precedence,len;
char next ;

stack[top]='#';
len=strlen(infix);
infix[len]='#';
for(i=0; infix[i]!='#';i++)
{

if( !white_space(infix[i]))
{
switch(infix[i])
{
case '(':
push(infix[i]);
break;

case ')':
while((next = pop()) != '(')
postfix[p++] = next;

break;
case '+':
case '-':
case '*':
case '/':
case '%':
case '^':
precedence = prec(infix[i]);
while(stack[top]!='#' && precedence<= prec(stack[top]))
postfix[p++] = pop();
push(infix[i]);
break;
default: /*if an operand comes */
postfix[p++] = infix[i];
}/*End of switch */
}/*End of if */
}/*End of for */
while(stack[top]!='#')
postfix[p++] = pop();
postfix[p] = '' ; /*End postfix with'' to make it a string*/
}/*End of infix_to_postfix()*/


/* This function returns the precedence of the operator */
prec(char symbol )
{
switch(symbol)
{
case '(':
return 0;
case '+':
case '-':
return 1;
case '*':
case '/':
case '%':
return 2;
case '^':
return 3;
}/*End of switch*/
}/*End of prec()*/


push(long int symbol)
{
if(top > MAX)
{
printf("Stack overflow\n");
exit(1);
}
else
{
top=top+1;
stack[top] = symbol;
}
}/*End of push()*/

long int pop()
{
if (top == -1 )
{
printf("Stack underflow \n");
exit(2);
}
else
return (stack[top--]);
}/*End of pop()*/

white_space(char symbol)
{
if( symbol == Blank || symbol == Tab || symbol == '')
return 1;
else
return 0;
}/*End of white_space()*/

long int eval_post()
{
long int a,b,temp,result,len;
int i;
len=strlen(postfix);
postfix[len]='#';

for(i=0;postfix[i]!='#';i++)
{
if(postfix[i]<='9' && postfix[i]>='0')
push( postfix[i]-48 );
else
{
a=pop();
b=pop();

switch(postfix[i])
{
case '+':
temp=b+a; break;
case '-':
temp=b-a;break;
case '*':
temp=b*a;break;
case '/':
temp=b/a;break;
case '%':
temp=b%a;break;
case '^':
temp=pow(b,a);/*End of switch
} */
push(temp);
}/*End of else*/
}/*End of for */

result=pop();
return result;
}/*End of eval_post */

/* Program of priority queue using linked list*/
# include<stdio.h>
# include<malloc.h>

struct node
{
int priority;
int info;
struct node *link;
}*front = NULL;

main()
{
int choice;
while(1)
{
printf("1.Insert\n");
printf("2.Delete\n");
printf("3.Display\n");
printf("4.Quit\n");
printf("Enter your choice : ");
scanf("%d", &choice);

switch(choice)
{
case 1:
insert();
break;
case 2:
del();
break;
case 3:
display();
break;
case 4:
exit(1);
default :
printf("Wrong choice\n");
}/*End of switch*/
}/*End of while*/
}/*End of main()*/


insert()
{
struct node *tmp,*q;
int added_item,item_priority;
tmp = (struct node *)malloc(sizeof(struct node));
printf("Input the item value to be added in the queue : ");
scanf("%d",&added_item);
printf("Enter its priority : ");
scanf("%d",&item_priority);
tmp->info = added_item;
tmp->priority = item_priority;
/*Queue is empty or item to be added has priority more than first item*/
if( front == NULL || item_priority < front->priority )
{
tmp->link = front;
front = tmp;
}
else
{
q = front;
while( q->link != NULL && q->link->priority <= item_priority )
q=q->link;
tmp->link = q->link;
q->link = tmp;
}/*End of else*/
}/*End of insert()*/

del()
{
struct node *tmp;
if(front == NULL)
printf("Queue Underflow\n");
else
{
tmp = front;
printf("Deleted item is %d\n",tmp->info);
front = front->link;
free(tmp);
}
}/*End of del()*/

display()
{
struct node *ptr;
ptr = front;
if(front == NULL)
printf("Queue is empty\n");
else
{ printf("Queue is :\n");
printf("Priority Item\n");
while(ptr != NULL)
{
printf("%5d %5d\n",ptr->priority,ptr->info);
ptr = ptr->link;
}
}/*End of else */

/*End of display() */

/* Program of queue using circular linked list*/
# include <stdio.h>
# include <malloc.h>

struct node
{
int info;
struct node *link;
}*rear=NULL;

main()
{
int choice;
while(1)
{
printf("1.Insert \n");
printf("2.Delete \n");
printf("3.Display\n");
printf("4.Quit\n");
printf("Enter your choice : ");
scanf("%d",&choice);

switch(choice)
{
case 1:
insert();
break;
case 2:
del();
break;
case 3:
display();
break;
case 4:
exit();
default:
printf("Wrong choice\n");
}/*End of switch*/
}/*End of while*/
}/*End of main()*/


insert()
{
int num;
struct node *q,*tmp;
printf("Enter the element for insertion : ");
scanf("%d",&num);
tmp= malloc(sizeof(struct node));
tmp->info = num;

if(rear == NULL) /*If queue is empty */
{
rear = tmp;
tmp->link = rear;
}
else
{
tmp->link = rear->link;
rear->link = tmp;
rear = tmp;
}
}/*End of insert()*/

del()
{
struct node *tmp,*q;
if(rear==NULL)
{
printf("Queue underflow\n");
return;
}
if( rear->link == rear ) /*If only one element*/
{
tmp = rear;
rear = NULL;
free(tmp);
return;
}
q=rear->link;
tmp=q;
rear->link = q->link;
printf("Deleted element is %d\n",tmp->info);
free(tmp);
}/*End of del()*/

display()
{
struct node *q;
if(rear == NULL)
{
printf("Queue is empty\n");
return;
}
q = rear->link;
printf("Queue is :\n");
while(q != rear)
{
printf("%d ", q->info);
q = q->link;
}
printf("%d\n",rear->info);
}/*End of display()*/

/*Program of queue using array*/
# include<stdio.h>
# define MAX 5

int queue_arr[MAX];
int rear = -1;
int front = -1;

main()
{
int choice;
while(1)
{
printf("1.Insert\n");
printf("2.Delete\n");
printf("3.Display\n");
printf("4.Quit\n");
printf("Enter your choice : ");
scanf("%d",&choice);

switch(choice)
{
case 1 :
insert();
break;
case 2 :
del();
break;
case 3:
display();
break;
case 4:
exit(1);
default:
printf("Wrong choice\n");
}/*End of switch*/
}/*End of while*/
}/*End of main()*/


insert()
{
int added_item;
if (rear==MAX-1)
printf("Queue Overflow\n");
else
{
if (front==-1) /*If queue is initially empty */
front=0;
printf("Input the element for adding in queue : ");
scanf("%d", &added_item);
rear=rear+1;
queue_arr[rear] = added_item ;
}
}/*End of insert()*/

del()
{
if (front == -1 || front > rear)
{
printf("Queue Underflow\n");
return ;
}
else
{
printf("Element deleted from queue is : %d\n", queue_arr[front]);
front=front+1;
}
}/*End of del() */

display()
{
int i;
if (front == -1)
printf("Queue is empty\n");
else
{
printf("Queue is :\n");
for(i=front;i<= rear;i++)
printf("%d ",queue_arr[i]);
printf("\n");
}
}/*End of display() */

/* Program of reversing a string using stack */
#include<stdio.h>
#define MAX 20
#include<string.h>

int top = -1;
char stack[MAX];
char pop();
push(char);
main()
{
char str[20];
int i;
printf("Enter the string : " );
gets(str);
/*Push characters of the string str on the stack */
for(i=0;i<strlen(str);i++)
push(str[i]);
/*Pop characters from the stack and store in string str */
for(i=0;i<strlen(str);i++)
str[i]=pop();
printf("Reversed string is : ");
puts(str);
}/*End of main()*/

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

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


/* Program of sparse matrix for 3-tuple method using array*/
#include<stdio.h>
#define srow 50
#define mrow 20
#define mcolumn 20

main()
{
int mat[mrow][mcolumn],sparse[srow][3];
int i,j,nzero=0,mr,mc,sr,s;
printf("Enter number of rows : ");
scanf("%d",&mr);
printf("Enter number of columns : ");
scanf("%d",&mc);

for(i=0;i<mr;i++)
for(j=0;j<mc;j++)
{
printf("Enter element for row %d,column %d : ",i+1,j+1);
scanf("%d",&mat[i][j]);
}
printf("Entered matrix is : \n");
for(i=0;i<mr;i++)
{
for(j=0;j<mc;j++)
{
printf("%6d",mat[i][j]);
if(mat[i][j]!=0)
nzero++;
}
printf("\n");
}

sr=nzero+1;
sparse[0][0]=mr;
sparse[0][1]=mc;
sparse[0][2]=nzero;
s=1;

for(i=0;i<mr;i++)
for(j=0;j<mc;j++)
{
if(mat[i][j]!=0)
{
sparse[s][0]=i+1;
sparse[s][1]=j+1;
sparse[s][2]=mat [i][j];
s++;
}
}
printf("Sparse matrix is :\n");
for(i=0;i<sr;i++)
{
for(j=0;j<3;j++)
printf("%5d",sparse[i][j]);
printf("\n");
}
}/*End of main()*/

/* Program of stack using array*/
#include<stdio.h>
#define MAX 5

int top = -1;
int stack_arr[MAX];

main()
{
int choice;
while(1)
{
printf("1.Push\n");
printf("2.Pop\n");
printf("3.Display\n");
printf("4.Quit\n");
printf("Enter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1 :
push();
break;
case 2:
pop();
break;
case 3:
display();
break;
case 4:
exit(1);
default:
printf("Wrong choice\n");
}/*End of switch*/
}/*End of while*/
}/*End of main()*/


push()
{
int pushed_item;
if(top == (MAX-1))
printf("Stack Overflow\n");
else
{
printf("Enter the item to be pushed in stack : ");
scanf("%d",&pushed_item);
top=top+1;
stack_arr[top] = pushed_item;
}
}/*End of push()*/

pop()
{
if(top == -1)
printf("Stack Underflow\n");
else
{
printf("Popped element is : %d\n",stack_arr[top]);
top=top-1;
}
}/*End of pop()*/

display()
{
int i;
if(top == -1)
printf("Stack is empty\n");
else
{
printf("Stack elements :\n");
for(i = top; i >=0; i--)
printf("%d\n", stack_arr[i] );
}
}/*End of display()*/

/* Program of stack using linked list*/
# include<stdio.h>
# include<malloc.h>

struct node
{
int info;
struct node *link;
} *top=NULL;

main()
{
int choice;
while(1)
{ printf("1.Push\n");
printf("2.Pop\n");
printf("3.Display\n");
printf("4.Quit\n");
printf("Enter your choice : ") ;
scanf("%d", &choice);

switch(choice)
{
case 1:
push();
break;
case 2:
pop();
break;
case 3:
display();
break;
case 4:
exit(1);
default :
printf("Wrong choice\n");
}/*End of switch */
}/*End of while */
}/*End of main() */


push()
{
struct node *tmp;
int pushed_item;
tmp = (struct node *)malloc(sizeof(struct node));
printf("Input the new value to be pushed on the stack : ");
scanf("%d",&pushed_item);
tmp->info=pushed_item;
tmp->link=top;
top=tmp;
}/*End of push()*/

pop()
{
struct node *tmp;
if(top == NULL)
printf("Stack is empty\n");
else
{ tmp=top;
printf("Popped item is %d\n",tmp->info);
top=top->link;
free(tmp);
}

}/*End of pop()*/

display()
{ struct node *ptr;
ptr=top;
if(top==NULL)
printf("Stack is empty\n");
else
{
printf("Stack elements :\n");
while(ptr!= NULL)
{
printf("%d\n",ptr->info);
ptr = ptr->link;
}/*End of while */
}/*End of else*/
}/*End of display()*/

No comments:

Post a Comment