DATA STRUCTURE CODES

#include <stdio.h>

#include <stdlib.h>

#define MAX 5

int top = -1;

int stack_arr[MAX]; // Define the stack array

// Function prototypes

void push();

void pop();

void display();

int 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(0); // Use exit(0) to indicate successful program termination

default:

printf("Wrong choice\n");

} /*end of switch */

} /*end of while */

} /*end of main() */

void push() {

int pushed_item;

if (top == (MAX - 1)) {

printf("Stack overflow\n");

} else {

printf("Enter item to be pushed in stack: ");

scanf("%d", &pushed_item);

top = top + 1;

stack_arr[top] = pushed_item;

} /*end of push */

void pop() {

if (top == -1) {

printf("Stack underflow\n");

} else {

printf("Popped element is: %d\n", stack_arr[top]);

top = top - 1;
 }

void 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() */

INFIX TO POSTFIX

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define MAX 100

// Define the stack data structure

struct Stack {

int top;

char items[MAX];

};

// Function to initialize the stack

void initialize(struct Stack* stack) {

 stack->top = -1;

// Function to check if the stack is empty

int isEmpty(struct Stack* stack) {

return stack->top == -1;

// Function to push an item onto the stack

void push(struct Stack* stack, char item) {

if (stack->top == MAX - 1) {

printf("Stack overflow\n");

} else {

stack->items[++stack->top] = item;

// Function to pop an item from the stack

char pop(struct Stack* stack) {

if (isEmpty(stack)) {

printf("Stack underflow\n");

return '\0';

} else {

return stack->items[stack->top--];

// Function to return the precedence of an operator

int precedence(char op) {

if (op == '+' || op == '-')

return 1;
 if (op == '*' || op == '/')

return 2;

return 0; // Default precedence

// Function to convert infix expression to postfix expression

void infixToPostfix(char* infix) {

struct Stack stack;

initialize(&stack);

int i, j;

char postfix[MAX];

i = j = 0;

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

char token = infix[i];

if (isalnum(token)) {

postfix[j++] = token; // Append operand to postfix expression

} else if (token == '(') {

push(&stack, token); // Push an open parenthesis onto the stack

} else if (token == ')') {

while (!isEmpty(&stack) && stack.items[stack.top] != '(') {

postfix[j++] = pop(&stack); // Pop and append operators to postfix until an open parenthesis
is encountered

if (!isEmpty(&stack) && stack.items[stack.top] == '(') {

pop(&stack); // Pop the open parenthesis

} else {

while (!isEmpty(&stack) && precedence(stack.items[stack.top]) >= precedence(token)) {

postfix[j++] = pop(&stack); // Pop and append operators to postfix with higher or equal
precedence
 }

push(&stack, token); // Push the current operator onto the stack

i++;

while (!isEmpty(&stack)) {

postfix[j++] = pop(&stack); // Pop and append remaining operators to postfix

postfix[j] = '\0'; // Null-terminate the postfix expression

printf("Postfix Expression: %s\n", postfix);

int main() {

char infix[MAX];

printf("Enter an infix expression: ");

scanf("%s", infix);

infixToPostfix(infix);

return 0;

char* infixToPostfix(char* infix){

struct stack * sp = (struct stack *) malloc(sizeof(struct stack));

sp->size = 10;

sp->top = -1;

sp->arr = (char *) malloc(sp->size * sizeof(char));

char * postfix = (char *) malloc((strlen(infix)+1) * sizeof(char));

int i=0; // Track infix traversal

int j = 0; // Track postfix addition

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

if(!isOperator(infix[i])){

postfix[j] = infix[i];

j++;

i++;

else{

if(precedence(infix[i])> precedence(stackTop(sp))){

push(sp, infix[i]);

i++;

else{

postfix[j] = pop(sp);

j++;

while (!isEmpty(sp))

postfix[j] = pop(sp);

j++;

postfix[j] = '\0';

return postfix;

3. Evaluate postfix expression using Stack ADT

#include <stdio.h>

#include <stdlib.h>

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

// Structure to represent the stack

struct Stack {

int top;

unsigned capacity;

int* array;

};

// Function to create a new stack

struct Stack* createStack(unsigned capacity) {

struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));

stack->capacity = capacity;

stack->top = -1;

stack->array = (int*)malloc(stack->capacity * sizeof(int));

return stack;

// Function to push an element onto the stack

void push(struct Stack* stack, int item) {

stack->array[++stack->top] = item;

// Function to pop an element from the stack

int pop(struct Stack* stack) {

return stack->array[stack->top--];

// Function to evaluate a postfix expression

int evaluatePostfix(char* expression) {

struct Stack* stack = createStack(strlen(expression));

 if (!stack) return -1;

for (int i = 0; expression[i]; i++) {

if (isdigit(expression[i]))

push(stack, expression[i] - '0');

else {

int operand2 = pop(stack);

int operand1 = pop(stack);

switch (expression[i]) {

case '+':

push(stack, operand1 + operand2);

break;

case '-':

push(stack, operand1 - operand2);

break;

case '*':

push(stack, operand1 * operand2);

break;

case '/':

push(stack, operand1 / operand2);

break;

return pop(stack);

int main() {

char expression[100];

printf("Enter a postfix expression: ");

gets(expression);
 int result = evaluatePostfix(expression);

if (result != -1)

printf("Result: %d\n", result);

else

printf("Invalid expression or memory allocation error.\n");

return 0;

4. Implement Queue ADT using arrays

#include <stdio.h>

#include <stdlib.h>

#define MAX_SIZE 100

struct Queue {

int front, rear, size;

int array[MAX_SIZE];

};

struct Queue* createQueue() {

struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue));

if (!queue) {

return NULL; // Check for memory allocation failure

queue->front = queue->size = 0;

queue->rear = -1;

return queue;

}
int isFull(struct Queue* queue) {

return (queue->size == MAX_SIZE);

int isEmpty(struct Queue* queue) {

return (queue->size == 0);

void enqueue(struct Queue* queue, int item) {

if (isFull(queue)) {

printf("Queue is full. Cannot enqueue.\n");

return;

queue->rear = (queue->rear + 1) % MAX_SIZE;

queue->array[queue->rear] = item;

queue->size++;

printf("%d enqueued to the queue.\n", item);

int dequeue(struct Queue* queue) {

if (isEmpty(queue)) {

printf("Queue is empty. Cannot dequeue.\n");

return -1; // You can choose a different value for an empty queue

int item = queue->array[queue->front];

queue->front = (queue->front + 1) % MAX_SIZE;

queue->size--;

return item;

int front(struct Queue* queue) {

 if (isEmpty(queue)) {

printf("Queue is empty. No front element.\n");

return -1; // You can choose a different value for an empty queue

return queue->array[queue->front];

int main() {

struct Queue* queue = createQueue();

int choice, item;

while (1) {

printf("Choose an operation:\n");

printf("1. Enqueue\n2. Dequeue\n3. Front\n4. Exit\n");

scanf("%d", &choice);

switch (choice) {

case 1:

printf("Enter an element to enqueue: ");

scanf("%d", &item);

enqueue(queue, item);

break;

case 2:

item = dequeue(queue);

if (item != -1) {

printf("%d dequeued from the queue.\n", item);

break;

case 3:
 item = front(queue);

if (item != -1) {

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

break;

case 4:

free(queue);

exit(0);

default:

printf("Invalid choice. Try again.\n");

return 0;

5.Implement Circular Queue ADT using arrays

#include <stdio.h>

#include <stdlib.h>

#define MAX_SIZE 100

// Define a structure for the circular queue

struct CircularQueue {

int front, rear, size;

int data[MAX_SIZE];

};

// Initialize an empty circular queue

void init(struct CircularQueue* queue) {

queue->front = queue->rear = -1;

queue->size = 0;

// Check if the circular queue is empty

int isEmpty(struct CircularQueue* queue) {

return (queue->size == 0);

// Check if the circular queue is full

int isFull(struct CircularQueue* queue) {

return (queue->size == MAX_SIZE);

// Add an element to the circular queue

void enqueue(struct CircularQueue* queue, int value) {

if (isFull(queue)) {

printf("Queue is full!\n");

exit(1);

if (isEmpty(queue)) {

queue->front = queue->rear = 0;

} else {

queue->rear = (queue->rear + 1) % MAX_SIZE; // Circular wrapping

queue->data[queue->rear] = value;

queue->size++;

// Remove and return the element from the front of the circular queue
int dequeue(struct CircularQueue* queue) {

if (isEmpty(queue)) {

printf("Queue is empty!\n");

exit(1);

int value = queue->data[queue->front];

if (queue->front == queue->rear) {

queue->front = queue->rear = -1;

} else {

queue->front = (queue->front + 1) % MAX_SIZE; // Circular wrapping

queue->size--;

return value;

// Get the element at the front of the circular queue without removing it

int front(struct CircularQueue* queue) {

if (isEmpty(queue)) {

printf("Queue is empty!\n");

exit(1);

return queue->data[queue->front];

int main() {

struct CircularQueue queue;

init(&queue);

enqueue(&queue, 10);

enqueue(&queue, 20);

enqueue(&queue, 30);
 printf("Front element: %d\n", front(&queue));

printf("Dequeued: %d\n", dequeue(&queue));

printf("Dequeued: %d\n", dequeue(&queue));

enqueue(&queue, 40);

printf("Front element: %d\n", front(&queue));

return 0;

Implement following operations of Singly Linked List

ADT
a. Create Linked List with n nodes

b. Insert at beginning

c. Insert at end

d. Insert before specified node

e. Display (Forward Traversal

#include <stdio.h>

#include <stdlib.h>

// Define the structure for a singly linked list node

struct Node {

int data;

struct Node* next;

};

// Function to create a linked list with n nodes

struct Node* createList(int n) {

struct Node* head = NULL;

struct Node* temp = NULL;

struct Node* newNode = NULL;

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

newNode = (struct Node*)malloc(sizeof(struct Node));

if (newNode == NULL) {

printf("Memory allocation failed!\n");

exit(1);

printf("Enter data for node %d: ", i + 1);

scanf("%d", &newNode->data);

newNode->next = NULL;

if (head == NULL) {

head = newNode;

temp = newNode;

} else {

temp->next = newNode;

temp = newNode;

return head;

// Function to insert a node at the beginning

struct Node* insertAtBeginning(struct Node* head, int data) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

 if (newNode == NULL) {

printf("Memory allocation failed!\n");

exit(1);

newNode->data = data;

newNode->next = head;

return newNode;

// Function to insert a node at the end

struct Node* insertAtEnd(struct Node* head, int data) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

if (newNode == NULL) {

printf("Memory allocation failed!\n");

exit(1);

newNode->data = data;

newNode->next = NULL;

if (head == NULL) {

return newNode;

struct Node* temp = head;

while (temp->next != NULL) {

temp = temp->next;

temp->next = newNode;
 return head;

// Function to insert a node before a specified node

struct Node* insertBeforeNode(struct Node* head, int data, int key) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

if (newNode == NULL) {

printf("Memory allocation failed!\n");

exit(1);

newNode->data = data;

if (head == NULL) {

return newNode;

if (head->data == key) {

newNode->next = head;

return newNode;

struct Node* prev = NULL;

struct Node* current = head;

while (current != NULL && current->data != key) {

prev = current;

current = current->next;

if (current == NULL) {
 printf("Node with key %d not found!\n", key);

free(newNode);

return head;

prev->next = newNode;

newNode->next = current;

return head;

// Function to display the linked list (forward traversal)

void display(struct Node* head) {

struct Node* current = head;

if (current == NULL) {

printf("The list is empty.\n");

return;

printf("Linked List (Forward Traversal):\n");

while (current != NULL) {

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

current = current->next;

printf("NULL\n");

// Function to free the memory used by the linked list

void freeList(struct Node* head) {

struct Node* current = head;

 while (current != NULL) {

struct Node* temp = current;

current = current->next;

free(temp);

int main() {

struct Node* head = NULL;

int n, data, key;

printf("Enter the number of nodes: ");

scanf("%d", &n);

if (n > 0) {

head = createList(n);

display(head);

printf("Enter data to insert at the beginning: ");

scanf("%d", &data);

head = insertAtBeginning(head, data);

display(head);

printf("Enter data to insert at the end: ");

scanf("%d", &data);

head = insertAtEnd(head, data);

display(head);

printf("Enter data to insert before a specified node: ");

scanf("%d", &data);

printf("Enter the key of the node before which to insert: ");

 scanf("%d", &key);

head = insertBeforeNode(head, data, key);

display(head);

} else {

printf("Invalid number of nodes.\n");

freeList(head);

return 0;

10. Implement following operations of Circular Linked

List ADT
a. Create list with n nodes

b. Insert at beginning

c. Insert at end

d. Display (Forward Traversal)

#include <stdio.h>

#include <stdlib.h>

// Define the structure for a singly linked list node

struct Node {

int data;

struct Node* next;

};

// Function to create a linked list with n nodes

struct Node* createList(int n) {

struct Node* head = NULL;

 struct Node* temp = NULL;

struct Node* newNode = NULL;

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

newNode = (struct Node*)malloc(sizeof(struct Node));

if (newNode == NULL) {

printf("Memory allocation failed!\n");

exit(1);

printf("Enter data for node %d: ", i + 1);

scanf("%d", &newNode->data);

newNode->next = NULL;

if (head == NULL) {

head = newNode;

temp = newNode;

} else {

temp->next = newNode;

temp = newNode;

return head;

// Function to delete a node at the beginning

struct Node* deleteAtBeginning(struct Node* head) {

if (head == NULL) {

printf("The list is empty. Nothing to delete.\n");

} else {
 struct Node* temp = head;

head = head->next;

free(temp);

return head;

// Function to delete a node at the end

struct Node* deleteAtEnd(struct Node* head) {

if (head == NULL) {

printf("The list is empty. Nothing to delete.\n");

} else if (head->next == NULL) {

free(head);

head = NULL;

} else {

struct Node* current = head;

struct Node* prev = NULL;

while (current->next != NULL) {

prev = current;

current = current->next;

prev->next = NULL;

free(current);

return head;

// Function to delete a node before a specified node

struct Node* deleteBeforeNode(struct Node* head, int key) {

if (head == NULL) {

printf("The list is empty. Nothing to delete.\n");

 return head;

if (head->data == key) {

printf("The first node cannot be deleted using deleteBeforeNode.\n");

return head;

struct Node* prev = NULL;

struct Node* current = head;

while (current != NULL && current->data != key) {

prev = current;

current = current->next;

if (current == NULL) {

printf("Node with key %d not found!\n", key);

} else {

if (prev->next == current) {

prev->next = current->next;

free(current);

return head;

// Function to display the linked list (forward traversal)

void display(struct Node* head) {

struct Node* current = head;

 if (current == NULL) {

printf("The list is empty.\n");

return;

printf("Linked List (Forward Traversal):\n");

while (current != NULL) {

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

current = current->next;

printf("NULL\n");

// Function to free the memory used by the linked list

void freeList(struct Node* head) {

struct Node* current = head;

while (current != NULL) {

struct Node* temp = current;

current = current->next;

free(temp);

int main() {

struct Node* head = NULL;

int n, key;

printf("Enter the number of nodes: ");

scanf("%d", &n);

if (n > 0) {
 head = createList(n);

display(head);

head = deleteAtBeginning(head);

display(head);

head = deleteAtEnd(head);

display(head);

printf("Enter the key of the node before which to delete: ");

scanf("%d", &key);

head = deleteBeforeNode(head, key);

display(head);

} else {

printf("Invalid number of nodes.\n");

freeList(head);

return 0;

11. Implement following operations of Circular Linked

List ADT
a. Create list with n nodes

b. Delete at beginning

c. Delete at end

d. Display (Forward Traversal)

#include <stdio.h>

#include <stdlib.h>
// Define the structure for a circular linked list node

struct Node {

int data;

struct Node* next;

};

// Function to create a circular linked list with n nodes

struct Node* createCircularList(int n) {

struct Node* head = NULL;

struct Node* temp = NULL;

struct Node* newNode = NULL;

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

newNode = (struct Node*)malloc(sizeof(struct Node));

if (newNode == NULL) {

printf("Memory allocation failed!\n");

exit(1);

printf("Enter data for node %d: ", i + 1);

scanf("%d", &newNode->data);

newNode->next = NULL;

if (head == NULL) {

head = newNode;

newNode->next = head; // Circular linkage

} else {

temp->next = newNode;

newNode->next = head; // Circular linkage

}
 temp = newNode;

return head;

// Function to delete a node at the beginning of a circular linked list

struct Node* deleteAtBeginning(struct Node* head) {

if (head == NULL) {

printf("The list is empty. Nothing to delete.\n");

} else {

struct Node* temp = head;

struct Node* lastNode = head;

while (lastNode->next != head) {

lastNode = lastNode->next;

lastNode->next = head->next; // Update the last node to point to the new head

head = head->next; // Move the head to the next node

free(temp);

return head;

// Function to delete a node at the end of a circular linked list

struct Node* deleteAtEnd(struct Node* head) {

if (head == NULL) {

printf("The list is empty. Nothing to delete.\n");

} else {
 struct Node* current = head;

struct Node* previous = NULL;

while (current->next != head) {

previous = current;

current = current->next;

if (previous != NULL) {

previous->next = head; // Update the previous node to point to the new head

} else {

head = NULL; // If there was only one node, set the head to NULL

free(current);

return head;

// Function to display the circular linked list (forward traversal)

void display(struct Node* head) {

if (head == NULL) {

printf("The list is empty.\n");

return;

struct Node* current = head;

printf("Circular Linked List (Forward Traversal):\n");

do {
 printf("%d -> ", current->data);

current = current->next;

} while (current != head);

printf("...\n"); // Indicates circular linkage

// Function to free the memory used by the circular linked list

void freeCircularList(struct Node* head) {

if (head == NULL) {

return;

struct Node* current = head;

struct Node* temp = NULL;

do {

temp = current;

current = current->next;

free(temp);

} while (current != head);

int main() {

struct Node* head = NULL;

int n;

printf("Enter the number of nodes: ");

scanf("%d", &n);

if (n > 0) {
 head = createCircularList(n);

display(head);

head = deleteAtBeginning(head);

display(head);

head = deleteAtEnd(head);

display(head);

} else {

printf("Invalid number of nodes.\n");

freeCircularList(head);

return 0;

12. Implement following operations of Circular Linked

List ADT
a. Create list for n nodes

b. Insert at beginning

c. Delete at end

d. Count no of nodes

e. Display (Forward Traversal)

#include <stdio.h>

#include <stdlib.h>

// Define the structure for a circular linked list node

struct Node {

int data;
 struct Node* next;

};

// Function to create a circular linked list with n nodes

struct Node* createCircularList(int n) {

struct Node* head = NULL;

struct Node* temp = NULL;

struct Node* newNode = NULL;

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

newNode = (struct Node*)malloc(sizeof(struct Node));

if (newNode == NULL) {

printf("Memory allocation failed!\n");

exit(1);

printf("Enter data for node %d: ", i + 1);

scanf("%d", &newNode->data);

newNode->next = NULL;

if (head == NULL) {

head = newNode;

newNode->next = head; // Circular linkage

} else {

temp->next = newNode;

newNode->next = head; // Circular linkage

temp = newNode;

return head;
}

// Function to insert a node at the beginning of a circular linked list

struct Node* insertAtBeginning(struct Node* head, int data) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

if (newNode == NULL) {

printf("Memory allocation failed!\n");

exit(1);

newNode->data = data;

if (head == NULL) {

head = newNode;

newNode->next = head;

} else {

struct Node* temp = head;

while (temp->next != head) {

temp = temp->next;

newNode->next = head;

temp->next = newNode;

head = newNode;

return head;

// Function to delete a node at the end of a circular linked list

struct Node* deleteAtEnd(struct Node* head) {

 if (head == NULL) {

printf("The list is empty. Nothing to delete.\n");

return head;

if (head->next == head) {

free(head);

return NULL;

struct Node* temp = head;

struct Node* prev = NULL;

while (temp->next != head) {

prev = temp;

temp = temp->next;

prev->next = head;

free(temp);

return head;

// Function to count the number of nodes in a circular linked list

int countNodes(struct Node* head) {

if (head == NULL) {

return 0;

int count = 0;
 struct Node* current = head;

do {

count++;

current = current->next;

} while (current != head);

return count;

// Function to display the circular linked list (forward traversal)

void display(struct Node* head) {

if (head == NULL) {

printf("The list is empty.\n");

return;

struct Node* current = head;

printf("Circular Linked List (Forward Traversal):\n");

do {

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

current = current->next;

} while (current != head);

printf("...\n"); // Indicates circular linkage

// Function to free the memory used by the circular linked list

void freeCircularList(struct Node* head) {

if (head == NULL) {
 return;

struct Node* current = head;

struct Node* temp = NULL;

do {

temp = current;

current = current->next;

free(temp);

} while (current != head);

int main() {

struct Node* head = NULL;

int n;

printf("Enter the number of nodes: ");

scanf("%d", &n);

if (n > 0) {

head = createCircularList(n);

display(head);

int dataToInsert;

printf("Enter data to insert at the beginning: ");

scanf("%d", &dataToInsert);

head = insertAtBeginning(head, dataToInsert);

display(head);

int nodesToDelete;
 printf("Enter the number of nodes to delete at the end: ");

scanf("%d", &nodesToDelete);

for (int i = 0; i < nodesToDelete; i++) {

head = deleteAtEnd(head);

display(head);

int nodeCount = countNodes(head);

printf("Number of nodes in the circular linked list: %d\n", nodeCount);

} else {

printf("Invalid number of nodes.\n");

freeCircularList(head);

return 0;

Implement Stack ADT using Linked List

#include <stdio.h>

#include <stdlib.h>

// Define the structure for a node in the linked list

struct Node {

int data;

struct Node* next;

};

// Define the structure for the stack

struct Stack {
 struct Node* top;

};

// Function to create an empty stack

struct Stack* createStack() {

struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));

if (stack == NULL) {

printf("Memory allocation failed!\n");

exit(1);

stack->top = NULL;

return stack;

// Function to check if the stack is empty

int isEmpty(struct Stack* stack) {

return (stack->top == NULL);

// Function to push an element onto the stack

void push(struct Stack* stack, int data) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

if (newNode == NULL) {

printf("Memory allocation failed!\n");

exit(1);

newNode->data = data;

newNode->next = stack->top;

stack->top = newNode;

}
// Function to pop an element from the stack

int pop(struct Stack* stack) {

if (isEmpty(stack)) {

printf("Stack is empty. Cannot pop.\n");

exit(1);

struct Node* temp = stack->top;

int data = temp->data;

stack->top = temp->next;

free(temp);

return data;

// Function to get the top element of the stack without popping it

int peek(struct Stack* stack) {

if (isEmpty(stack)) {

printf("Stack is empty. No top element.\n");

exit(1);

return stack->top->data;

// Function to display the elements of the stack

void display(struct Stack* stack) {

struct Node* current = stack->top;

if (isEmpty(stack)) {

printf("Stack is empty.\n");

return;

printf("Stack elements: ");

while (current != NULL) {

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

current = current->next;

printf("\n");

// Function to free the memory used by the stack

void freeStack(struct Stack* stack) {

while (!isEmpty(stack)) {

pop(stack);

free(stack);

int main() {

struct Stack* stack = createStack();

push(stack, 10);

push(stack, 20);

push(stack, 30);

display(stack);

printf("Top element: %d\n", peek(stack));

pop(stack);

display(stack);

freeStack(stack);

return 0;
}

14. Implement Queue ADT using Linked List

#include <stdio.h>

#include <stdlib.h>

// Define the structure for a node in the linked list

struct Node {

int data;

struct Node* next;

};

// Define the structure for the stack

struct Stack {

struct Node* top;

};

// Function to create an empty stack

struct Stack* createStack() {

struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));

if (stack == NULL) {

printf("Memory allocation failed!\n");

exit(1);

stack->top = NULL;

return stack;

// Function to check if the stack is empty

int isEmpty(struct Stack* stack) {

 return (stack->top == NULL);

// Function to push an element onto the stack

void push(struct Stack* stack, int data) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

if (newNode == NULL) {

printf("Memory allocation failed!\n");

exit(1);

newNode->data = data;

newNode->next = stack->top;

stack->top = newNode;

// Function to pop an element from the stack

int pop(struct Stack* stack) {

if (isEmpty(stack)) {

printf("Stack is empty. Cannot pop.\n");

exit(1);

struct Node* temp = stack->top;

int data = temp->data;

stack->top = temp->next;

free(temp);

return data;

// Function to get the top element of the stack without popping it

int peek(struct Stack* stack) {

if (isEmpty(stack)) {
 printf("Stack is empty. No top element.\n");

exit(1);

return stack->top->data;

// Function to display the elements of the stack

void display(struct Stack* stack) {

struct Node* current = stack->top;

if (isEmpty(stack)) {

printf("Stack is empty.\n");

return;

printf("Stack elements: ");

while (current != NULL) {

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

current = current->next;

printf("\n");

// Function to free the memory used by the stack

void freeStack(struct Stack* stack) {

while (!isEmpty(stack)) {

pop(stack);

free(stack);

int main() {

struct Stack* stack = createStack();

 push(stack, 10);

push(stack, 20);

push(stack, 30);

display(stack);

printf("Top element: %d\n", peek(stack));

pop(stack);

display(stack);

freeStack(stack);

return 0;

15. Implement following operations of Binary Search

Tree using Linked List
a. Insertion

b. Searching

c. Traversal (Preorder)

d. Count total no of nodes

#include <stdio.h>

#include <stdlib.h>

// Structure for a BST node

struct Node {

int data;

struct Node* left;

struct Node* right;

};

// Function to create a new BST node

struct Node* createNode(int key) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

newNode->data = key;

newNode->left = newNode->right = NULL;

return newNode;

// Function to insert a node into the BST

struct Node* insert(struct Node* root, int key) {

if (root == NULL) {

return createNode(key);

if (key < root->data) {

root->left = insert(root->left, key);

} else if (key > root->data) {

root->right = insert(root->right, key);

return root;

// Function to find the minimum value node in a BST

struct Node* findMin(struct Node* root) {

while (root->left != NULL) {

root = root->left;

return root;

}
// Function to delete a node with a given key from the BST

struct Node* deleteNode(struct Node* root, int key) {

if (root == NULL) return root;

if (key < root->data) {

root->left = deleteNode(root->left, key);

} else if (key > root->data) {

root->right = deleteNode(root->right, key);

} else {

if (root->left == NULL) {

struct Node* temp = root->right;

free(root);

return temp;

} else if (root->right == NULL) {

struct Node* temp = root->left;

free(root);

return temp;

struct Node* temp = findMin(root->right);

root->data = temp->data;

root->right = deleteNode(root->right, temp->data);

return root;

// Function to search for a key in the BST

struct Node* search(struct Node* root, int key) {

if (root == NULL || root->data == key) return root;

if (key < root->data) return search(root->left, key);

 return search(root->right, key);

// Function to perform in-order traversal of the BST

void inOrderTraversal(struct Node* root) {

if (root != NULL) {

inOrderTraversal(root->left);

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

inOrderTraversal(root->right);

// Function to perform pre-order traversal of the BST

void preOrderTraversal(struct Node* root) {

if (root != NULL) {

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

preOrderTraversal(root->left);

preOrderTraversal(root->right);

// Function to perform post-order traversal of the BST

void postOrderTraversal(struct Node* root) {

if (root != NULL) {

postOrderTraversal(root->left);

postOrderTraversal(root->right);

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

int main() {
 struct Node* root = NULL;

int choice, key;

while (1) {

printf("Choose an operation:\n");

printf("1. Insert\n2. Delete\n3. Search\n4. In-order Traversal\n5. Pre-order Traversal\n6. Post-

order Traversal\n7. Exit\n");

scanf("%d", &choice);

switch (choice) {

case 1:

printf("Enter a key to insert: ");

scanf("%d", &key);

root = insert(root, key);

break;

case 2:

printf("Enter a key to delete: ");

scanf("%d", &key);

root = deleteNode(root, key);

break;

case 3:

printf("Enter a key to search: ");

scanf("%d", &key);

if (search(root, key) != NULL) {

printf("Key found in the BST.\n");

} else {

printf("Key not found in the BST.\n");

break;
 case 4:

printf("In-order Traversal: ");

inOrderTraversal(root);

printf("\n");

break;

case 5:

printf("Pre-order Traversal: ");

preOrderTraversal(root);

printf("\n");

break;

case 6:

printf("Post-order Traversal: ");

postOrderTraversal(root);

printf("\n");

break;

case 7:

// Free memory and exit

free(root);

exit(0);

default:

printf("Invalid choice. Try again.\n");

return 0;

}
16. Implement following operations of Binary Search
Tree using Linked List
a. Insertion

b. Deletion

c. Traversal (Inorder)

#include <stdio.h>

#include <stdlib.h>

// Structure for a BST node

struct Node {

int data;

struct Node* left;

struct Node* right;

};

// Function to create a new BST node

struct Node* createNode(int key) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

newNode->data = key;

newNode->left = newNode->right = NULL;

return newNode;

// Function to insert a node into the BST

struct Node* insert(struct Node* root, int key) {

if (root == NULL) {

return createNode(key);

if (key < root->data) {

 root->left = insert(root->left, key);

} else if (key > root->data) {

root->right = insert(root->right, key);

return root;

// Function to find the minimum value node in a BST

struct Node* findMin(struct Node* root) {

while (root->left != NULL) {

root = root->left;

return root;

// Function to delete a node with a given key from the BST

struct Node* deleteNode(struct Node* root, int key) {

if (root == NULL) return root;

if (key < root->data) {

root->left = deleteNode(root->left, key);

} else if (key > root->data) {

root->right = deleteNode(root->right, key);

} else {

if (root->left == NULL) {

struct Node* temp = root->right;

free(root);

return temp;

} else if (root->right == NULL) {

struct Node* temp = root->left;

free(root);
 return temp;

struct Node* temp = findMin(root->right);

root->data = temp->data;

root->right = deleteNode(root->right, temp->data);

return root;

// Function to perform in-order traversal of the BST

void inOrderTraversal(struct Node* root) {

if (root != NULL) {

inOrderTraversal(root->left);

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

inOrderTraversal(root->right);

int main() {

struct Node* root = NULL;

int choice, key;

while (1) {

printf("Choose an operation:\n");

printf("1. Insert\n2. Delete\n3. In-order Traversal\n4. Exit\n");

scanf("%d", &choice);

switch (choice) {

case 1:

printf("Enter a key to insert: ");

 scanf("%d", &key);

root = insert(root, key);

break;

case 2:

printf("Enter a key to delete: ");

scanf("%d", &key);

root = deleteNode(root, key);

break;

case 3:

printf("In-order Traversal: ");

inOrderTraversal(root);

printf("\n");

break;

case 4:

// Free memory and exit

free(root);

exit(0);

default:

printf("Invalid choice. Try again.\n");

return 0;

17. Implement following operations of Binary Search

Tree using Linked List
a. Insertion

b. Traversal ( Postorder)

c. Count total no of internal nodes

d. Count total no of leaf nodes

e. Height of the tree

#include <stdio.h>

#include <stdlib.h>

// Define the structure for a BST node

struct TreeNode {

int data;

struct TreeNode* left;

struct TreeNode* right;

};

// Function to create a new BST node

struct TreeNode* createNode(int data) {

struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));

if (newNode == NULL) {

printf("Memory allocation failed!\n");

exit(1);

newNode->data = data;

newNode->left = NULL;

newNode->right = NULL;

return newNode;

// Function to insert a node into the BST

struct TreeNode* insert(struct TreeNode* root, int data) {

if (root == NULL) {
 return createNode(data);

if (data < root->data) {

root->left = insert(root->left, data);

} else if (data > root->data) {

root->right = insert(root->right, data);

return root;

// Function to perform a postorder traversal of the BST

void postorderTraversal(struct TreeNode* root) {

if (root == NULL) {

return;

postorderTraversal(root->left);

postorderTraversal(root->right);

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

// Function to count the total number of internal nodes in the BST

int countInternalNodes(struct TreeNode* root) {

if (root == NULL || (root->left == NULL && root->right == NULL)) {

return 0;

return 1 + countInternalNodes(root->left) + countInternalNodes(root->right);

}
// Function to count the total number of leaf nodes in the BST

int countLeafNodes(struct TreeNode* root) {

if (root == NULL) {

return 0;

if (root->left == NULL && root->right == NULL) {

return 1;

return countLeafNodes(root->left) + countLeafNodes(root->right);

// Function to calculate the height of the tree

int treeHeight(struct TreeNode* root) {

if (root == NULL) {

return 0;

int leftHeight = treeHeight(root->left);

int rightHeight = treeHeight(root->right);

// Height of the tree is the maximum of left and right subtree heights, plus 1 for the current node.

return (leftHeight > rightHeight) ? leftHeight + 1 : rightHeight + 1;

int main() {

struct TreeNode* root = NULL;

root = insert(root, 50);

 root = insert(root, 30);

root = insert(root, 70);

root = insert(root, 20);

root = insert(root, 40);

root = insert(root, 60);

root = insert(root, 80);

printf("Postorder Traversal: ");

postorderTraversal(root);

printf("\n");

int internalNodeCount = countInternalNodes(root);

printf("Total number of internal nodes: %d\n", internalNodeCount);

int leafNodeCount = countLeafNodes(root);

printf("Total number of leaf nodes: %d\n", leafNodeCount);

int height = treeHeight(root);

printf("Height of the tree: %d\n", height);

return 0;

18. Implement following operations of Binary Search

Tree using Linked List
a. Insertion

b. Traversal (Preorder, Inorder, Postorder)

c. Height of the tree

#include <stdio.h>

#include <stdlib.h>
// Structure for a BST node

struct Node {

int data;

struct Node *left;

struct Node *right;

};

// Function to create a new BST node

struct Node* createNode(int data) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

newNode->data = data;

newNode->left = newNode->right = NULL;

return newNode;

// Function to insert a new node into the BST

struct Node* insert(struct Node* root, int data) {

if (root == NULL) {

return createNode(data);

if (data < root->data) {

root->left = insert(root->left, data);

} else if (data > root->data) {

root->right = insert(root->right, data);

return root;

}
// Function to perform an inorder traversal

void inorderTraversal(struct Node* root) {

if (root != NULL) {

inorderTraversal(root->left);

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

inorderTraversal(root->right);

// Function to perform a preorder traversal

void preorderTraversal(struct Node* root) {

if (root != NULL) {

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

preorderTraversal(root->left);

preorderTraversal(root->right);

// Function to perform a postorder traversal

void postorderTraversal(struct Node* root) {

if (root != NULL) {

postorderTraversal(root->left);

postorderTraversal(root->right);

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

// Function to calculate the height of the BST

int height(struct Node* root) {

if (root == NULL) {

return 0;
 }

int leftHeight = height(root->left);

int rightHeight = height(root->right);

return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;

int main() {

struct Node* root = NULL;

root = insert(root, 50);

root = insert(root, 30);

root = insert(root, 70);

root = insert(root, 20);

root = insert(root, 40);

root = insert(root, 60);

root = insert(root, 80);

printf("Inorder traversal: ");

inorderTraversal(root);

printf("\n");

printf("Preorder traversal: ");

preorderTraversal(root);

printf("\n");

printf("Postorder traversal: ");

postorderTraversal(root);

printf("\n");

int treeHeight = height(root);

 printf("Height of the tree: %d\n", treeHeight);

return 0;

19. Implement Graph Traversal Technique: DFS

#include <stdio.h>

#include <stdlib.h>

// Structure to represent a node in the adjacency list

struct Node {

int data;

struct Node* next;

};

// Structure to represent a graph with an array of adjacency lists

struct Graph {

int vertices;

struct Node** adjacencyList;

int* visited;

};

// Function to create a new node

struct Node* createNode(int data) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

newNode->data = data;

newNode->next = NULL;

return newNode;

}
// Function to create a new graph with 'v' vertices

struct Graph* createGraph(int v) {

struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));

graph->vertices = v;

graph->adjacencyList = (struct Node**)malloc(v * sizeof(struct Node*));

graph->visited = (int*)malloc(v * sizeof(int));

for (int i = 0; i < v; i++) {

graph->adjacencyList[i] = NULL;

graph->visited[i] = 0;

return graph;

// Function to add an edge to the graph

void addEdge(struct Graph* graph, int src, int dest) {

struct Node* newNode = createNode(dest);

newNode->next = graph->adjacencyList[src];

graph->adjacencyList[src] = newNode;

// For an undirected graph, you would also add the reverse edge

newNode = createNode(src);

newNode->next = graph->adjacencyList[dest];

graph->adjacencyList[dest] = newNode;

// Depth-First Search function

void DFS(struct Graph* graph, int vertex) {

graph->visited[vertex] = 1;

printf("%d ", vertex);

 struct Node* current = graph->adjacencyList[vertex];

while (current != NULL) {

int adjacentVertex = current->data;

if (!graph->visited[adjacentVertex]) {

DFS(graph, adjacentVertex);

current = current->next;

int main() {

int vertices = 5;

struct Graph* graph = createGraph(vertices);

addEdge(graph, 0, 1);

addEdge(graph, 0, 2);

addEdge(graph, 1, 3);

addEdge(graph, 2, 4);

printf("Depth-First Search starting from vertex 0: ");

DFS(graph, 0);

return 0;

20. Implement Graph Traversal Technique: BFS

#include <stdio.h>

#include <stdlib.h>

// Structure to represent a node in the adjacency list

struct Node {

int data;

struct Node* next;

};

// Structure to represent a graph with an array of adjacency lists

struct Graph {

int vertices;

struct Node** adjacencyList;

int* visited;

};

// Structure to represent a queue for BFS

struct Queue {

int front, rear, size;

unsigned capacity;

int* array;

};

// Function to create a new node

struct Node* createNode(int data) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

newNode->data = data;

newNode->next = NULL;

return newNode;

// Function to create a new graph with 'v' vertices

struct Graph* createGraph(int v) {

struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));

graph->vertices = v;
 graph->adjacencyList = (struct Node**)malloc(v * sizeof(struct Node*));

graph->visited = (int*)malloc(v * sizeof(int));

for (int i = 0; i < v; i++) {

graph->adjacencyList[i] = NULL;

graph->visited[i] = 0;

return graph;

// Function to add an edge to the graph

void addEdge(struct Graph* graph, int src, int dest) {

struct Node* newNode = createNode(dest);

newNode->next = graph->adjacencyList[src];

graph->adjacencyList[src] = newNode;

// For an undirected graph, you would also add the reverse edge

newNode = createNode(src);

newNode->next = graph->adjacencyList[dest];

graph->adjacencyList[dest] = newNode;

// Function to create a new queue for BFS

struct Queue* createQueue(unsigned capacity) {

struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue));

queue->capacity = capacity;

queue->front = queue->size = 0;

queue->rear = capacity - 1;

queue->array = (int*)malloc(capacity * sizeof(int));

return queue;

}
// Function to check if the queue is empty

int isEmpty(struct Queue* queue) {

return (queue->size == 0);

// Function to check if the queue is full

int isFull(struct Queue* queue) {

return (queue->size == queue->capacity);

// Function to enqueue an element into the queue

void enqueue(struct Queue* queue, int item) {

if (isFull(queue))

return;

queue->rear = (queue->rear + 1) % queue->capacity;

queue->array[queue->rear] = item;

queue->size = queue->size + 1;

// Function to dequeue an element from the queue

int dequeue(struct Queue* queue) {

if (isEmpty(queue))

return -1;

int item = queue->array[queue->front];

queue->front = (queue->front + 1) % queue->capacity;

queue->size = queue->size - 1;

return item;

// Breadth-First Search function

void BFS(struct Graph* graph, int startVertex) {

struct Queue* queue = createQueue(graph->vertices);

graph->visited[startVertex] = 1;

enqueue(queue, startVertex);

while (!isEmpty(queue)) {

int currentVertex = dequeue(queue);

printf("%d ", currentVertex);

struct Node* temp = graph->adjacencyList[currentVertex];

while (temp != NULL) {

int adjacentVertex = temp->data;

if (!graph->visited[adjacentVertex]) {

graph->visited[adjacentVertex] = 1;

enqueue(queue, adjacentVertex);

temp = temp->next;

int main() {

int vertices = 7;

struct Graph* graph = createGraph(vertices);

addEdge(graph, 0, 1);

addEdge(graph, 0, 2);

addEdge(graph, 1, 3);

addEdge(graph, 1, 4);

addEdge(graph, 2, 5);
 addEdge(graph, 2, 6);

printf("Breadth-First Search starting from vertex 0: ");

BFS(graph, 0);

return 0;

21. Implement Hashing using array. Demonstrate

Linear Probing to handle collision
#include <stdio.h>

#include <stdlib.h>

#define SIZE 10

// Structure to represent a hash table

struct HashTable {

int keys[SIZE];

int values[SIZE];

};

// Initialize the hash table

void initialize(struct HashTable *table) {

for (int i = 0; i < SIZE; i++) {

table->keys[i] = -1; // -1 represents an empty slot

// Hash function to map a key to an index in the table

int hash(int key) {

 return key % SIZE;

// Function to insert a key-value pair into the hash table using linear probing

void insert(struct HashTable *table, int key, int value) {

int index = hash(key);

while (table->keys[index] != -1) {

index = (index + 1) % SIZE; // Linear probing

table->keys[index] = key;

table->values[index] = value;

printf("Key %d with value %d inserted at index %d\n", key, value, index);

// Function to retrieve a value for a given key from the hash table

int retrieve(struct HashTable *table, int key) {

int index = hash(key);

while (table->keys[index] != key) {

if (table->keys[index] == -1) {

return -1; // Key not found

index = (index + 1) % SIZE;

return table->values[index];

int main() {
struct HashTable table;

initialize(&table);

int choice, key, value;

while (1) {

printf("Choose an operation:\n");

printf("1. Insert\n2. Retrieve\n3. Exit\n");

scanf("%d", &choice);

switch (choice) {

case 1:

printf("Enter a key and value to insert: ");

scanf("%d %d", &key, &value);

insert(&table, key, value);

break;

case 2:

printf("Enter a key to retrieve: ");

scanf("%d", &key);

value = retrieve(&table, key);

if (value == -1) {

printf("Key %d not found in the table.\n", key);

} else {

printf("Value for key %d: %d\n", key, value);

break;

case 3:

exit(0);
 default:

printf("Invalid choice. Try again.\n");

return 0;

22. Implement Hashing using array. Demonstrate

Quadratic Probing to handle collision
#include <stdio.h>

#include <stdlib.h>

#define SIZE 10

// Structure to represent a hash table

struct HashTable {

int keys[SIZE];

int values[SIZE];

};

// Initialize the hash table

void initialize(struct HashTable *table) {

for (int i = 0; i < SIZE; i++) {

table->keys[i] = -1; // -1 represents an empty slot

// Hash function to map a key to an index in the table

int hash(int key) {

return key % SIZE;

}

// Function to insert a key-value pair into the hash table using quadratic probing

void insert(struct HashTable *table, int key, int value) {

int index = hash(key);

int i = 0;

while (table->keys[index] != -1) {

i++;

index = (index + i*i) % SIZE; // Quadratic probing

table->keys[index] = key;

table->values[index] = value;

printf("Key %d with value %d inserted at index %d\n", key, value, index);

// Function to retrieve a value for a given key from the hash table

int retrieve(struct HashTable *table, int key) {

int index = hash(key);

int i = 0;

while (table->keys[index] != key) {

if (table->keys[index] == -1) {

return -1; // Key not found

i++;

index = (index + i*i) % SIZE;

return table->values[index];
}

int main() {

struct HashTable table;

initialize(&table);

int choice, key, value;

while (1) {

printf("Choose an operation:\n");

printf("1. Insert\n2. Retrieve\n3. Exit\n");

scanf("%d", &choice);

switch (choice) {

case 1:

printf("Enter a key and value to insert: ");

scanf("%d %d", &key, &value);

insert(&table, key, value);

break;

case 2:

printf("Enter a key to retrieve: ");

scanf("%d", &key);

value = retrieve(&table, key);

if (value == -1) {

printf("Key %d not found in the table.\n", key);

} else {

printf("Value for key %d: %d\n", key, value);

break;
 case 3:

exit(0);

default:

printf("Invalid choice. Try again.\n");

return 0;