Program to implement a Linked Queue.
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
struct Node
{
int item;
struct Node *next;
};
typedef struct Node *Nodeptr;
struct Queue
{
Nodeptr front, rear;
};
int empty( struct Queue *q )
{
if( q->front == NULL )
return 1;
else
return 0;
}
Nodeptr getnode()
{
return( ( Nodeptr ) malloc( sizeof( struct Node ) ) );
}
void insert( struct Queue *q, int x )
{
Nodeptr temp;
temp = getnode();
if( temp == NULL )
{
printf("The memory is full.\n");
return;
}
temp->item = x;
temp->next = NULL;
if( q->rear == NULL )
q->front = temp;
else
(q->rear)->next = temp;
q->rear = temp;
}
int del( struct Queue *q )
{
Nodeptr temp;
int x;
if( empty( q ) )
{
printf("The queue is empty.\n");
return( -999 );
}
temp = q->front;
x = (q->front)->item;
q->front = (q->front)->next;
if( empty( q ) )
q->rear = NULL;
free( temp );
return( x );
}
void display( struct Queue *q )
{
Nodeptr temp;
if( empty( q ) )
{
printf("The queue is empty.\n");
}
else
{
temp = q->front;
while( temp != NULL )
{
printf("%d -> ",temp->item);
temp = temp->next;
}
printf("END\n");
}
}
void main()
{
struct Queue *q;
char c;
int x;
clrscr();
q->front = q->rear = NULL;
do
{
printf("\nMain Menu: "
"\n 1. Empty,"
"\n 2. Insert,"
"\n 3. Delete,"
"\n 4. Display,"
"\n 5. Exit."
"\nEnter your choice: ");
c = getche();
printf("\n");
switch( c )
{
case '1':
if( empty( q ) )
printf("The queue is empty.\n");
else
printf("The queue is not empty.\n");
break;
case '2':
printf("Enter item to insert: ");
scanf("%d",&x);
insert( q, x );
break;
case '3':
x = del( q );
if( x != -999 )
printf("The removed item: %d\n",x);
break;
case '4':
display( q );
break;
}
}
while( c != '5' );
}
...............................................................................................................................
Program to implement a Linked Stack.
#include <conio.h>
#include <stdlib.h>
struct Node
{
int item;
struct Node *next;
};
typedef struct Node *Nodeptr;
struct Stack
{
Nodeptr top;
};
int empty( struct Stack *s )
{
if( s->top == NULL )
return 1;
else
return 0;
}
Nodeptr getnode()
{
return( ( Nodeptr ) malloc( sizeof( struct Node ) ) );
}
void push( struct Stack *s, int x )
{
Nodeptr temp;
temp = getnode();
if( temp == NULL )
printf("The memory is full.\n");
else
{
temp->item = x;
temp->next = s->top;
s->top = temp;
}
}
int pop( struct Stack *s )
{
Nodeptr temp;
int x;
if( empty( s ) )
{
printf("The linked stack is empty.\n");
x = -999;
}
else
{
temp = s->top;
x = (s->top)->item;
s->top = (s->top)->next;
free( temp );
}
return( x );
}
void display( struct Stack *s )
{
Nodeptr temp;
if( empty( s ) )
{
printf("The stack is empty.\n");
return;
}
temp = s->top;
while( temp != NULL )
{
printf("%d -> ",temp->item );
temp = temp->next ;
}
printf("END.\n");
}
void main()
{
struct Stack *s;
char c;
int x;
clrscr();
s->top = NULL;
do
{
printf("\nMain Menu: "
"\n 1. Empty,"
"\n 2. Insert,"
"\n 3. Delete,"
"\n 4. Display,"
"\n 5. Exit."
"\nEnter your choice: ");
c = getche();
printf("\n");
switch( c )
{
case '1':
if( empty( s ) )
printf("The linked stack is empty.\n");
else
printf("The linked stack is not empty.\n");
break;
case '2':
printf("Enter item to insert: ");
scanf("%d",&x);
push( s, x );
break;
case '3':
x = pop( s );
if( x != -999 )
printf("The popped item: %d\n",x);
break;
case '4':
printf("The linked stack: ");
display( s );
break;
}
}
while( c != '5' );
}
....................................................................................................................................
/* Write a C program to evaluate a postfix expression. */
#include <stdio.h>
#include <conio.h>
#include <math.h>
#define STACKSIZE 20
struct Stack
{
int item[STACKSIZE];
int top;
};
int empty( struct Stack *s )
{
if( s->top == -1 )
return( 1 );
else
return( 0 );
}
void push( struct Stack *s, int x )
{
if( s->top == STACKSIZE - 1 )
{
printf("\nThe stack is full.");
getch();
exit( 0 );
}
else
s->item[ ++s->top ] = x;
}
int pop( struct Stack *s )
{
if( empty( s ) )
{
printf("\nThe stack is empty.");
getch();
exit( 0 );
}
return( s->item[ s->top-- ] );
}
int result( char postfix[] )
{
struct Stack *s;
char x;
int a, b, i, value;
s = ( struct Stack * ) malloc( sizeof( struct Stack ) );
s->top = -1;
for( i = 0 ; ( x = postfix[i] ) != '\0'; i++ )
{
if( isdigit( x ) )
{
push( s, (x - 48 ) );
}
else
{
b = pop( s );
a = pop( s );
switch( x )
{
case '+':
value = a + b;
break;
case '-':
value = a - b;
break;
case '*':
value = a * b;
break;
case '/':
value = a / b;
break;
case '%':
value = a % b;
break;
case '$':
value = pow( a, b );
break;
default:
printf("\n'%c' is an invalid operator.",x);
getch();
exit(0);
}
push( s, value );
}
}
return( pop( s ) );
}
void main()
{
char postfix[30];
clrscr();
printf("Enter a postfix expression: ");
scanf( "%s",postfix );
printf("\nThe result of the postfix expression => %d", result( postfix ) );
getch();
}
....................................................................................................................................
Program to implement a minimum priority queue
#include <stdio.h>
#include <conio.h>
#define QSIZE 6
struct Queue
{
int item[QSIZE];
int front;
int rear;
};
int empty( struct Queue *pq )
{
if( pq->front == pq->rear )
return 1;
else
return 0;
}
void pqinsert( struct Queue *pq, int x )
{
if( pq->rear == QSIZE - 1 )
printf("The queue is full.");
else
pq->item[++pq->rear] = x;
}
int pqmindel( struct Queue *pq )
{
int i, min, index;
if( empty( pq ) )
{
printf("\nThe queue is empty.");
return( -999 );
}
min = pq->item[pq->front];
index = pq->front;
for( i = pq->front + 1; i <= pq->rear; i++ )
if( pq->item[i] < min )
{
min = pq->item[i];
index = i;
}
for( i = index; i < pq->rear; i++ )
pq->item[i] = pq->item[i+1];
pq->rear--;
return( min );
}
void display( struct Queue *pq )
{
int i;
if( empty( pq ) )
printf("\nThe queue is empty.");
else
{
printf("\nThe Pririty Queue: ");
for( i = pq->front + 1; i <= pq->rear; i++ )
printf("%d ",pq->item[i]);
}
}
void main()
{
struct Queue *pq;
char c;
int x;
clrscr();
pq->front = pq->rear = -1;
do
{
printf("\n\nMain Menu: "
"\n 1. Empty,"
"\n 2. Insert,"
"\n 3. Delete,"
"\n 4. Display,"
"\n 5. Exit."
"\nEnter your choice: ");
c = getche();
switch( c )
{
case '1':
if( empty( pq ) )
printf("\nThe queue is empty.");
else
printf("\nThe queue is not empty.");
break;
case '2':
printf("\nEnter item to insert: ");
scanf("%d",&x);
pqinsert( pq, x );
break;
case '3':
x = pqmindel( pq );
if( x != -999 )
printf("\nThe removed item: %d",x);
break;
case '4':
display( pq );
break;
}
}
while( c != '5' );
}
..............................................................................................................................................
Program to implement linear queue
#include <stdio.h>
#include <conio.h>
#define QSIZE 6
struct Queue
{
int item[QSIZE];
int front;
int rear;
};
int empty( struct Queue *q )
{
if( q->front == q->rear )
return 1;
else
return 0;
}
void insert( struct Queue *q, int x )
{
if( q->rear == QSIZE - 1 )
printf("The queue is full.");
else
q->item[++q->rear] = x;
}
int del( struct Queue *q )
{
if( empty( q ) )
{
printf("\nThe queue is empty.");
return( -999 );
}
else
return( q->item[++q->front] );
}
void display( struct Queue *q )
{
int i;
if( empty( q ) )
printf("\nThe queue is full.");
else
{
printf("\nThe Queue: ");
for( i = q->front + 1; i <= q->rear; i++ )
printf("%d ",q->item[i]);
}
}
void main()
{
struct Queue q;
char c;
int x;
clrscr();
q.front = q.rear = -1;
do
{
printf("\n\nMain Menu: "
"\n 1. Empty,"
"\n 2. Insert,"
"\n 3. Delete,"
"\n 4. Display,"
"\n 5. Exit."
"\nEnter your choice: ");
c = getche();
switch( c )
{
case '1':
if( empty( &q ) )
printf("\nThe queue is empty.");
else
printf("\nThe queue is not empty.");
break;
case '2':
printf("\nEnter item to insert: ");
scanf("%d",&x);
insert( &q, x );
break;
case '3':
x = del( &q );
if( x != -999 )
printf("\nThe removed item: %d",x);
break;
case '4':
display( &q );
break;
}
}
while( c != '5' );
}
0 comments:
Post a Comment