Name:-Arvind kumar

Reg. no:- 24MCA0188

Q1. Stack Implementation

Sol:-

#include <stdio.h>

#define size 10

struct stack

int s[size];

int top;

} st;

void insert()

// check for full

int ele;

printf("Enter the element ");

scanf("%d", &ele);

if ([Link] == size - 1)

printf("Stack is full \n");

}
 else

[Link]++;

st.s[[Link]] = ele;

void delete()

// check for empty

if ([Link] == -1)

printf("Stack is empty \n");

else

[Link]--;

void display()

if ([Link] == -1)

printf("Stack is empty \n");

 }

else

int temp = [Link];

while (temp >= 0)

printf("%d ", st.s[temp]);

temp--;

printf("\n");

void main()

[Link] = -1;

int choice = 0;

while (choice != 4)

printf("[Link] \n [Link] \n [Link] \n [Link] \n");

printf("Enter your choice \n");

scanf("%d", &choice);

switch (choice)
 {

case 1:

insert();

break;

case 2:

delete ();

break;

case 3:

display();

break;

default:

if (choice != 4)

printf("Enter right option \n");

Output:-
Q2. Infix to Postfix Conversion

Sol:-

#include <stdio.h>

struct Stack

int arr[20];

int top;

} st;

char infix[20], postfix[20];

void push(int ele)

if ([Link] == 19)

printf("Stack Overflow!");

else

[Link]++;

[Link][[Link]] = ele;

char pop()

if ([Link] == -1)

printf("Stack Underflow!");

return '0';

int ele;

ele = [Link][[Link]];

[Link]--;
 if (ele == 1)

return '+';

else if (ele == 2)

return '-';

else if (ele == 3)

return '*';

else if (ele == 4)

return '/';

else if (ele == 5)

return '^';

return '0';

void toPostfix()

int i, j = 0;

for (i = 0; infix[i] != '\0'; i++)

switch (infix[i])

case '+':

if ([Link] == -1)

{
 push(1);

break;

while ([Link][[Link]] >= 1)

postfix[j++] = pop();

push(1);

break;

case '-':

if ([Link] == -1)

push(2);

break;

while ([Link][[Link]] >= 1)

postfix[j++] = pop();

push(2);

break;
case '*':

if ([Link] == -1)

push(3);

break;

while ([Link][[Link]] >= 3)

postfix[j++] = pop();

push(3);

break;

case '/':

if ([Link] == -1)

push(4);

break;

while ([Link][[Link]] >= 3)

postfix[j++] = pop();

}
 push(4);

break;

case '^':

if ([Link] == -1)

push(5);

break;

while ([Link][[Link]] >= 5)

postfix[j++] = pop();

push(5);

break;

case '(':

push(0);

break;

case ')':

if ([Link] == -1)

{
 printf("Invalid expression.");

break;

while ([Link][[Link]] != 0)

postfix[j++] = pop();

[Link]--;

break;

default:

postfix[j++] = infix[i];

break;

while ([Link] != -1)

postfix[j++] = pop();

printf("Postfix expression is : ");

i = 0;
 while (postfix[i] != '\0')

printf("%c", postfix[i++]);

void main()

[Link] = -1;

printf("Enter the expression: ");

scanf("%s", &infix);

toPostfix();

Output:-

Q3. Infix to Prefix Conversion-

Sol:-

#include <stdio.h>

#define size 20
struct stack

int arr[size];

int top;

} st;

char infix[size], prefix_temp[size], infix_reversed[size], prefix[size];

int length(char *arr)

int len, i;

len = 0;

i = 0;

while (arr[i] != '\0')

len++;

i++;

return len;

void push(int ele)

{
 if ([Link] == 19)

printf("Stack Overflow!");

else

[Link]++;

[Link][[Link]] = ele;

char pop()

if ([Link] == -1)

printf("Stack Underflow!");

return '0';

int ele;

ele = [Link][[Link]];

[Link]--;

if (ele == 1)

return '+';
 else if (ele == 2)

return '-';

else if (ele == 3)

return '*';

else if (ele == 4)

return '/';

else if (ele == 5)

return '^';

return '0';

void reverseInfix()

int i, j, len;

j = 0;

len = length(infix);

for (i = len - 1; i >= 0; i--)

infix_reversed[j++] = infix[i];

void reversePrefix()
{

int i, j, len;

j = 0;

len = length(prefix_temp);

for (i = len - 1; i >= 0; i--)

prefix[j++] = prefix_temp[i];

void toPrefix()

int i, j;

j = 0;

reverseInfix();

for (i = 0; infix_reversed[i] != '\0'; i++)

switch (infix_reversed[i])

case '+':

if ([Link] == -1)

push(1);
 break;

else if ([Link][[Link]] <= 2)

push(1);

break;

else

while ([Link][[Link]] > 2 && [Link] != -1)

prefix_temp[j++] = pop();

push(1);

break;

case '-':

if ([Link] == -1)

push(2);

break;

}
 else if ([Link][[Link]] <= 2)

push(2);

break;

else

while ([Link][[Link]] > 2 && [Link] != -1)

prefix_temp[j++] = pop();

push(2);

break;

case '*':

if ([Link] == -1)

push(3);

break;

else if ([Link][[Link]] <= 3)

{
 push(3);

break;

else

while ([Link][[Link]] > 3 && [Link] != -1)

prefix_temp[j++] = pop();

push(3);

break;

case '/':

if ([Link] == -1)

push(4);

break;

else if ([Link][[Link]] <= 4)

push(4);

break;
 }

else

while ([Link][[Link]] > 4 && [Link] != -1)

prefix_temp[j++] = pop();

push(4);

break;

case '^':

if ([Link] == -1)

push(5);

break;

else if ([Link][[Link]] <= 5)

push(5);

break;

else
 {

while ([Link][[Link]] > 5 && [Link] != -1)

prefix_temp[j++] = pop();

push(5);

break;

case ')':

push(0);

break;

case '(':

if ([Link] == -1)

printf("Invalid expression.");

break;

while ([Link][[Link]] != 0)

if ([Link] == 0)

{
 printf("Invalid expression.");

return;

prefix_temp[j++] = pop();

pop();

break;

default:

prefix_temp[j++] = infix_reversed[i];

break;

while ([Link] != -1)

prefix_temp[j++] = pop();

reversePrefix();

printf("Prefix is : %s\n", prefix);

}
void main()

[Link] = -1;

printf("Enter infix expression: ");

scanf("%s", &infix);

toPrefix();

Output:-

[Link] Evaluation-

Sol:-

#include<stdio.h>

#include<math.h>

#define size 20

struct stack{

int arr[size];

int top;

}st;
char postfix[size];

void push(int data){

if ([Link]==size-1){

printf("Stack overflow.");

else{

[Link]++;

[Link][[Link]]=data;

int pop(){

if ([Link]==-1){

printf("Stack Underflow!");

return '0';

int ele;

ele = [Link][[Link]];

[Link]--;

return ele;

}
int evaluate(int data1, int data2, char opr){

if (opr=='+'){

return data2 + data1;

else if (opr=='-'){

return data2 - data1;

else if (opr=='*'){

return data2 * data1;

else if (opr=='/'){

return data2 / data1;

else if (opr=='^'){

return pow(data2,data1);

else{

return 0;

int postfix_evaluation(){

int i, data1, data2, res;

for(i=0; postfix[i]!='\0'; i++){

switch (postfix[i]){

case '+':

data1 = pop();

data2 = pop();

res = evaluate(data1, data2, '+');

push(res);

break;

case '-':

data1 = pop();

data2 = pop();

res = evaluate(data1, data2, '-');

push(res);

break;

case '*':

data1 = pop();

data2 = pop();

res = evaluate(data1, data2, '*');

push(res);

break;

case '/':

data1 = pop();

data2 = pop();
 res = evaluate(data1, data2, '/');

push(res);

break;

case '^':

data1 = pop();

data2 = pop();

res = evaluate(data1, data2, '^');

push(res);

break;

default:

push(postfix[i]-48);

break;

return pop();

void main(){

[Link] = -1;

printf("Enter the postfix expression: ");

scanf("%s", &postfix);

int res;
 res = postfix_evaluation();

printf("%d\n", res);

Output:-

Q5. Prefix Evaluation-

Sol:-

#include<stdio.h>

#include<math.h>

#define size 20

struct stack{

int arr[size];

int top;

}st;

char prefix[size], prefixReversed[size];

int length(char *arr){

int len, i;

len = 0;
 i = 0;

while (arr[i]!='\0'){

len++;

i++;

return len;

void reverse(){

int i, j, len;

j = 0;

len = length(prefix);

for (i=len-1; i>=0; i--){

prefixReversed[j++] = prefix[i];

void push(int data){

if ([Link]==size-1){

printf("Stack overflow.");

else{

[Link]++;
 [Link][[Link]]=data;

int pop(){

if ([Link]==-1){

printf("Stack Underflow!");

return '0';

int ele;

ele = [Link][[Link]];

[Link]--;

return ele;

int prefix_evaluation(){

int i, data1, data2;

reverse();

for(i=0; prefixReversed[i]!='\0'; i++){

switch (prefixReversed[i]){

case '+':

data1 = pop();

data2 = pop();
 push(data2 + data1);

break;

case '-':

data1 = pop();

data2 = pop();

push(data2 - data1);

break;

case '*':

data1 = pop();

data2 = pop();

push(data2 * data1);

break;

case '/':

data1 = pop();

data2 = pop();

push(data2 / data1);

break;

case '^':

data1 = pop();

data2 = pop();

push(pow(data2, data1));

break;

default:
 push(prefixReversed[i]-48);

break;

return pop();

void main(){

[Link] = -1;

printf("Enter the postfix expression: ");

scanf("%s", &prefix);

int res;

res = prefix_evaluation();

printf("%d\n", res);

Output:-

Q6. Linear Queue Implementation-

Sol:-
#include <stdio.h>

#include <stdlib.h>

#define size 20

struct Queue

int q[size];

int front, rear;

} lq;

void insert()

int data;

if ([Link] == size - 1)

printf("Queue is FUll");

else

printf("Enter your data");

scanf("%d", &data);

if ([Link] == -1)

{
 [Link]++;

lq.q[++[Link]] = data;

else

lq.q[++[Link]] = data;

void delete()

if ([Link] == -1)

printf("Queue is Empty");

else if ([Link] == [Link])

[Link] = -1;

[Link] = -1;

else

[Link]++;
 }

void display()

int temp;

if ([Link] == -1)

printf("Queue is Empty");

else

temp = [Link];

while (temp <= [Link])

printf("%d ", lq.q[temp]);

temp++;

void main()

[Link] = [Link] = -1;

 int choice;

while (choice != 4)

printf("\[Link] \[Link] \[Link] \[Link]\n");

printf("Enter your choice: ");

scanf("%d", &choice);

switch (choice)

case 1:

insert();

break;

case 2:

delete ();

break;

case 3:

display();

break;

default:

printf("Wrong choice!");

Output:-
Q7. Circular Queue Implementation-

Sol:-

#include <stdio.h>

#include <stdlib.h>

#define size 20

struct Queue

int q[size];

int front, rear;

} cq;

void insert()

int data;

if ([Link] == ([Link] + 1) % size)

printf("Queue is FUll");

else

printf("Enter your data:");

scanf("%d", &data);

if ([Link] == -1)

[Link] = (([Link] + 1) % size);

[Link] = (([Link] + 1) % size);

cq.q[[Link]] = data;

else

[Link] = (([Link] + 1) % size);

cq.q[[Link]] = data;
 }

void delete()

if ([Link] == -1)

printf("Queue is Empty");

else if ([Link] == [Link])

[Link] = -1;

[Link] = -1;

else

[Link] = ([Link] + 1 % size);

void display()

int temp;

if ([Link] == -1)
 {

printf("Queue is Empty");

else

temp = [Link];

if ([Link] == [Link])

printf("%d ", cq.q[temp]);

else

while (temp != [Link])

printf("%d ", cq.q[temp]);

temp = (temp + 1) % size;

printf("%d ", cq.q[temp]);

void main()
{

[Link] = [Link] = -1;

int choice;

while (choice != 4)

printf("\[Link] \[Link] \[Link] \[Link]\n");

printf("Enter your choice: ");

scanf("%d", &choice);

switch (choice)

case 1:

insert();

break;

case 2:

delete ();

break;

case 3:

display();

break;

default:

printf("Wrong choice!");

}
}

Output:-

Q8. Priority Queue Implementation-

Sol-

#include <stdio.h>

#include <conio.h>

#include <stdlib.h>

#define size 20

struct Queue
{

int q[size];

int front, rear;

} pq;

int isEmpty()

if ([Link] == -1)

return 1;

else

return 0;

int isFull()

if ([Link] == size - 1)

return 1;

else
 {

return 0;

void priority()

int i, j, k, temp;

for (i = 1; i < 5; i++)

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

if (pq.q[j] < pq.q[i])

temp = pq.q[j];

pq.q[j] = pq.q[i];

for (k = i; k > j; k--)

pq.q[k] = pq.q[k - 1];

pq.q[k + 1] = temp;

}
}

void main()

[Link] = [Link] = -1;

int choice, item, temp;

while (choice != 4)

printf("\[Link] \[Link] \[Link] \[Link]\n");

printf("Enter your choice: ");

scanf("%d", &choice);

switch (choice)

case 1:

if (isFull() == 1)

printf("Queue is FUll");

else

printf("Enter the item: ");

scanf("%d", &item);

if ([Link] == -1)
 {

[Link]++;

[Link]++;

pq.q[[Link]] = item;

else

pq.q[++[Link]] = item;

priority();

break;

case 2:

if (isEmpty() == 1)

printf("Queue is Empty");

else

if (([Link] == [Link]) && ([Link] != 1))

[Link] = -1;

[Link] = -1;
 }

else

[Link]++;

break;

case 3:

if (isEmpty() == 1)

printf("Queue is Empty");

else

priority();

temp = [Link];

while (temp <= [Link])

printf("%d ", pq.q[temp]);

temp++;

break;
 default:

printf("Wrong choice!");

Output:- Priority=Decending order

Q9. Singly Linked-List Implementation-

Sol:-

#include <stdio.h>

#include <stdlib.h>
struct node

int data;

struct node *next;

};

struct node *head, *tail, *temp, *nw, *temp1, *temp2;

void display()

if (head == NULL)

printf("List is Empty \n");

else

temp = head;

printf("Output is here: ");

while (temp != NULL)

printf("%d ", temp->data);

temp = temp->next;

printf("\n");
 }

void create()

int item;

printf("Enter your item: ");

scanf("%d", &item);

if (head == NULL)

nw = (struct node *)malloc(sizeof(struct node));

nw->data = item;

nw->next = NULL;

head = tail = nw;

else

nw = (struct node *)malloc(sizeof(struct node));

nw->data = item;

nw->next = NULL;

tail->next = nw;

tail = nw;

}
void insert_at_begin()

int item;

printf("Enter item: ");

scanf("%d", &item);

if (head == NULL)

nw = (struct node *)malloc(sizeof(struct node));

nw->data = item;

nw->next = NULL;

head = tail = nw;

else

nw = (struct node *)malloc(sizeof(struct node));

nw->data = item;

nw->next = head;

head = nw;

void insert_at_mid()

int pos, item;

 printf("Enter position which you want to insert: ");

scanf("%d", &pos);

printf("Enter your item: ");

scanf("%d", &item);

temp1 = temp2 = head;

for (int i = 0; i < pos - 2; i++)

temp1 = temp1->next;

temp2 = temp1->next;

nw = (struct node *)malloc(sizeof(struct node));

nw->data = item;

nw->next = temp2;

temp1->next = nw;

void insert_at_end()

int item;

printf("Enter item: ");

scanf("%d", &item);

nw = (struct node *)malloc(sizeof(struct node));

nw->data = item;

nw->next = NULL;
 tail->next = nw;

tail = nw;

void delete_from_start()

if (head == NULL)

printf("Sorry! Data not available in the list");

else

temp = head;

head = head->next;

temp->next = NULL;

free(temp);

void delete_from_mid()

int pos;

printf("Enter the position where you want to delete: ");

scanf("%d", &pos);

temp1 = temp2 = head;

 for (int i = 0; i < pos - 2; i++)

temp1 = temp1->next;

temp2 = temp1->next;

temp1->next = temp2->next;

temp2->next = NULL;

free(temp2);

void delete_from_end()

if (head == tail)

temp = head;

temp->next = NULL;

free(temp);

head = tail = NULL;

else

temp = head;

while (temp->next->next != NULL)

{
 temp = temp->next;

temp->next = NULL;

free(tail);

tail = temp;

void main()

head = tail = NULL;

int choice;

while (choice != 9)

printf("[Link] \n [Link] \n [Link] at Begin \n [Link] at Mid \n

[Link] at End \[Link] from Begin \[Link] from Mid \[Link] from
End \[Link] \n");

printf("Enter choice ");

scanf("%d", &choice);

switch (choice)

case 1:

create();

break;
case 2:

display();

break;

case 3:

insert_at_begin();

break;

case 4:

insert_at_mid();

break;

case 5:

insert_at_end();

break;

case 6:

delete_from_start();

break;

case 7:

delete_from_mid();

break;

case 8:

delete_from_end();

break;

default:

printf("Choose valid option: ");

 }

Output:-

Q10. Doubly Linked-List Implementation-

Sol:-

#include <stdio.h>

#include <stdlib.h>
struct node

int data;

struct node *next, *prev;

};

struct node *head, *tail, *nw, *temp;

void create()

int data, n, i;

printf("How many data you want to input: ");

scanf("%d", &n);

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

printf("Enter data: ");

scanf("%d", &data);

if (head == NULL)

nw = (struct node *)malloc(sizeof(struct node));

nw->data = data;

nw->prev = NULL;

nw->next = NULL;
 head = tail = nw;

else

nw = (struct node *)malloc(sizeof(struct node));

nw->data = data;

nw->prev = tail;

nw->next = NULL;

tail->next = nw;

tail = nw;

void display()

if (head == NULL)

printf("There is no element in list.\n");

else

temp = head;
 printf("Elements are: ");

while (temp != NULL)

printf("%d ", temp->data);

temp = temp->next;

void main()

int choice;

head = tail = NULL;

choice = 0;

while (choice != 3)

printf("Enter your choice: \n");

printf("1. Create\n2. Display\n3. Exit\n");

scanf("%d", &choice);

if (choice == 1)

create();

}
 else if (choice == 2)

display();

else if (choice > 3 || choice <= 0)

printf("Wrong choice! Try again.\n");

Output:-