R23 Data Structures SEC Lab Cycle Programs

Pre-requisite:
Course Objectives:
 To provide the knowledge of basic data structures and their implementations.
 To understand importance of data structures in context of writing efficient
programs.
 To develop skills to apply appropriate data structures in problem solving.

Course Outcomes: At the end of the course, Student will be able to

 CO1: Identify the role of data structures in organizing and accessing data.
 CO2: Design, implement, and apply linked lists for dynamic data storage.
 CO3: Develop applications using stacks and queues.
 CO4: Design and implement algorithms for operations on binary trees and
binary search trees.
 CO5: Devise novel solutions to small scale programming challenges involving
data structures such as stacks, queues, Trees.

UNIT I
Introduction to Data Structures: Definition and importance of Data structures,
Abstract data types (ADTs) and its specifications Arrays: Introduction, 1-D, 2-D
Arrays, accessing elements of array, Row Major and Column Major storage of
Arrays, Searching Techniques: Linear & Binary Search, Sorting Techniques:
Bubble sort, Selection sort, Quick sort.

UNIT II
Linked Lists: Singly linked lists: representation and operations, doubly linked lists
and circular linked lists, Comparing arrays and linked lists, Applications of linked
lists.

UNIT III

1
Stacks: Introduction to stacks: properties and operations, implementing stacks
using arrays and linked lists, Applications of stacks in expression evaluation,
backtracking, reversing list etc.

UNIT IV
Queues: Introduction to queues: properties and operations, Circular queues,
implementing queues using arrays and linked lists, Applications of queues
scheduling, etc.
Deques: Introduction to deques (double-ended queues), Operations on deques
and their applications.

UNIT V
Trees: Introduction to Trees, Binary trees and traversals, Binary Search Tree–
Insertion, Deletion & Traversal

1. Program to find min & max element in an array.

2. Program to implement matrix multiplication.
3. Find an element in given list of sorted elements in an array using Binary
search.
4. Implement Selection and Quick sort techniques.
5. Write a program to implement the following operations.
a. Insert b. Deletion
6. Write a program to store name, roll no, and marks of students in a class
using circular
double linked list.
7. Write a program to perform addition of given two polynomial expressions
using linked list.
8. Implement stack operations using
a. Arrays b. Linked list
9. Convert given infix expression into post fix expression using stacks.
10. Evaluate given post fix expression using stack.
11. Write a program to reverse given linked list using stack.
2
12. Implement Queue operations using
a. Arrays b. Linked list
13. Implement Circular Queue using
b. Arrays b. Linked list
14. Implement Dequeue using linked list.
15. Implement binary tree traversals using linked list.
16. Write program to create binary search tree for given list of integers.
Perform inorder traversal of the tree. Implement insertion and deletion
operations.
1. Program to find min & max element in an array.
Program:
#include <stdio.h>

int main() {
int arr[100], n, i, min, max;

printf("Enter number of elements: ");

scanf("%d", &n);

printf("Enter array elements:\n");

for(i = 0; i < n; i++)
scanf("%d", &arr[i]);

min = max = arr[0];

for(i = 1; i < n; i++) {
if(arr[i] < min)
min = arr[i];
if(arr[i] > max)
max = arr[i];
}

printf("Minimum = %d\n", min);

3
 printf("Maximum = %d\n", max);

return 0;
Output:
Enter number of elements: 5
Enter array elements:
34
56
8
2
34
Minimum = 2
Maximum = 56

2. Program to implement matrix multiplication.

Program:
#include <stdio.h>

int main() {
int a[10][10], b[10][10], c[10][10];
int i, j, k, r1, c1, r2, c2;

printf("Enter rows and columns of first matrix: ");

scanf("%d%d", &r1, &c1);

printf("Enter rows and columns of second matrix: ");

scanf("%d%d", &r2, &c2);

if(c1 != r2) {
printf("Multiplication not possible.\n");
return 0;
}
4
 printf("Enter first matrix:\n");
for(i = 0; i < r1; i++)
for(j = 0; j < c1; j++)
scanf("%d", &a[i][j]);

printf("Enter second matrix:\n");

for(i = 0; i < r2; i++)
for(j = 0; j < c2; j++)
scanf("%d", &b[i][j]);

for(i = 0; i < r1; i++) {

for(j = 0; j < c2; j++) {
c[i][j] = 0;
for(k = 0; k < c1; k++)
c[i][j] += a[i][k] * b[k][j];
}
}

printf("Result matrix:\n");
for(i = 0; i < r1; i++) {
for(j = 0; j < c2; j++)
printf("%d ", c[i][j]);
printf("\n");
}

return 0;
}
Output:
Enter rows and columns of first matrix: 2
2
Enter rows and columns of second matrix: 2
5
 2
Enter first matrix:
1
1
1
1
Enter second matrix:
1
2
3
4
Result matrix:
46
46

3. Find an element in given list of sorted elements in an array using

Binary Search
Program:
#include <stdio.h>

int main() {
int arr[100], n, key, i, low, high, mid;

printf("Enter number of elements: ");

scanf("%d", &n);

printf("Enter sorted elements:\n");

for(i = 0; i < n; i++)
scanf("%d", &arr[i]);

printf("Enter element to search: ");

scanf("%d", &key);
6
 low = 0;
high = n - 1;

while(low <= high) {

mid = (low + high) / 2;

if(arr[mid] == key) {
printf("Element found at position %d\n", mid + 1);
return 0;
}
else if(arr[mid] < key)
low = mid + 1;
else
high = mid - 1;
}

printf("Element not found.\n");

return 0;
}
Output:
Enter number of elements: 5
Enter sorted elements:
2
9
10
23
56
Enter element to search: 9
Element found at position 2

4. Implement Selection and Quick sort technique

7
Selection Sort Program:
#include <stdio.h>

int main() {
int arr[100], n, i, j, min, temp;

printf("Enter number of elements: ");

scanf("%d", &n);

printf("Enter elements:\n");
for(i = 0; i < n; i++)
scanf("%d", &arr[i]);

for(i = 0; i < n - 1; i++) {

min = i;
for(j = i + 1; j < n; j++) {
if(arr[j] < arr[min])
min = j;
}
temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}

printf("Sorted array:\n");
for(i = 0; i < n; i++)
printf("%d ", arr[i]);

return 0;
}
Output:
8
Enter number of elements: 5
Enter elements:
7
5
0
10
1
Sorted array:
0 1 5 7 10

Quick Sort Program:

#include <stdio.h>

// Swap function
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}

// Partition function (pivot = arr[lb])

int partition(int arr[], int lb, int ub) {
int pivot = arr[lb]; // pivot is the first element
int start = lb;
int end = ub;

while (start < end) {

while (arr[start] <= pivot)
start++;

while (arr[end] > pivot)

end--;
9
 if (start < end)
swap(&arr[start], &arr[end]);
}

swap(&arr[lb], &arr[end]); // pivot placed at correct position

return end; // this is the loc
}

// QuickSort function
void quickSort(int arr[], int lb, int ub) {
if (lb < ub) {
int loc = partition(arr, lb, ub); // loc is pivot index
quickSort(arr, lb, loc - 1);
quickSort(arr, loc + 1, ub);
}
}

// Print array
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}

// Main function
int main() {
int arr[] = {7, 2, 1, 6, 8, 5, 3, 4};
int n = sizeof(arr) / sizeof(arr[0]);

printf("Original array:\n");
printArray(arr, n);
10
 quickSort(arr, 0, n - 1);

printf("Sorted array:\n");
printArray(arr, n);

return 0;
}
Output:
Original array:
72168534
Sorted array:
12345678

5. Write a program to implement the following operations.

a. Insert b. Deletion c. Traversal
Program:
#include <stdio.h>
#include <stdlib.h>

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

struct Node* head = NULL;

// Insert at end
void insert(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;
11
 if(head == NULL) {
head = newNode;
} else {
struct Node* temp = head;
while(temp->next != NULL)
temp = temp->next;
temp->next = newNode;
}
}
// Delete from front
void deleteFront() {
if(head == NULL) {
printf("List is empty.\n");
return;
}
struct Node* temp = head;
head = head->next;
free(temp);
printf("First node deleted.\n");
}

// Traverse
void display() {
struct Node* temp = head;
if(temp == NULL) {
printf("List is empty.\n");
return;
}
printf("List elements: ");
while(temp != NULL) {
printf("%d ", temp->data);
12
 temp = temp->next;
}
printf("\n");
}

int main() {
int choice, val;

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

switch(choice) {
case 1:
printf("Enter value to insert: ");
scanf("%d", &val);
insert(val);
break;
case 2:
deleteFront();
break;
case 3:
display();
break;
case 4:
return 0;
default:
printf("Invalid choice!\n");
}
}
}
Output:
13
1. Insert
2. Delete
3. Display
4. Exit
Enter choice: 1
Enter value to insert: 10

1. Insert
2. Delete
3. Display
4. Exit
Enter choice: 1
Enter value to insert: 20

1. Insert
2. Delete
3. Display
4. Exit
Enter choice: 1
Enter value to insert: 50

1. Insert
2. Delete
3. Display
4. Exit
Enter choice: 1
Enter value to insert: 32

1. Insert
2. Delete
3. Display
4. Exit
14
Enter choice: 3
List elements: 10 20 50 32

1. Insert
2. Delete
3. Display
4. Exit
Enter choice: 2
First node deleted.
1. Insert
2. Delete
3. Display
4. Exit
Enter choice: 2
First node deleted.

1. Insert
2. Delete
3. Display
4. Exit
Enter choice: 20
Invalid choice!

1. Insert
2. Delete
3. Display
4. Exit
Enter choice: 3
List elements: 50 32

1. Insert
2. Delete
15
 3. Display
4. Exit
Enter choice: 4

6. Write a program to store name, roll no, and marks of students in a

class using circular double linked list.
Program:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct Student {
int roll;
char name[50];
float marks;
struct Student* prev;
struct Student* next;
};
struct Student* head = NULL;

// Create new node

struct Student* createNode(int roll, char name[], float marks) {
struct Student* newNode = (struct Student*)malloc(sizeof(struct
Student));
newNode->roll = roll;
strcpy(newNode->name, name);
newNode->marks = marks;
newNode->prev = newNode->next = NULL;
return newNode;
}

// Insert at end
void insert(int roll, char name[], float marks) {
16
 struct Student* newNode = createNode(roll, name, marks);

if(head == NULL) {
head = newNode;
head->next = head;
head->prev = head;
} else {
struct Student* last = head->prev;

last->next = newNode;
newNode->prev = last;
newNode->next = head;
head->prev = newNode;
}
}

// Display the list

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

struct Student* temp = head;

printf("\nStudent Records:\n");

do {
printf("Roll No: %d\n", temp->roll);
printf("Name : %s\n", temp->name);
printf("Marks : %.2f\n", temp->marks);
printf("-------------------\n");
temp = temp->next;
17
 } while(temp != head);
}

int main() {
int choice, roll;
float marks;
char name[50];

while(1) {
printf("\n1. Insert Student\n2. Display All\n3. Exit\nEnter choice: ");
scanf("%d", &choice);
switch(choice) {
case 1:
printf("Enter Roll No: ");
scanf("%d", &roll);
printf("Enter Name: ");
scanf(" %[^\n]", name); // To read full name with spaces
printf("Enter Marks: ");
scanf("%f", &marks);
insert(roll, name, marks);
break;
case 2:
display();
break;
case 3:
return 0;
default:
printf("Invalid choice!\n");
}
}
}
Output:
18
1. Insert Student
2. Display All
3. Exit
Enter choice: 1
Enter Roll No: 1
Enter Name: Alice
Enter Marks: 80

1. Insert Student
2. Display All
3. Exit
Enter choice: 1
Enter Roll No: 2
Enter Name: Bob
Enter Marks: 76

1. Insert Student
2. Display All
3. Exit
Enter choice: 1
Enter Roll No: 3
Enter Name: Risy
Enter Marks: 89

1. Insert Student
2. Display All
3. Exit
Enter choice: 2

Student Records:
Roll No: 1
Name : Alice
19
 Marks : 80.00
-------------------
Roll No: 2
Name : Bob
Marks : 76.00
-------------------
Roll No: 3
Name : Risy
Marks : 89.00
-------------------

1. Insert Student
2. Display All
3. Exit
Enter choice: 3

7. Write a program to perform addition of given two polynomial

expressions using linked list.
Program:
#include <stdio.h>
#include <stdlib.h>

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

struct Node
{
int coefficient; // Coefficient of the term
int exponent; // Exponent of the term
struct Node* next; // Pointer to the next term
};

// Function to create a new node

struct Node* createNode(int coefficient, int exponent)
20
{
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->coefficient = coefficient;
newNode->exponent = exponent;
newNode->next = NULL;
return newNode;
}

// Function to add two polynomials

struct Node* addPolynomials(struct Node* poly1, struct Node* poly2)
{
// Dummy node to start the result polynomial
struct Node* result = createNode(0, 0);
struct Node* current = result;

while (poly1 != NULL && poly2 != NULL) {

if (poly1->exponent > poly2->exponent) {
current->next = createNode(poly1->coefficient, poly1->exponent);
poly1 = poly1->next;
}
else if (poly1->exponent < poly2->exponent) {
current->next = createNode(poly2->coefficient, poly2->exponent);
poly2 = poly2->next;
}
else {
int sum = poly1->coefficient + poly2->coefficient;
if (sum != 0) { // Only add if the sum is non-zero
current->next = createNode(sum, poly1->exponent);
}
poly1 = poly1->next;
poly2 = poly2->next;
}
21
 current = current->next;
}

// Append remaining terms from poly1 or poly2

while (poly1 != NULL)
{
current->next = createNode(poly1->coefficient, poly1->exponent);
poly1 = poly1->next;
current = current->next;
}
while (poly2 != NULL) {
current->next = createNode(poly2->coefficient, poly2->exponent);
poly2 = poly2->next;
current = current->next;
}

return result->next; // Return the actual head of the result polynomial

}

// Function to print the polynomial

void printPolynomial(struct Node* poly)
{
if (poly == NULL) {
printf("0\n");
return;
}

while (poly != NULL) {

printf("%dx^%d", poly->coefficient, poly->exponent);
if (poly->next != NULL) {
printf(" + ");
22
 }
poly = poly->next;
}
printf("\n");
}

int main()
{
// Create the first polynomial: 3x^3 + 5x^2 + 6x + 2
struct Node* poly1 = createNode(3, 3);
poly1->next = createNode(5, 2);
poly1->next->next = createNode(6, 1);
poly1->next->next->next = createNode(2, 0);

// Create the second polynomial: 4x^3 + 2x^2 + 7

struct Node* poly2 = createNode(4, 3);
poly2->next = createNode(2, 2);
poly2->next->next = createNode(7, 0);

// Add the polynomials

struct Node* result = addPolynomials(poly1, poly2);
// Print the result
printf("Sum of the polynomials is: ");
printPolynomial(result);
return 0;
}
Output:
Sum of the polynomials is: 7x^3 + 7x^2 + 6x^1 + 9x^0

8. Implement stack operations using

a. Arrays b. Linked list.
Stack Implementation Using Arrays
23
Program:
#include <stdio.h>
#include <stdlib.h>
#define MAX 5 // Define stack size

int stack[MAX], top = -1;

// Function to push an element onto the stack

void push(int value) {
if (top == MAX - 1) {
printf("Stack Overflow! Cannot push %d\n", value);
return;
}
stack[++top] = value;
printf("%d pushed to stack\n", value);
}

// Function to pop an element from the stack

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

// Function to get the top element without removing it

int peek() {
if (top == -1) {
printf("Stack is empty.\n");
return -1;
}
24
 return stack[top];
}

// Function to check if the stack is empty

int isEmpty() {
return top == -1;
}

// Main function to test the stack

int main()
{
push(10);
push(20);
push(30);

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

printf("Popped element is %d\n", pop());
printf("Popped element is %d\n", pop());

if (isEmpty())
printf("Stack is empty now.\n");
else
printf("Stack is not empty.\n");

return 0;
}
Output:
10 pushed to stack
20 pushed to stack
30 pushed to stack
Top element is 30
Popped element is 30
25
Popped element is 20
Stack is not empty.
Stack Implementation Using Linked List
#include <stdio.h>
#include <stdlib.h>

// Define a node structure for stack

struct Node {
int data;
struct Node* next;
};
struct Node* top = NULL;

// Function to push an element onto the stack

void push(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (!newNode) {
printf("Heap Overflow! Cannot push %d\n", value);
return;
}
newNode->data = value;
newNode->next = top;
top = newNode;
printf("%d pushed to stack\n", value);
}

// Function to pop an element from the stack

int pop() {
if (top == NULL) {
printf("Stack Underflow! No element to pop.\n");
return -1;
}
26
 struct Node* temp = top;
int value = temp->data;
top = top->next;
free(temp);
return value;
}

// Function to get the top element without removing it

int peek() {
if (top == NULL) {
printf("Stack is empty.\n");
return -1;
}
return top->data;
}

// Function to check if the stack is empty

int isEmpty() {
return top == NULL;
}

// Main function to test the stack

int main()
{
push(10);
push(20);
push(30);

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

printf("Popped element is %d\n", pop());

printf("Popped element is %d\n", pop());
27
 if (isEmpty())
printf("Stack is empty now.\n");
else
printf("Stack is not empty.\n");

return 0;
}
Output:
10 pushed to stack
20 pushed to stack
30 pushed to stack
Top element is 30
Popped element is 30
Popped element is 20
Stack is not empty.

9. Convert given infix expression into post fix expression using stacks.

10. Evaluate given post fix expression using stack.

C program to convert an infix expression to postfix and evaluate it

using stack

Program:
#include <stdio.h>
#include <ctype.h>

#define MAX 100

int stack[MAX], top = -1;
28
void push(int value)
{
stack[++top] = value;
}

int pop()
{
return stack[top--];
}

int precedence(char c)
{
return (c == '+' || c == '-') ? 1 : (c == '*' || c == '/') ? 2 : 0;
}

void infixToPostfix(char* infix, char* postfix)

{
int j = 0;
for (int i = 0; infix[i]; i++)
{
if (isdigit(infix[i]))
postfix[j++] = infix[i];
else if (infix[i] == '(')
push(infix[i]);
else if (infix[i] == ')')
{
while (top >= 0 && stack[top] != '(')
postfix[j++] = pop();
pop();
}
else
29
 {
while (top >= 0 && precedence(stack[top]) >= precedence(infix[i]))
postfix[j++] = pop();
push(infix[i]);
}
}
while (top >= 0)
postfix[j++] = pop();
postfix[j] = '\0';
}

int evaluatePostfix(char* expr)

{
for (int i = 0; expr[i]; i++)
{
if (isdigit(expr[i])) push(expr[i] - '0');
else
{
int b = pop(), a = pop();
if (expr[i] == '+') push(a + b);
else if (expr[i] == '-') push(a - b);
else if (expr[i] == '*') push(a * b);
else if (expr[i] == '/') push(a / b);
}
}
return pop();
}

int main()
{
char infix[MAX], postfix[MAX];
printf("Enter infix: ");
30
 scanf("%s", infix);
infixToPostfix(infix, postfix);
printf("Postfix: %s\n", postfix);
printf("Result: %d\n", evaluatePostfix(postfix));
return 0;
}

Output:
Enter infix: ((3+4)/(5-2))
Postfix: 34+52-/
Result: 2

11. Write a program to reverse given linked list using stack.

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

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

// Stack node for storing Node pointers

struct StackNode {
struct Node* listNode;
struct StackNode* next;
};

// Stack operations
void push(struct StackNode** top, struct Node* node) {

31
 struct StackNode* newStackNode = (struct
StackNode*)malloc(sizeof(struct StackNode));
newStackNode->listNode = node;
newStackNode->next = *top;
*top = newStackNode;
}

struct Node* pop(struct StackNode** top) {

if (*top == NULL)
return NULL;
struct StackNode* temp = *top;
*top = (*top)->next;
struct Node* poppedNode = temp->listNode;
free(temp);
return poppedNode;
}

// 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 print the list

void printList(struct Node* head) {
struct Node* temp = head;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
32
 printf("\n");
}

// Function to reverse the linked list using stack

struct Node* reverseUsingStack(struct Node* head) {
struct StackNode* stack = NULL;
struct Node* temp = head;

// Push all nodes to stack

while (temp != NULL) {
push(&stack, temp);
temp = temp->next;
}
// Pop from stack and rebuild the list
if (stack == NULL)
return NULL;

head = pop(&stack);
temp = head;

while (stack != NULL) {

temp->next = pop(&stack);
temp = temp->next;
}
temp->next = NULL;

return head;
}

// Main function
int main() {
// Creating a sample linked list: 10 -> 20 -> 30 -> 40
33
 struct Node* head = createNode(10);
head->next = createNode(20);
head->next->next = createNode(30);
head->next->next->next = createNode(40);

printf("Original List:\n");
printList(head);

head = reverseUsingStack(head);

printf("Reversed List:\n");
printList(head);

return 0;
}
Output:
Original List:
10 20 30 40
Reversed List:
40 30 20 10

12. Implement Queue operations using

a. Arrays b. Linked list
Implementation of Queue using arrays
Program:
#include <stdio.h>
#define MAX 5 // Maximum size of the queue
int queue[MAX]; // Array to store queue elements
int front = -1, rear = -1; // Front and rear of the queue

// Check if the queue is empty

int isEmpty()
34
{
return front == -1;
}

// Check if the queue is full

int isFull()
{
return rear == MAX - 1;
}

// Add an element to the queue (enqueue)

void enqueue(int item)
{
if (isFull())
{
printf("Queue is full. Cannot enqueue %d.\n", item);
}
else
{
if (front == -1) front = 0; // Set front when first element is added
queue[++rear] = item; // Increment rear and add the item
printf("Enqueued: %d\n", item);
}
}

// Remove an element from the queue (dequeue)

void dequeue()
{
if (isEmpty())
{
printf("Queue is empty. Cannot dequeue.\n");
}
35
 else
{
printf("Dequeued: %d\n", queue[front]);
if (front == rear) // If the queue becomes empty after dequeue
front = rear = -1;
else
front++; // Increment front
}
}

// Get the front element of the queue (peek)

void peek()
{
if (isEmpty())
printf("Queue is empty.\n");
else
printf("Front item: %d\n", queue[front]);
}

// Display all elements of the queue

void display()
{
if (isEmpty())
{
printf("Queue is empty.\n");
}
else
{
printf("Queue contents: ");
for (int i = front; i <= rear; i++) {
printf("%d ", queue[i]);
}
36
 printf("\n");
}
}

// Main function to demonstrate queue operations

int main()
{
enqueue(10);
enqueue(20);
enqueue(30);
enqueue(40);
enqueue(50); // Queue is full
display(); // Display queue contents
dequeue();
dequeue();
display(); // Display remaining queue contents
enqueue(60); // Enqueue after dequeue
display(); // Display queue after enqueue
peek(); // Peek at the front element
return 0;
}
Output:
Enqueued: 10
Enqueued: 20
Enqueued: 30
Enqueued: 40
Enqueued: 50
Queue contents: 10 20 30 40 50
Dequeued: 10
Dequeued: 20
Queue contents: 30 40 50
Queue is full. Cannot enqueue 60.
37
Queue contents: 30 40 50
Front item: 30
Implementation of Queues using Linked List
Program:
#include <stdio.h>
#include <stdlib.h>

// Node structure
struct Node
{
int data;
struct Node* next;
};
// Queue front and rear pointers
struct Node* front = NULL;
struct Node* rear = NULL;

// Check if the queue is empty

int isEmpty()
{
return front == NULL;
}

// Enqueue operation (insert at rear)

void enqueue(int value)
{
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL)
{
printf("Memory allocation failed. Queue is full!\n");
return;
}
38
 newNode->data = value;
newNode->next = NULL;

if (isEmpty())
{
front = rear = newNode;
}
else
{
rear->next = newNode;
rear = newNode;
}
printf("Enqueued: %d\n", value);
}

// Dequeue operation (remove from front)

void dequeue()
{
if (isEmpty())
{
printf("Queue is empty. Cannot dequeue.\n");
return;
}
struct Node* temp = front;
printf("Dequeued: %d\n", temp->data);
front = front->next;
free(temp);

if (front == NULL)
{ // If queue becomes empty, reset rear
rear = NULL;
}
39
}

// Peek operation (get front element)

void peek()
{
if (isEmpty())
{
printf("Queue is empty.\n");
}
else
{
printf("Front element: %d\n", front->data);
}
}

// Display operation (print queue elements)

void display()
{
if (isEmpty())
{
printf("Queue is empty.\n");
return;
}
struct Node* temp = front;
printf("Queue: ");
while (temp)
{
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
40
 // Main function
int main()
{
enqueue(10);
enqueue(20);
enqueue(30);
display(); // Output: Queue: 10 20 30
peek(); // Output: Front element: 10
dequeue();
dequeue();
display(); // Output: Queue: 30
return 0;
}
Output:
Enqueued: 10
Enqueued: 20
Enqueued: 30
Queue: 10 20 30
Front element: 10
Dequeued: 10
Dequeued: 20
Queue: 30

13. Implement Circular Queue using

a. Arrays b. Linked list
C Program to implement Circular Queue using Array
Program:
#include <stdio.h>
#define MAX 5 // Maximum size of the queue
int queue[MAX]; // Array to store queue elements
int front = -1, rear = -1; // Front and rear of the queue
41
// Check if the queue is empty
int isEmpty() {
return front == -1;
}

// Check if the queue is full

int isFull() {
return (rear + 1) % MAX == front;
}

// Add an element to the queue (enqueue)

void enqueue(int item) {
if (isFull()) {
printf("Queue is full. Cannot enqueue %d.\n", item);
} else {
if (front == -1) front = 0; // Set front when first element is added
rear = (rear + 1) % MAX; // Circular increment of rear
queue[rear] = item; // Add the item at the new rear position
printf("\nEnqueued: %d", item);
}
}

// Remove an element from the queue (dequeue)

void dequeue() {
if (isEmpty()) {
printf("Queue is empty. Cannot dequeue.\n");
} else {
printf("\n Dequeued: %d", queue[front]);
if (front == rear) { // If the queue becomes empty after dequeue
front = rear = -1;
} else {
42
 front = (front + 1) % MAX; // Circular increment of front
}
}
}

// Get the front element of the queue (peek)

void peek() {
if (isEmpty()) {
printf("Queue is empty.\n");
} else {
printf("\n Front item: %d", queue[front]);
}
}
// Display all elements of the queue using a for loop
void display() {
if (isEmpty()) {
printf("Queue is empty.\n");
} else {
printf("\n Queue contents:");
int i;
// Using a for loop to handle circular queue traversal
for (i = front; i != rear; i = (i + 1) % MAX) {
printf("%d ", queue[i]);
}
//printf("%d\n", queue[rear]); // Print the last element (rear)
}
}

// Main function to demonstrate queue operations

int main() {
enqueue(10);
enqueue(20);
43
 enqueue(30);
enqueue(40);
enqueue(50); // Queue is full
display(); // Display queue contents

dequeue();
dequeue();
display(); // Display remaining queue contents

enqueue(60); // Enqueue after dequeue

display(); // Display queue after enqueue

peek(); // Peek at the front element

enqueue(70); // Enqueue another element
display(); // Display queue after another enqueue

return 0;
}
Output:
Enqueued: 10
Enqueued: 20
Enqueued: 30
Enqueued: 40
Enqueued: 50
10 20 30 40 50
Output:Dequeued: 10
Dequeued: 20
30 40 50
Enqueued: 60
30 40 50 60
Front item: 30
Enqueued: 70
44
30 40 50 60 70

C Program to implement Circular Queue using Linked List

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

// Node structure for Circular Queue

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

struct Node* front = NULL;

struct Node* rear = NULL;

// Enqueue operation
void enqueue(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;

if (front == NULL) {
front = rear = newNode;
rear->next = front; // Circular link
} else {
rear->next = newNode;
rear = newNode;
rear->next = front;
}
printf("\nEnqueued: %d", value);
}

45
// Dequeue operation
void dequeue() {
if (front == NULL) {
printf("\nQueue is empty. Cannot dequeue.\n");
return;
}

if (front == rear) {
printf("\nDequeued: %d", front->data);
free(front);
front = rear = NULL;
} else {
struct Node* temp = front;
printf("\nDequeued: %d", temp->data);
front = front->next;
rear->next = front;
free(temp);
}
}

// Peek operation
void peek() {
if (front == NULL) {
printf("\nQueue is empty.");
} else {
printf("\nFront item: %d", front->data);
}
}

// Display operation
void display() {
if (front == NULL) {
46
 printf("\nQueue is empty.");
return;
}

struct Node* temp = front;

printf("\nQueue contents: ");
do {
printf("%d ", temp->data);
temp = temp->next;
} while (temp != front);
}

// Main function to demonstrate circular queue using linked list

int main() {
enqueue(10);
enqueue(20);
enqueue(30);
enqueue(40);
enqueue(50);

display();

dequeue();
dequeue();

display();

enqueue(60);
display();

peek();

47
 enqueue(70);
display();

return 0;
}
Output:
Enqueued: 10
Enqueued: 20
Enqueued: 30
Enqueued: 40
Enqueued: 50
Queue contents: 10 20 30 40 50
Dequeued: 10
Dequeued: 20
Queue contents: 30 40 50
Enqueued: 60
Queue contents: 30 40 50 60
Front item: 30
Enqueued: 70
Queue contents: 30 40 50 60 70

14. Implement Dequeue using linked list

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

// Node structure for doubly linked list

struct Node {
int data;
struct Node* prev;
struct Node* next;
};
48
struct Node* front = NULL;
struct Node* rear = NULL;

// Insert at front
void insertFront(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->prev = NULL;
newNode->next = front;

if (front == NULL) {
front = rear = newNode;
} else {
front->prev = newNode;
front = newNode;
}
printf("\nInserted at front: %d", value);
}

// Insert at rear
void insertRear(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;
newNode->prev = rear;

if (rear == NULL) {
front = rear = newNode;
} else {
rear->next = newNode;
rear = newNode;
49
 }
printf("\nInserted at rear: %d", value);
}

// Delete from front

void deleteFront() {
if (front == NULL) {
printf("\nDeque is empty. Cannot delete from front.");
return;
}

struct Node* temp = front;

printf("\nDeleted from front: %d", temp->data);
if (front == rear) {
front = rear = NULL;
} else {
front = front->next;
front->prev = NULL;
}
free(temp);
}

// Delete from rear

void deleteRear() {
if (rear == NULL) {
printf("\nDeque is empty. Cannot delete from rear.");
return;
}

struct Node* temp = rear;

printf("\nDeleted from rear: %d", temp->data);

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

// Display Deque
void display() {
if (front == NULL) {
printf("\nDeque is empty.");
return;
}

struct Node* temp = front;

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

// Main function
int main() {
insertRear(10);
insertRear(20);
insertFront(5);
insertFront(2);

display();
51
 deleteFront();
deleteRear();

display();

insertRear(30);
insertFront(1);

display();

return 0;
}
Output:
Inserted at rear: 10
Inserted at rear: 20
Inserted at front: 5
Inserted at front: 2
Deque contents: 2 5 10 20
Deleted from front: 2
Deleted from rear: 20
Deque contents: 5 10
Inserted at rear: 30
Inserted at front: 1
Deque contents: 1 5 10 30

15. Implement binary tree traversals using linked list.

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

// Structure for binary tree node

52
struct Node {
int data;
struct Node* left;
struct Node* right;
};

// Function to create a new node

struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->left = newNode->right = NULL;
return newNode;
}
// Inorder Traversal (LNR)
void inorder(struct Node* root) {
if (root == NULL) return;
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}

// Preorder Traversal (NLR)

void preorder(struct Node* root) {
if (root == NULL) return;
printf("%d ", root->data);
preorder(root->left);
preorder(root->right);
}

// Postorder Traversal (LRN)

void postorder(struct Node* root) {
if (root == NULL) return;
53
 postorder(root->left);
postorder(root->right);
printf("%d ", root->data);
}

// Main function
int main() {
/*
1
/\
2 3
/\
4 5
*/

struct Node* root = createNode(1);

root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);

printf("Inorder Traversal: ");

inorder(root);

printf("\nPreorder Traversal: ");

preorder(root);

printf("\nPostorder Traversal: ");

postorder(root);

return 0;
}
54
 Output:
Inorder Traversal: 4 2 5 1 3
Preorder Traversal: 1 2 4 5 3
Postorder Traversal: 4 5 2 3 1

16. Write program to create binary search tree for given list of
integers. Perform traversal of the tree. Implement insertion and
deletion operations
Program:
#include <stdio.h>
#include <stdlib.h>

// Node structure
struct Node {
int data;
struct Node* left;
struct Node* right;
};

// Create a new node

struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->left = newNode->right = NULL;
return newNode;
}

// Insert into BST

struct Node* insert(struct Node* root, int value) {
if (root == NULL)
return createNode(value);

55
 if (value < root->data)
root->left = insert(root->left, value);
else if (value > root->data)
root->right = insert(root->right, value);

return root;
}

// Find minimum value node in a subtree

struct Node* findMin(struct Node* node) {
while (node->left != NULL)
node = node->left;
return node;
}
// Delete a node from BST
struct Node* deleteNode(struct Node* root, int value) {
if (root == NULL) return root;

if (value < root->data)

root->left = deleteNode(root->left, value);
else if (value > root->data)
root->right = deleteNode(root->right, value);
else {
// Node found
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;
56
 } else {
struct Node* temp = findMin(root->right);
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
}
}
return root;
}

// Inorder traversal (LNR)

void inorder(struct Node* root) {
if (root == NULL) return;
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}

// Preorder traversal (NLR)

void preorder(struct Node* root) {
if (root == NULL) return;
printf("%d ", root->data);
preorder(root->left);
preorder(root->right);
}

// Postorder traversal (LRN)

void postorder(struct Node* root) {
if (root == NULL) return;
postorder(root->left);
postorder(root->right);
printf("%d ", root->data);
}
57
// Main function
int main() {
int values[] = {50, 30, 70, 20, 40, 60, 80};
int n = sizeof(values) / sizeof(values[0]);

struct Node* root = NULL;

// Creating BST
for (int i = 0; i < n; i++) {
root = insert(root, values[i]);
}

printf("Inorder Traversal: ");

inorder(root);

printf("\nPreorder Traversal: ");

preorder(root);

printf("\nPostorder Traversal: ");

postorder(root);

printf("\n\nInserting 25...");
root = insert(root, 25);
printf("\nInorder after insertion: ");
inorder(root);

printf("\n\nDeleting 70...");
root = deleteNode(root, 70);
printf("\nInorder after deletion: ");
inorder(root);

58
 return 0;
}
Output:
Inorder Traversal: 20 30 40 50 60 70 80
Preorder Traversal: 50 30 20 40 70 60 80
Postorder Traversal: 20 40 30 60 80 70 50
Inserting 25...
Inorder after insertion: 20 25 30 40 50 60 70 80
Deleting 70...
Inorder after deletion: 20 25 30 40 50 60 80

59