Data Structures and algorithms Lab [BCA-106P] 2025

/*Program 12: WAP to implement a Singly Linked List.

Name : Abhijeet Singh

Enroll. No : 02914202024
*/

Solution:

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

struct Node {
int data;
struct Node* next;
};

struct Node* head = NULL;

void insertAtEnd(int value) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;

if (head == NULL) {
head = newNode;
} else {
struct Node* temp = head;
while (temp->next != NULL)
temp = temp->next;
temp->next = newNode;
}
printf("Node inserted.\n");
}

void deleteAtBeginning() {
if (head == NULL) {
printf("List is empty.\n");
} else {
struct Node* temp = head;
head = head->next;
free(temp);
printf("Node deleted from beginning.\n");
}
}

void display() {
if (head == NULL) {
printf("List is empty.\n");
} else {

Abhijeet Singh [Roll No: 02914202024] Page 27

 Data Structures and algorithms Lab [BCA-106P] 2025

struct Node* temp = head;

printf("Linked List: ");
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
}

void main() {
int choice, value;
clrscr();
printf("\t\t Name: Abhijeet Singh \t\t Roll No: 02914202024\n\n");

while (1) {
printf("\n1. Insert at End\n2. Delete from Beginning\n3. Display\n4. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);

switch (choice) {
case 1:
printf("Enter value to insert: ");
scanf("%d", &value);
insertAtEnd(value);
break;
case 2:
deleteAtBeginning();
break;
case 3:
display();
break;
case 4:
exit(0);
default:
printf("Invalid choice.\n");
}
}
getch();
}

Abhijeet Singh [Roll No: 02914202024] Page 28

 Data Structures and algorithms Lab [BCA-106P] 2025

Output:

Abhijeet Singh [Roll No: 02914202024] Page 29

 Data Structures and algorithms Lab [BCA-106P] 2025

/*Program 13: WAP to implement a Circular Linked Lists

Name : Abhijeet Singh

Enroll. No : 02914202024
*/

Solution:

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

struct Node {
int data;
struct Node* next;
};

struct Node* head = NULL;

void insertAtEnd(int value) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;

if (head == NULL) {
head = newNode;
newNode->next = head;
} else {
struct Node* temp = head;
while (temp->next != head)
temp = temp->next;
temp->next = newNode;
newNode->next = head;
}
printf("Node inserted.\n");
}

void deleteAtBeginning() {
if (head == NULL) {
printf("List is empty.\n");
return;
}

struct Node* temp = head;

if (head->next == head) {
head = NULL;
} else {
struct Node* last = head;
while (last->next != head)
last = last->next;

Abhijeet Singh [Roll No: 02914202024] Page 30

 Data Structures and algorithms Lab [BCA-106P] 2025

head = head->next;
last->next = head;
}
free(temp);
printf("Node deleted from beginning.\n");
}

void display() {
if (head == NULL) {
printf("List is empty.\n");
return;
}

struct Node* temp = head;

printf("Circular Linked List: ");
do {
printf("%d -> ", temp->data);
temp = temp->next;
} while (temp != head);
printf("(head)\n");
}

void main() {
int choice, value;
clrscr();
printf("\t\t Name: Abhijeet Singh \t\t Roll No: 02914202024\n\n");

while (1) {
printf("\n1. Insert at End\n2. Delete from Beginning\n3. Display\n4. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);

switch (choice) {
case 1:
printf("Enter value to insert: ");
scanf("%d", &value);
insertAtEnd(value);
break;
case 2:
deleteAtBeginning();
break;
case 3:
display();
break;
case 4:
exit(0);
default:
printf("Invalid choice.\n");
}
}

Abhijeet Singh [Roll No: 02914202024] Page 31

 Data Structures and algorithms Lab [BCA-106P] 2025

getch();
}

Output:

Abhijeet Singh [Roll No: 02914202024] Page 32

 Data Structures and algorithms Lab [BCA-106P] 2025

/*Program 14: WAP to implement Doubly Linked Lists

Name : Abhijeet Singh

Enroll. No : 02914202024
*/

Solution:

#include <stdio.h>

Output:

Abhijeet Singh [Roll No: 02914202024] Page 33

 Data Structures and algorithms Lab [BCA-106P] 2025

Abhijeet Singh [Roll No: 02914202024] Page 34

 Data Structures and algorithms Lab [BCA-106P] 2025

/*Program 15: WAP to implement Polynomial addition operation using linked list.

Name : Abhijeet Singh

Enroll. No : 02914202024
*/

Solution:

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

struct polynode {
float coeff;
int exp;
struct polynode *next;
};

void poly_append(struct polynode **, float, int);

void display_poly(struct polynode *);
void poly_add(struct polynode *, struct polynode *, struct polynode **);

void poly_append(struct polynode **q, float x, int y) {

struct polynode *temp = (struct polynode *)malloc(sizeof(struct polynode));
temp->coeff = x;
temp->exp = y;
temp->next = NULL;

if (*q == NULL) {
*q = temp;
} else {
struct polynode *last = *q;
while (last->next != NULL) {
last = last->next;
}
last->next = temp;
}
}

void display_poly(struct polynode *q) {

while (q != NULL) {
printf("%.1f x^%d ", q->coeff, q->exp);
if (q->next != NULL) {
printf("+ ");
}
q = q->next;
}
printf("\n");
}

void poly_add(struct polynode *x, struct polynode *y, struct polynode **s) {

Abhijeet Singh [Roll No: 02914202024] Page 35

 Data Structures and algorithms Lab [BCA-106P] 2025

struct polynode *z = NULL;

while (x != NULL && y != NULL) {

struct polynode *temp = (struct polynode *)malloc(sizeof(struct polynode));
if (x->exp < y->exp) {
temp->coeff = y->coeff;
temp->exp = y->exp;
y = y->next;
} else if (x->exp > y->exp) {
temp->coeff = x->coeff;
temp->exp = x->exp;
x = x->next;
} else {
temp->coeff = x->coeff + y->coeff;
temp->exp = x->exp;
x = x->next;
y = y->next;
}
temp->next = NULL;

if (*s == NULL) {
*s = temp;
z = *s;
} else {
z->next = temp;
z = z->next;
}
}

while (x != NULL) {
struct polynode *temp = (struct polynode *)malloc(sizeof(struct polynode));
temp->coeff = x->coeff;
temp->exp = x->exp;
temp->next = NULL;
if (*s == NULL) {
*s = temp;
z = *s;
} else {
z->next = temp;
z = z->next;
}
x = x->next;
}

while (y != NULL) {
struct polynode *temp = (struct polynode *)malloc(sizeof(struct polynode));
temp->coeff = y->coeff;
temp->exp = y->exp;
temp->next = NULL;
if (*s == NULL) {

Abhijeet Singh [Roll No: 02914202024] Page 36

 Data Structures and algorithms Lab [BCA-106P] 2025

*s = temp;
z = *s;
} else {
z->next = temp;
z = z->next;
}
y = y->next;
}
}

int main() {
struct polynode *first = NULL, *second = NULL, *total = NULL;

printf("\t\t Name: Abhijeet Singh \t\t Roll No: 02914202024\n\n");

poly_append(&first, 1.4, 5);

poly_append(&first, 1.5, 4);
poly_append(&first, 1.7, 2);
poly_append(&first, 1.8, 1);
poly_append(&first, 1.9, 0);

printf("First Polynomial: ");

display_poly(first);

poly_append(&second, 1.5, 6);

poly_append(&second, 2.5, 5);
poly_append(&second, -3.5, 4);
poly_append(&second, 4.5, 3);
poly_append(&second, 6.5, 1);

printf("Second Polynomial: ");

display_poly(second);

printf("\nResult of Addition: ");

poly_add(first, second, &total);
display_poly(total);

return 0;
}

Output:

Abhijeet Singh [Roll No: 02914202024] Page 37

 Data Structures and algorithms Lab [BCA-106P] 2025

/*Program 16: Write a C program to create two linked lists from a given list in
following way
INPUT List:- 1 2 3 4 5 6 7 8 9 10
OUTPUT:- First List:- 1 3 5 7 9 Second List:- 2 4 6 8 10

Name : Abhijeet Singh

Enroll. No : 02914202024
*/

Solution:

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

struct Node
{
int data;
struct Node* next;
};

void append(struct Node** head_ref, int new_data)

{
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
struct Node* last = *head_ref;

new_node->data = new_data;
new_node->next = NULL;

if (*head_ref == NULL)
{
*head_ref = new_node;
return;
}

while (last->next != NULL)

{
last = last->next;
}
last->next = new_node;
}

void display(struct Node* node)

{
while (node != NULL)
{
printf("%d ", node->data);
node = node->next;
}
printf("\n");

Abhijeet Singh [Roll No: 02914202024] Page 38

 Data Structures and algorithms Lab [BCA-106P] 2025

void createLists(struct Node* input, struct Node** list1, struct Node** list2)
{
int index = 1; // Start with index 1 for the first element
while (input != NULL)
{
if (index % 2 != 0)
{
append(list1, input->data);
}
else
{
append(list2, input->data);
}
input = input->next;
index++;
}
}

int main()
{
struct Node* inputList = NULL;
struct Node* list1 = NULL;
struct Node* list2 = NULL;

printf("\t\t Name: Abhijeet Singh \t\t Roll No: 02914202024\n\n");

for (int i = 1; i <= 10; i++)

{
append(&inputList, i);
}

createLists(inputList, &list1, &list2);

printf("Input List: ");

display(inputList);
printf("First List (Odd Indexed): ");
display(list1);
printf("Second List (Even Indexed): ");
display(list2);

return 0;
}

Abhijeet Singh [Roll No: 02914202024] Page 39

 Data Structures and algorithms Lab [BCA-106P] 2025

Output:

Abhijeet Singh [Roll No: 02914202024] Page 40

 Data Structures and algorithms Lab [BCA-106P] 2025

/*Program 17: Write a menu driven program to implement (i) Static

Stack (ii) Dynamic Stack.

Name : Abhijeet Singh

Enroll. No : 02914202024
*/

Solution:

(i) Static Stack

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

#define MAXSIZE 10

void push();
int pop();
void traverse();

int stack[MAXSIZE];
int Top = -1;

int main()
{
int choice;
char ch;
printf("\t\t Name: Abhijeet Singh \t\t Roll No: 02914202024\n\n");

do
{
printf("\n--- Static Stack using Array ---");
printf("\n1. PUSH ");
printf("\n2. POP ");
printf("\n3. TRAVERSE ");
printf("\nEnter your choice: ");
scanf("%d", &choice);

switch (choice)
{
case 1:
push();
break;
case 2:
printf("\nThe deleted element is %d\n", pop());
break;
case 3:
traverse();
break;
default:

Abhijeet Singh [Roll No: 02914202024] Page 41

 Data Structures and algorithms Lab [BCA-106P] 2025

printf("\nYou Entered Wrong Choice\n");

}

printf("\nDo You Wish To Continue (Y/N): ");

scanf(" %c", &ch); // added space before %c to skip any leftover newline

} while (ch == 'Y' || ch == 'y');

return 0;
}

void push()
{
int item;
if (Top == MAXSIZE - 1)
{
printf("\nThe Stack Is FULL (OVERFLOW)\n");
return;
}
else
{
printf("Enter the element to be inserted: ");
scanf("%d", &item);
Top = Top + 1;
stack[Top] = item;
printf("Element pushed successfully.\n");
}
}

int pop()
{
int item;
if (Top == -1)
{
printf("The Stack is EMPTY (UNDERFLOW)\n");
return -1;
}
else
{
item = stack[Top];
Top = Top - 1;
return item;
}
}

void traverse()
{
int i;
if (Top == -1)
{

Abhijeet Singh [Roll No: 02914202024] Page 42

 Data Structures and algorithms Lab [BCA-106P] 2025

printf("The Stack is EMPTY\n");

}
else
{
printf("\nStack elements (Top to Bottom):\n");
for (i = Top; i >= 0; i--)
{
printf("%d\n", stack[i]);
}
}
}

Output:

(ii) Dynamic Stack.

Abhijeet Singh [Roll No: 02914202024] Page 43

 Data Structures and algorithms Lab [BCA-106P] 2025

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

// Node structure
struct node
{
int data;
struct node *link;
};

// Function declarations
void push(struct node **, int);
int pop(struct node **);
void display(struct node *);

int main()
{
struct node *top = NULL;
int ch, item;
printf("\t\t Name: Abhijeet Singh \t\t Roll No: 02914202024\n\n");

do
{
printf("\n--- Dynamic Stack using Linked List ---");
printf("\n1. Push");
printf("\n2. Pop");
printf("\n3. Display");
printf("\n4. Exit");
printf("\nEnter your choice: ");
scanf("%d", &ch);

switch (ch)
{
case 1:
printf("Enter value to be inserted: ");
scanf("%d", &item);
push(&top, item);
break;
case 2:
item = pop(&top);
if (item != -1)
printf("Item popped: %d\n", item);
break;
case 3:
display(top);
break;
case 4:
printf("Exiting program...\n");
exit(0);
default:

Abhijeet Singh [Roll No: 02914202024] Page 44

 Data Structures and algorithms Lab [BCA-106P] 2025

printf("Invalid choice. Please try again.\n");

}
} while (1);

return 0;
}

void push(struct node **top, int item)

{
struct node *temp = (struct node *)malloc(sizeof(struct node));
if (temp == NULL)
{
printf("\nMemory allocation failed. Stack is full.\n");
return;
}
temp->data = item;
temp->link = *top;
*top = temp;
}

int pop(struct node **top)

{
if (*top == NULL)
{
printf("\nStack is empty.\n");
return -1;
}
struct node *temp = *top;
int item = temp->data;
*top = temp->link;
free(temp);
return item;
}

void display(struct node *top)

{
if (top == NULL)
{
printf("\nStack is empty.\n");
return;
}

printf("\nStack elements (Top to Bottom):\n");

struct node *ptr = top;
while (ptr != NULL)
{
printf("%d\n", ptr->data);
ptr = ptr->link;
}
}

Abhijeet Singh [Roll No: 02914202024] Page 45

 Data Structures and algorithms Lab [BCA-106P] 2025

Output:

Abhijeet Singh [Roll No: 02914202024] Page 46

 Data Structures and algorithms Lab [BCA-106P] 2025

/*Program 18: Write a program to convert Infix to equivalent (i) Prefix expression (ii)
Postfix expression

Name : Abhijeet Singh

Enroll. No : 02914202024
*/

Solution:

(i) Prefix Expression

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

#define MAX 50

struct infix {
char target[MAX];
char stack[MAX];
char *s, *t;
int top;
};

void initinfix(struct infix *);

void setexpr(struct infix *, char *);
void push(struct infix *, char);
char pop(struct infix *);
void convert(struct infix *);
int priority(char);
void show(struct infix);
void reverse(char *str);

int main() {
struct infix p;
char expr[MAX];
printf("\t\t Name: Abhijeet Singh \t\t Roll No: 02914202024\n\n");

initinfix(&p);

printf("Enter an expression in infix form: ");

fgets(expr, MAX, stdin);
expr[strcspn(expr, "\n")] = '\0'; // Remove trailing newline

setexpr(&p, expr);
convert(&p);

printf("The prefix expression is: ");

show(p);

Abhijeet Singh [Roll No: 02914202024] Page 47

 Data Structures and algorithms Lab [BCA-106P] 2025

return 0;
}

/* initializes structure elements */

void initinfix(struct infix *p) {
p->top = -1;
strcpy(p->target, "");
strcpy(p->stack, "");
p->t = p->target;
}

/* reverse the expression and set pointer */

void setexpr(struct infix *p, char *str) {
static char rev[MAX];
strcpy(rev, str);
reverse(rev); // use custom reverse
p->s = rev;
}

/* reverse a string in place */

void reverse(char *str) {
int i, len = strlen(str);
char temp;
for (i = 0; i < len / 2; i++) {
temp = str[i];
str[i] = str[len - 1 - i];
str[len - 1 - i] = temp;
}
}

/* push an element to the stack */

void push(struct infix *p, char c) {
if (p->top == MAX - 1)
printf("\nStack is full.\n");
else
p->stack[++(p->top)] = c;
}

/* pop an element from the stack */

char pop(struct infix *p) {
if (p->top == -1) {
printf("\nStack is empty.\n");
return -1;
} else
return p->stack[(p->top)--];
}

/* convert infix to prefix */

void convert(struct infix *p) {

Abhijeet Singh [Roll No: 02914202024] Page 48

 Data Structures and algorithms Lab [BCA-106P] 2025

char opr;
while (*(p->s)) {
if (*(p->s) == ' ' || *(p->s) == '\t') {
p->s++;
continue;
}

if (isdigit(*(p->s)) || isalpha(*(p->s))) {
*(p->t) = *(p->s);
p->t++;
p->s++;
} else if (*(p->s) == ')') {
push(p, *(p->s));
p->s++;
} else if (*(p->s) == '*' || *(p->s) == '+' || *(p->s) == '/' || *(p->s) == '%' || *(p->s) == '-' ||
*(p->s) == '$') {
while (p->top != -1 && priority(p->stack[p->top]) > priority(*(p->s))) {
*(p->t) = pop(p);
p->t++;
}
push(p, *(p->s));
p->s++;
} else if (*(p->s) == '(') {
opr = pop(p);
while (opr != ')') {
*(p->t) = opr;
p->t++;
opr = pop(p);
}
p->s++;
} else {
p->s++;
}
}

while (p->top != -1) {

*(p->t) = pop(p);
p->t++;
}
*(p->t) = '\0';
}

/* get priority of operators */

int priority(char c) {
if (c == '$')
return 3;
else if (c == '*' || c == '/' || c == '%')
return 2;
else if (c == '+' || c == '-')
return 1;

Abhijeet Singh [Roll No: 02914202024] Page 49

 Data Structures and algorithms Lab [BCA-106P] 2025

else
return 0;
}

/* display the prefix expression */

void show(struct infix p) {
reverse(p.target);
printf("%s\n", p.target);
}

Output:

(ii) Postfix expression

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#define MAX 50

struct infix {
char target[MAX];
char stack[MAX];
char *s, *t;
int top;
};

void initinfix(struct infix *);

void setexpr(struct infix *, char *);
void push(struct infix *, char);
char pop(struct infix *);
void convert(struct infix *);
int priority(char);
void show(struct infix);

int main() {
struct infix p;
char expr[MAX];
printf("\t\t Name: Abhijeet Singh \t\t Roll No: 02914202024\n\n");
initinfix(&p);

Abhijeet Singh [Roll No: 02914202024] Page 50

 Data Structures and algorithms Lab [BCA-106P] 2025

printf("\nEnter an expression in infix form: ");

fgets(expr, MAX, stdin);
expr[strcspn(expr, "\n")] = '\0'; // remove newline character

setexpr(&p, expr);
convert(&p);

printf("\nThe postfix expression is: ");

show(p);

return 0;
}

/* initializes structure elements */

void initinfix(struct infix *p) {
p->top = -1;
strcpy(p->target, "");
strcpy(p->stack, "");
p->t = p->target;
p->s = "";
}

/* sets s to point to given expr */

void setexpr(struct infix *p, char *str) {
p->s = str;
}

/* adds an operator to the stack */

void push(struct infix *p, char c) {
if (p->top == MAX - 1)
printf("\nStack is full.\n");
else {
p->top++;
p->stack[p->top] = c;
}
}

/* pops an operator from the stack */

char pop(struct infix *p) {
char item;
if (p->top == -1) {
printf("\nStack is empty.\n");
return -1;
} else {
item = p->stack[p->top];
p->top--;
return item;
}
}

Abhijeet Singh [Roll No: 02914202024] Page 51

 Data Structures and algorithms Lab [BCA-106P] 2025

/* returns the priority of an operator */

int priority(char c) {
if (c == '$')
return 3;
else if (c == '*' || c == '/' || c == '%')
return 2;
else if (c == '+' || c == '-')
return 1;
else
return 0;
}

/* converts the given expression from infix to postfix */

void convert(struct infix *p) {
char opr;

while (*(p->s) != '\0') {

if (*(p->s) == ' ' || *(p->s) == '\t') {
p->s++;
continue;
}

if (isdigit(*(p->s)) || isalpha(*(p->s))) {
while (isdigit(*(p->s)) || isalpha(*(p->s))) {
*(p->t) = *(p->s);
p->s++;
p->t++;
}
} else if (*(p->s) == '(') {
push(p, *(p->s));
p->s++;
} else if (*(p->s) == '*' || *(p->s) == '+' || *(p->s) == '/' || *(p->s) == '%' || *(p->s) == '-' ||
*(p->s) == '$') {
if (p->top != -1) {
opr = pop(p);
while (priority(opr) >= priority(*(p->s))) {
*(p->t) = opr;
p->t++;
opr = pop(p);
}
push(p, opr);
push(p, *(p->s));
} else {
push(p, *(p->s));
}
p->s++;
} else if (*(p->s) == ')') {
opr = pop(p);
while (opr != '(') {
*(p->t) = opr;

Abhijeet Singh [Roll No: 02914202024] Page 52

 Data Structures and algorithms Lab [BCA-106P] 2025

p->t++;
opr = pop(p);
}
p->s++;
} else {

p->s++;
}
}

while (p->top != -1) {

char opr = pop(p);
*(p->t) = opr;
p->t++;
}
*(p->t) = '\0';
}

/* displays the postfix form */

void show(struct infix p) {
printf("%s\n", p.target);
}

Output:

Abhijeet Singh [Roll No: 02914202024] Page 53

 Data Structures and algorithms Lab [BCA-106P] 2025

/*Program 19: Write a program to evaluate (i) Prefix Expression (ii) Postfix Expression
using stack.

Name : Abhijeet Singh

Enroll. No : 02914202024
*/

Solution:

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

#define SIZE 100

int stack[SIZE];
int top = -1;

// Push an element to the stack

void push(int value)
{
if (top == SIZE - 1)
{
printf("Stack Overflow\n");
return;
}
stack[++top] = value;
}

// Pop an element from the stack

int pop()
{
if (top == -1)
{
printf("Stack Underflow\n");
return -1;
}
return stack[top--];
}

// Function to evaluate Postfix expression

int evaluatePostfix(char *expression)
{
int i = 0;
int operand1, operand2, result;
while (expression[i])
{
if (isdigit(expression[i]))
{

Abhijeet Singh [Roll No: 02914202024] Page 54

 Data Structures and algorithms Lab [BCA-106P] 2025

push(expression[i] - '0'); // Push operand to stack

}
else if (expression[i] == '+' || expression[i] == '-' || expression[i] == '*' || expression[i] ==
'/')
{
operand2 = pop();
operand1 = pop();

switch (expression[i])
{
case '+':
result = operand1 + operand2;
break;
case '-':
result = operand1 - operand2;
break;
case '*':
result = operand1 * operand2;
break;
case '/':
result = operand1 / operand2;
break;
default:
result = 0;
break;
}

push(result);
}
i++;
}
return pop();
}
int evaluatePrefix(char *expression)
{
int i = strlen(expression) - 1;
int operand1, operand2, result;
while (i >= 0)
{
if (isdigit(expression[i]))
{
push(expression[i] - '0'); // Push operand to stack
}
else if (expression[i] == '+' || expression[i] == '-' || expression[i] == '*' || expression[i] ==
'/')
{
operand1 = pop();
operand2 = pop();
switch (expression[i])
{

Abhijeet Singh [Roll No: 02914202024] Page 55

 Data Structures and algorithms Lab [BCA-106P] 2025

case '+':
result = operand1 + operand2;
break;
case '-':
result = operand1 - operand2;
break;
case '*':
result = operand1 * operand2;
break;
case '/':
result = operand1 / operand2;
break;
default:
result = 0;
break;
}
push(result);
}
i--;
}
return pop();
}
int main()
{
char postfix[SIZE], prefix[SIZE];

printf("\t\t Name: Abhijeet Singh \t\t Roll No: 02914202024\n\n");

printf("Enter Postfix Expression: ");

scanf("%s", postfix);
printf("Postfix Evaluation Result: %d\n", evaluatePostfix(postfix));

printf("Enter Prefix Expression: ");

scanf("%s", prefix);
printf("Prefix Evaluation Result: %d\n", evaluatePrefix(prefix));

return 0;
}

Output:

/*Program 20: WAP to implement a (i) Static (ii) Dynamic Linear Queue
Abhijeet Singh [Roll No: 02914202024] Page 56
 Data Structures and algorithms Lab [BCA-106P] 2025

Name : Abhijeet Singh

Enroll. No : 02914202024
*/

Solution:

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

#define MAX 50

// Static Queue Variables

int queue[MAX], rear_s = -1, front_s = -1;

// Dynamic Queue
struct node {
int info;
struct node *link;
} *front_d = NULL, *rear_d = NULL;

void static_insert(), static_delete(), static_display();

void dynamic_insert(), dynamic_delete(), dynamic_display();

void main() {
int mode, ch;
printf("\t\t Name: Abhijeet Singh \t\t Roll No: 02914202024\n\n");

while (1) {
printf("\nChoose Queue Type:\n1. Static Linear Queue\n2. Dynamic Linear Queue\n3.
Exit\nEnter your choice: ");
scanf("%d", &mode);

switch (mode) {
case 1:
do {
printf("\nStatic Queue Menu:\n1. Insert\n2. Delete\n3. Display\n4. Back to Main
Menu\nEnter choice: ");
scanf("%d", &ch);
switch (ch) {
case 1: static_insert(); break;
case 2: static_delete(); break;
case 3: static_display(); break;
case 4: break;
default: printf("Invalid choice.\n");
}
} while (ch != 4);
break;

case 2:

Abhijeet Singh [Roll No: 02914202024] Page 57

 Data Structures and algorithms Lab [BCA-106P] 2025

do {
printf("\nDynamic Queue Menu:\n1. Insert\n2. Delete\n3. Display\n4. Back to
Main Menu\nEnter choice: ");
scanf("%d", &ch);
switch (ch) {
case 1: dynamic_insert(); break;
case 2: dynamic_delete(); break;
case 3: dynamic_display(); break;
case 4: break;
default: printf("Invalid choice.\n");
}
} while (ch != 4);
break;

case 3:
printf("Exiting program...\n");
exit(0);

default:
printf("Invalid choice.\n");
}
}
}

// Static Queue Functions

void static_insert() {
int item;
if (rear_s == MAX - 1) {
printf("Queue is full.\n");
} else {
printf("Enter ITEM to insert: ");
scanf("%d", &item);
if (front_s == -1) {
front_s = 0;
}
rear_s++;
queue[rear_s] = item;
printf("Inserted: %d\n", item);
}
}

void static_delete() {
if (front_s == -1 || front_s > rear_s) {
printf("Queue is empty.\n");
} else {
printf("Deleted: %d\n", queue[front_s]);
front_s++;
if (front_s > rear_s) front_s = rear_s = -1;
}
}

Abhijeet Singh [Roll No: 02914202024] Page 58

 Data Structures and algorithms Lab [BCA-106P] 2025

void static_display() {
if (front_s == -1) {
printf("Queue is empty.\n");
} else {
printf("Queue: ");
for (int i = front_s; i <= rear_s; i++)
printf("%d ", queue[i]);
printf("\n");
}
}

// Dynamic Queue Functions

void dynamic_insert() {
int item;
struct node *temp = (struct node *)malloc(sizeof(struct node));
if (!temp) {
printf("Memory allocation failed.\n");
return;
}

printf("Enter ITEM to insert: ");

scanf("%d", &item);
temp->info = item;
temp->link = NULL;

if (rear_d == NULL) {
front_d = rear_d = temp;
} else {
rear_d->link = temp;
rear_d = temp;
}

printf("Inserted: %d\n", item);

}

void dynamic_delete() {
if (front_d == NULL) {
printf("Queue is empty.\n");
} else {
struct node *temp = front_d;
int item = front_d->info;
front_d = front_d->link;
if (front_d == NULL)
rear_d = NULL;
free(temp);
printf("Deleted: %d\n", item);
}
}

Abhijeet Singh [Roll No: 02914202024] Page 59

 Data Structures and algorithms Lab [BCA-106P] 2025

void dynamic_display() {
struct node *temp = front_d;
if (temp == NULL) {
printf("Queue is empty.\n");
} else {
printf("Queue: ");
while (temp != NULL) {
printf("%d ", temp->info);
temp = temp->link;
}
printf("\n");
}
}
Output:

Abhijeet Singh [Roll No: 02914202024] Page 60

 Data Structures and algorithms Lab [BCA-106P] 2025

Abhijeet Singh [Roll No: 02914202024] Page 61

 Data Structures and algorithms Lab [BCA-106P] 2025

/*Program 21: WAP to implement a (i) Static (ii) Dynamic Circular Queue

Name : Abhijeet Singh

Enroll. No : 02914202024
*/

Solution:

1.Static Circular Queue

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

#define SIZE 5

void insert();
void delet();
void display();

int queue[SIZE], rear = -1, front = -1, item;

void main()
{
int ch;
printf("\t\t Name: Abhijeet Singh \t\t Roll No: 02914202024\n\n");
do
{
printf("\n1. Insert\n2. Delete\n3. Display\n4. Exit");
printf("\nEnter your choice: ");
scanf("%d", &ch);

switch(ch)
{
case 1: insert(); break;
case 2: delet(); break;
case 3: display(); break;
case 4: exit(0);
default: printf("\nInvalid choice. Please try again...");
}
}
while(1);
}

void insert()
{
if((front == 0 && rear == SIZE - 1) || (front == rear + 1))
{
printf("\nQueue is full.");
}
else

Abhijeet Singh [Roll No: 02914202024] Page 62

 Data Structures and algorithms Lab [BCA-106P] 2025

{
printf("\nEnter ITEM: ");
scanf("%d", &item);

if(rear == -1)
front = rear = 0;
else if(rear == SIZE - 1)
rear = 0;
else
rear++;

queue[rear] = item;
printf("Item inserted: %d", item);
}
}

void delet()
{
if(front == -1)
{
printf("\nQueue is empty.");
}
else
{
item = queue[front];
if(front == rear)
front = rear = -1;
else if(front == SIZE - 1)
front = 0;
else
front++;

printf("ITEM deleted: %d", item);

}
}

void display()
{
int i;
if(front == -1)
{
printf("\nQueue is empty.");
}
else
{
printf("\nQueue elements are: ");
if(front <= rear)
{
for(i = front; i <= rear; i++)
printf("%d ", queue[i]);

Abhijeet Singh [Roll No: 02914202024] Page 63

 Data Structures and algorithms Lab [BCA-106P] 2025

}
else
{
for(i = front; i < SIZE; i++)
printf("%d ", queue[i]);
for(i = 0; i <= rear; i++)
printf("%d ", queue[i]);
}
}
}

Output:

Abhijeet Singh [Roll No: 02914202024] Page 64

 Data Structures and algorithms Lab [BCA-106P] 2025

2.Dyanamic Circular Queue

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

void insert();
void delet();
void display();

int *queue, front = -1, rear = -1, size, item;

int main()
{
int ch;
printf("\t\t Name: Abhijeet Singh \t\t Roll No: 02914202024\n\n");

printf("Enter the size of queue: ");

scanf("%d", &size);
queue = (int *)malloc(size * sizeof(int));

if(queue == NULL)
{
printf("Memory allocation failed!");
return 1;
}

do
{
printf("\n1. Insert\n2. Delete\n3. Display\n4. Exit");
printf("\nEnter your choice: ");
scanf("%d", &ch);

switch(ch)
{
case 1: insert(); break;
case 2: delet(); break;
case 3: display(); break;
case 4: free(queue); exit(0);
default: printf("\nInvalid choice. Please try again...");
}
}
while(1);

return 0;
}

void insert()
{
if((front == 0 && rear == size - 1) || (rear + 1) % size == front)
{

Abhijeet Singh [Roll No: 02914202024] Page 65

 Data Structures and algorithms Lab [BCA-106P] 2025

printf("\nQueue is full.");
}
else
{
printf("\nEnter ITEM: ");
scanf("%d", &item);

if(rear == -1)
front = rear = 0;
else
rear = (rear + 1) % size;

queue[rear] = item;
printf("Item inserted: %d", item);
}
}

void delet()
{
if(front == -1)
{
printf("\nQueue is empty.");
}
else
{
item = queue[front];
if(front == rear)
front = rear = -1;
else
front = (front + 1) % size;

printf("ITEM deleted: %d", item);

}
}

void display()
{
int i;
if(front == -1)
{
printf("\nQueue is empty.");
}
else
{
printf("\nQueue elements are: ");
i = front;
while(1)
{
printf("%d ", queue[i]);
if(i == rear)

Abhijeet Singh [Roll No: 02914202024] Page 66

 Data Structures and algorithms Lab [BCA-106P] 2025

break;
i = (i + 1) % size;
}
}
}

Output:

Abhijeet Singh [Roll No: 02914202024] Page 67

 Data Structures and algorithms Lab [BCA-106P] 2025

/*Program 22: WAP to implement a (i) Static (ii) Dynamic De-Queue

Name : Abhijeet Singh
Enroll. No : 02914202024
*/

Solution:

1.Static De-Queue

#include <stdio.h>
#define MAX 10

int q[MAX], front = -1, rear = -1;

void add_rear();
void add_front();
void delete_rear();
void delete_front();
void display();

void main()
{
int ch;
printf("\t\t Name: Abhijeet Singh \t\t Roll No: 02914202024\n\n");

do
{
printf("\n D-Queue Menu");
printf("\n--------------");
printf("\n 1. AddRear");
printf("\n 2. AddFront");
printf("\n 3. DeleteRear");
printf("\n 4. DeleteFront");
printf("\n 5. Display");
printf("\n 6. Exit");
printf("\n--------------");

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

scanf("%d", &ch);

switch(ch)
{
case 1:
add_rear();
printf("\n Queue after insert at rear");
display();
break;

case 2:
add_front();

Abhijeet Singh [Roll No: 02914202024] Page 68

 Data Structures and algorithms Lab [BCA-106P] 2025

printf("\n Queue after insert at front");

display();
break;

case 3:
delete_rear();
printf("\n Queue after delete at rear");
display();
break;

case 4:
delete_front();
printf("\n Queue after delete at front");
display();
break;

case 5:
display();
break;

case 6:
exit(0);

default:
printf("\n Wrong Choice\n");
}
}
while(ch != 6);
}
void add_rear()
{
int no;
printf("\n Enter value to insert : ");
scanf("%d", &no);

if(rear == MAX - 1)
{
printf("\n Queue is Overflow");
return;
}
else
{
if(rear == -1)
rear = 0;
else
rear++;

if(front == -1)
front = 0;

Abhijeet Singh [Roll No: 02914202024] Page 69

 Data Structures and algorithms Lab [BCA-106P] 2025

q[rear] = no;
}
}

void add_front()
{
int no;
printf("\n Enter value to insert:-");
scanf("%d", &no);

if(front <= 0)
{
printf("\n Cannot add value at front end");
return;
}
else
{
front--;
q[front] = no;
}
}
void delete_front()
{
int no;
if(front == -1)
{
printf("\n Queue is Underflow\n");
return;
}
else
{
no = q[front];
printf("\n Deleted element is %d\n", no);

if(front == rear)
{
front = -1;
rear = -1;
}
else
{
front++;
}
}
}

void delete_rear()
{
int no;
if(rear == -1)

Abhijeet Singh [Roll No: 02914202024] Page 70

 Data Structures and algorithms Lab [BCA-106P] 2025

{
printf("\n Cannot delete value at rear end\n");
return;
}
else
{
no = q[rear];

if(front == rear)
{
front = -1;
rear = -1;
}
else
{
rear--;
}

printf("\n Deleted element is %d\n", no);

}
}
void display()
{
int i;
if(front == -1)
{
printf("\n Queue is Underflow\n");
return;
}
else
{
printf("\n Output");
for(i = front; i <= rear; i++)
{
printf("\n %d", q[i]);
}
}}

Abhijeet Singh [Roll No: 02914202024] Page 71

 Data Structures and algorithms Lab [BCA-106P] 2025

Output:

Abhijeet Singh [Roll No: 02914202024] Page 72

 Data Structures and algorithms Lab [BCA-106P] 2025

2.Dyanmic De-Queue

Solution:

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

struct node {
int data;
struct node *prev;
struct node *next;
};

struct dqueue {
struct node *front;
struct node *rear;
};

void initdqueue(struct dqueue *);

void addqatend(struct dqueue *, int item);
void addqatbeg(struct dqueue *, int item);
int delqatbeg(struct dqueue *);
int delqatend(struct dqueue *);
void display(struct dqueue);
int count(struct dqueue);
void deldqueue(struct dqueue *);

int main()
{
struct dqueue dq;
int i, n;

printf("\t\t Name: Abhijeet Singh \t\t Roll No: 02914202024\n\n");

initdqueue(&dq);

addqatend(&dq, 11);
addqatbeg(&dq, 10);
addqatend(&dq, 12);
addqatbeg(&dq, 9);
addqatend(&dq, 13);
addqatbeg(&dq, 8);
addqatend(&dq, 14);
addqatbeg(&dq, 7);

display(dq);

n = count(dq);
printf("\nTotal elements: %d", n);

Abhijeet Singh [Roll No: 02914202024] Page 73

 Data Structures and algorithms Lab [BCA-106P] 2025

i = delqatbeg(&dq);
printf("\nItem extracted = %d", i);

i = delqatbeg(&dq);
printf("\nItem extracted = %d", i);

i = delqatbeg(&dq);
printf("\nItem extracted = %d", i);

i = delqatend(&dq);
printf("\nItem extracted = %d", i);

display(dq);

n = count(dq);
printf("\nElements Left: %d\n", n);

deldqueue(&dq);

return 0;
}

void initdqueue(struct dqueue *p)

{
p->front = p->rear = NULL;
}

void addqatend(struct dqueue *p, int item)

{
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->data = item;

if (p->rear == NULL) {
temp->next = temp->prev = temp;
p->front = p->rear = temp;
} else {
temp->next = p->front;
temp->prev = p->rear;
p->rear->next = temp;
p->front->prev = temp;
p->rear = temp;
}
}

void addqatbeg(struct dqueue *p, int item)

{
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->data = item;

if (p->front == NULL) {

Abhijeet Singh [Roll No: 02914202024] Page 74

 Data Structures and algorithms Lab [BCA-106P] 2025

temp->next = temp->prev = temp;

p->front = p->rear = temp;
} else {
temp->next = p->front;
temp->prev = p->rear;
p->rear->next = temp;
p->front->prev = temp;
p->front = temp;
}
}

int delqatbeg(struct dqueue *p)

{
if (p->front == NULL) {
printf("\nQueue is empty.");
return 0;
}

int item = p->front->data;

struct node *temp = p->front;

if (p->front == p->rear) { // only one node

p->front = p->rear = NULL;
} else {
p->front = p->front->next;
p->front->prev = p->rear;
p->rear->next = p->front;
}

free(temp);
return item;
}

int delqatend(struct dqueue *p)

{
if (p->rear == NULL) {
printf("\nQueue is empty.");
return 0;
}

int item = p->rear->data;

struct node *temp = p->rear;

if (p->front == p->rear) {
p->front = p->rear = NULL;
} else {
p->rear = p->rear->prev;
p->rear->next = p->front;
p->front->prev = p->rear;
}

Abhijeet Singh [Roll No: 02914202024] Page 75

 Data Structures and algorithms Lab [BCA-106P] 2025

free(temp);
return item;
}

void display(struct dqueue dq)

{
struct node *temp = dq.front;
if (temp == NULL) {
printf("\nQueue is empty.");
return;
}

printf("\nfront -> ");

do {
if (temp->next == dq.front)
printf("%d <- rear", temp->data);
else
printf("%d -> ", temp->data);
temp = temp->next;
} while (temp != dq.front);
printf("\n");
}

int count(struct dqueue dq)

{
int c = 0;
struct node *temp = dq.front;
if (temp == NULL)
return 0;

do {
c++;
temp = temp->next;
} while (temp != dq.front);

return c;
}

void deldqueue(struct dqueue *p)

{
while (p->front != NULL)
delqatbeg(p);
}

Abhijeet Singh [Roll No: 02914202024] Page 76

 Data Structures and algorithms Lab [BCA-106P] 2025

Output:

Abhijeet Singh [Roll No: 02914202024] Page 77