4) STACK using ARRAY-
#include<stdio.h>
#include<stdlib.h>
#define SIZE 4
void push(int);
void pop();
void display();
int stack[SIZE], top = -1;
int main()
int value, choice;
while (1)
printf("\n\n**** MENU ****\n");
printf("1. Push\n2. Pop\n3. Display\n4. Exit");
printf("\nEnter your choice : ");
scanf("%d", & choice);
switch (choice)
case 1:
printf("Enter the value to be inserted: ");
scanf("%d", & value);
push(value);
break;
case 2:
pop();
break;
case 3:
display();
break;
case 4:
exit(0);
break;
default:
printf("\nWrong selection!! Try again!!");
void push(int value)
if (top == SIZE - 1)
printf("\nStack is full!! Insertion is not possible!!");
else
top++;
stack[top] = value;
printf("\nInsertion Success!!");
void pop()
if (top == -1)
printf("\nStack is empty. Deletion is not possible!!");
else
printf("\nDeleted: %d", stack[top]);
top--;
void display()
if (top == -1)
printf("\nStack is empty!!");
else
int i;
printf("\nStack elements are:\n");
for (i = top; i >= 0; i--)
printf("%d\n", stack[i]);
Output-
5) Stack using Linked list-
#include <stdio.h>
#include <stdlib.h>
// Define a node structure for the linked list
struct Node {
int data;
struct Node* next;
};
typedef struct Node NODE;
// Function declarations
NODE* createNode(int data);
void push(NODE** top, int data);
void pop(NODE** top);
void display(NODE* top);
int main() {
NODE* top = NULL; // Initialize an empty stack
int choice, data;
while (1) {
// Menu
printf("\n\n**** MENU ****\n");
printf("1. Push\n2. Pop\n3. Display\n4. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("Enter data to push: ");
scanf("%d", &data);
push(&top, data);
break;
case 2:
pop(&top);
break;
case 3:
display(top);
break;
case 4:
exit(0);
default:
printf("Invalid choice! Please enter a valid option.\n");
return 0;
// Function to create a new node
NODE* createNode(int data) {
NODE* newNode = (NODE*)malloc(sizeof(NODE));
if (newNode == NULL) {
printf("Memory allocation failed.\n");
exit(1);
newNode->data = data;
newNode->next = NULL;
return newNode;
// Function to push an element onto the stack
void push(NODE** top, int data) {
NODE* newNode = createNode(data);
newNode->next = *top;
*top = newNode;
printf("Pushed %d onto the stack.\n", data);
// Function to pop an element from the stack
void pop(NODE** top) {
if (*top == NULL) {
printf("Stack underflow! Cannot pop from an empty stack.\n");
return;
}
NODE* temp = *top;
*top = temp->next;
printf("Popped %d from the stack.\n", temp->data);
free(temp);
// Function to display the elements of the stack
void display(NODE* top) {
if (top == NULL) {
printf("Stack is empty.\n");
return;
printf("Stack elements (top to bottom): ");
while (top != NULL) {
printf("%d ", top->data);
top = top->next;
printf("\n");
}
6) QUEUES using Arrays-
#include <stdio.h>
#include <stdlib.h>
#define MAX 5
int insertion();
int deletion();
int display();
int queue_array[MAX];
int rear = -1;
int front = -1;
int main() {
int choice;
while (1) {
printf("\n1. Insert element to queue\n");
printf("2. Delete element from queue\n");
printf("3. Display all elements of the queue\n");
printf("4. Quit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
insertion();
break;
case 2:
deletion();
break;
case 3:
display();
break;
case 4:
exit(0);
default:
printf("Wrong choice\n");
return 0;
int insertion() {
int add_item;
if (rear == MAX - 1) {
printf("Queue Overflow\n");
} else {
front = 0;
printf("Insert the element in the queue: ");
scanf("%d", &add_item);
rear++;
queue_array[rear] = add_item;
int deletion() {
if (front == -1 || front > rear) {
printf("Queue Underflow\n");
} else {
printf("Element deleted from the queue is: %d\n", queue_array[front]);
front++;
int display() {
int i;
if (front == -1) {
printf("Queue is empty\n");
} else {
printf("Queue is:\n");
for (i = front; i <= rear; i++) {
printf("%d ", queue_array[i]);
printf("\n");
Output-
7) Queues Using LINKED LIST
#include <stdio.h>
#include <stdlib.h>
// Node structure for a linked list
struct Node {
int data;
struct Node* next;
};
typedef struct Node NODE;
// Function declarations
void enqueue(int data);
void dequeue();
void display();
void menu();
// Global variables
NODE* front = NULL;
NODE* rear = NULL;
int main() {
int choice, data;
while (1) {
menu();
printf("\nEnter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("Enter the data to enqueue: ");
scanf("%d", &data);
enqueue(data);
break;
case 2:
dequeue();
break;
case 3:
display();
break;
case 4:
exit(0);
default:
printf("Invalid choice! Please enter a valid option.\n");
return 0;
// Function to enqueue a new element into the queue
void enqueue(int data) {
NODE* newNode = (NODE*)malloc(sizeof(NODE));
if (newNode == NULL) {
printf("Memory allocation failed.\n");
exit(1);
newNode->data = data;
newNode->next = NULL;
if (front == NULL) {
front = rear = newNode;
} else {
rear->next = newNode;
rear = newNode;
printf("Enqueued: %d\n", data);
// Function to dequeue an element from the queue
void dequeue() {
if (front == NULL) {
printf("Queue is empty. Dequeue not possible.\n");
} else {
NODE* temp = front;
front = front->next;
printf("Dequeued: %d\n", temp->data);
free(temp);
// If the queue becomes empty after dequeue, update rear
if (front == NULL) {
rear = NULL;
// Function to display the elements in the queue
void display() {
if (front == NULL) {
printf("Queue is empty.\n");
} else {
NODE* temp = front;
printf("Queue elements: ");
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
printf("\n");
// Function to display menu options
void menu() {
printf("\n**** MENU ****\n");
printf("1. Enqueue\n");
printf("2. Dequeue\n");
printf("3. Display\n");
printf("4. Exit\n");
}
8) Circular Queue
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 5
// Circular Queue structure
struct CircularQueue {
int front, rear;
int arr[MAX_SIZE];
};
typedef struct CircularQueue CIRCULAR_QUEUE;
// Function declarations
void initializeQueue(CIRCULAR_QUEUE* cq);
void enqueue(CIRCULAR_QUEUE* cq, int data);
void dequeue(CIRCULAR_QUEUE* cq);
void display(CIRCULAR_QUEUE* cq);
void menu();
int main() {
CIRCULAR_QUEUE cq;
initializeQueue(&cq);
int choice, data;
while (1) {
menu();
printf("\nEnter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("Enter the data to enqueue: ");
scanf("%d", &data);
enqueue(&cq, data);
break;
case 2:
dequeue(&cq);
break;
case 3:
display(&cq);
break;
case 4:
exit(0);
default:
printf("Invalid choice! Please enter a valid option.\n");
return 0;
// Function to initialize the circular queue
void initializeQueue(CIRCULAR_QUEUE* cq) {
cq->front = cq->rear = -1;
// Function to enqueue an element into the circular queue
void enqueue(CIRCULAR_QUEUE* cq, int data) {
if ((cq->front == 0 && cq->rear == MAX_SIZE - 1) || (cq->rear == (cq->front - 1) % (MAX_SIZE - 1))) {
printf("Circular Queue is full. Cannot enqueue.\n");
} else {
if (cq->front == -1) {
cq->front = cq->rear = 0;
} else {
cq->rear = (cq->rear + 1) % MAX_SIZE;
cq->arr[cq->rear] = data;
printf("Enqueued: %d\n", data);
// Function to dequeue an element from the circular queue
void dequeue(CIRCULAR_QUEUE* cq) {
if (cq->front == -1) {
printf("Circular Queue is empty. Cannot dequeue.\n");
} else {
printf("Dequeued: %d\n", cq->arr[cq->front]);
if (cq->front == cq->rear) {
initializeQueue(cq);
} else {
cq->front = (cq->front + 1) % MAX_SIZE;
// Function to display the elements in the circular queue
void display(CIRCULAR_QUEUE* cq) {
if (cq->front == -1) {
printf("Circular Queue is empty.\n");
} else {
int i = cq->front;
printf("Circular Queue elements: ");
do {
printf("%d ", cq->arr[i]);
i = (i + 1) % MAX_SIZE;
} while (i != (cq->rear + 1) % MAX_SIZE);
printf("\n");
// Function to display menu options
void menu() {
printf("\n**** MENU ****\n");
printf("1. Enqueue\n");
printf("2. Dequeue\n");
printf("3. Display\n");
printf("4. Exit\n");
}
9) Infix to Postfix
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define MAX_SIZE 100
struct Stack {
int top;
char items[MAX_SIZE];
};
typedef struct Stack STACK;
int isEmpty(STACK* stack) {
return stack->top == -1;
void push(STACK* stack, char item) {
if (stack->top == MAX_SIZE - 1) {
printf("Stack Overflow\n");
exit(1);
stack->items[++stack->top] = item;
char pop(STACK* stack) {
if (isEmpty(stack)) {
printf("Stack Underflow\n");
exit(1);
return stack->items[stack->top--];
int getPrecedence(char op) {
if (op == '+' || op == '-')
return 1;
if (op == '*' || op == '/')
return 2;
return 0;
void infixToPostfix(char infix[], char postfix[]) {
STACK stack;
stack.top = -1;
int i, j;
char ch, popped;
for (i = 0, j = 0; infix[i] != '\0'; i++) {
ch = infix[i];
if (isalnum(ch)) {
postfix[j++] = ch;
} else if (ch == '(') {
push(&stack, ch);
} else if (ch == ')') {
while (!isEmpty(&stack) && (popped = pop(&stack)) != '(') {
postfix[j++] = popped;
} else {
while (!isEmpty(&stack) && getPrecedence(ch) <= getPrecedence(stack.items[stack.top])) {
postfix[j++] = pop(&stack);
push(&stack, ch);
while (!isEmpty(&stack)) {
postfix[j++] = pop(&stack);
postfix[j] = '\0';
int main() {
char infix[MAX_SIZE], postfix[MAX_SIZE];
printf("Enter an infix expression: ");
fgets(infix, MAX_SIZE, stdin);
infix[strcspn(infix, "\n")] = '\0';
infixToPostfix(infix, postfix);
printf("Postfix expression: %s\n", postfix);
return 0;
}
10) Postfix expression evaluation
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#define MAX_SIZE 100
struct Stack {
int top;
int items[MAX_SIZE];
};
typedef struct Stack STACK;
int isEmpty(STACK* stack) {
return stack->top == -1;
void push(STACK* stack, int item) {
if (stack->top == MAX_SIZE - 1) {
printf("Stack Overflow\n");
exit(1);
stack->items[++stack->top] = item;
int pop(STACK* stack) {
if (isEmpty(stack)) {
printf("Stack Underflow\n");
exit(1);
return stack->items[stack->top--];
}
int evaluatePostfix(char postfix[]) {
STACK stack;
stack.top = -1;
for (int i = 0; postfix[i] != '\0'; i++) {
char ch = postfix[i];
if (isdigit(ch)) {
push(&stack, ch - '0');
} else if (isspace(ch)) {
continue; // Skip spaces
} else {
int operand2 = pop(&stack);
int operand1 = pop(&stack);
switch (ch) {
case '+':
push(&stack, operand1 + operand2);
break;
case '-':
push(&stack, operand1 - operand2);
break;
case '*':
push(&stack, operand1 * operand2);
break;
case '/':
push(&stack, operand1 / operand2);
break;
default:
printf("Invalid operator: %c\n", ch);
exit(1);
return pop(&stack);
}
int main() {
char postfix[MAX_SIZE];
printf("Enter a postfix expression: ");
scanf("%s", postfix);
int result = evaluatePostfix(postfix);
printf("Result of the postfix expression: %d\n", result);
return 0;
OUTPUT-
11) Merge Sort
#include <stdio.h>
// Function to merge two subarrays of arr[]
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
void merge(int arr[], int l, int m, int r) {
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
// Create temporary arrays
int L[n1], R[n2];
// Copy data to temporary arrays L[] and R[]
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
// Merge the temporary arrays back into arr[l..r]
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
k++;
// Copy the remaining elements of L[], if there are any
while (i < n1) {
arr[k] = L[i];
i++;
k++;
// Copy the remaining elements of R[], if there are any
while (j < n2) {
arr[k] = R[j];
j++;
k++;
// Recursive function to perform merge sort on arr[l..r]
void mergeSort(int arr[], int l, int r) {
if (l < r) {
// Same as (l+r)/2, but avoids overflow for large l and r
int m = l + (r - l) / 2;
// Sort first and second halves
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
// Merge the sorted halves
merge(arr, l, m, r);
// Function to print an array
void printArray(int A[], int size) {
for (int i = 0; i < size; i++)
printf("%d ", A[i]);
printf("\n");
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int arr_size = sizeof(arr) / sizeof(arr[0]);
printf("Given array: \n");
printArray(arr, arr_size);
// Perform merge sort
mergeSort(arr, 0, arr_size - 1);
printf("\nSorted array: \n");
printArray(arr, arr_size);
return 0;
}
12) Bubble Sort
#include <stdio.h>
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// Swap arr[j] and arr[j + 1]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
printf("\n");
int main() {
// Given input array
int arr[] = {64, 34, 25, 12, 22, 11, 90};
// Calculate the size of the array
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
printArray(arr, n);
// Perform Bubble Sort
bubbleSort(arr, n);
printf("Sorted array: ");
printArray(arr, n);
return 0;
}
13) DFS
#include <stdio.h>
#define MAX_VERTICES 100
int graph[MAX_VERTICES][MAX_VERTICES];
int visited[MAX_VERTICES];
int vertices, edges;
void initializeGraph() {
for (int i = 0; i < MAX_VERTICES; i++) {
visited[i] = 0;
for (int j = 0; j < MAX_VERTICES; j++) {
graph[i][j] = 0;
void addEdge(int start, int end) {
graph[start][end] = 1;
graph[end][start] = 1;
void dfs(int vertex) {
printf("%d ", vertex);
visited[vertex] = 1;
for (int i = 0; i < vertices; i++) {
if (graph[vertex][i] == 1 && !visited[i]) {
dfs(i);
int main() {
printf("Enter the number of vertices and edges: ");
scanf("%d %d", &vertices, &edges);
initializeGraph();
printf("Enter the edges (start end):\n");
for (int i = 0; i < edges; i++) {
int start, end;
scanf("%d %d", &start, &end);
addEdge(start, end);
int startVertex;
printf("Enter the starting vertex for DFS: ");
scanf("%d", &startVertex);
printf("DFS starting from vertex %d: ", startVertex);
dfs(startVertex);
return 0;
}
14) BFS
#include <stdio.h>
#define MAX_VERTICES 100
#define MAX_QUEUE_SIZE 100
int graph[MAX_VERTICES][MAX_VERTICES];
int visited[MAX_VERTICES];
int vertices, edges;
int queue[MAX_QUEUE_SIZE];
int front = -1, rear = -1;
void initializeGraph() {
for (int i = 0; i < MAX_VERTICES; i++) {
visited[i] = 0;
for (int j = 0; j < MAX_VERTICES; j++) {
graph[i][j] = 0;
void addEdge(int start, int end) {
graph[start][end] = 1;
graph[end][start] = 1;
void enqueue(int vertex) {
if (rear == MAX_QUEUE_SIZE - 1) {
printf("Queue is full\n");
return;
if (front == -1) {
front = 0;
queue[++rear] = vertex;
int dequeue() {
if (front == -1) {
printf("Queue is empty\n");
return -1;
int vertex = queue[front++];
if (front > rear) {
front = rear = -1;
return vertex;
void bfs(int startVertex) {
printf("%d ", startVertex);
visited[startVertex] = 1;
enqueue(startVertex);
while (front != -1) {
int currentVertex = dequeue();
for (int i = 0; i < vertices; i++) {
if (graph[currentVertex][i] == 1 && !visited[i]) {
printf("%d ", i);
visited[i] = 1;
enqueue(i);
int main() {
printf("Enter the number of vertices and edges: ");
scanf("%d %d", &vertices, &edges);
initializeGraph();
printf("Enter the edges (start end):\n");
for (int i = 0; i < edges; i++) {
int start, end;
scanf("%d %d", &start, &end);
addEdge(start, end);
}
int startVertex;
printf("Enter the starting vertex for BFS: ");
scanf("%d", &startVertex);
printf("BFS starting from vertex %d: ", startVertex);
bfs(startVertex);
return 0;
15) Quick Sort
# include <stdio.h>
#include <stdlib.h>
#include <time.h>
int getBig(int *a, int i, int right, int pivot)
{
for (int k = i; k <= right; k++)
{
if (a[k] > pivot)
return k;
}
return right + 1;
}
int getSmall(int *a, int j, int left, int pivot)
{
for (int k = j; k >= left; k--)
{
if (a[k] < pivot)
return k;
}
return -1;
}
void swap(int *a, int *b)
{
int t = *a;
*a = *b;
*b = t;
}
void random_quick(int *a, int left, int right)
{
if (left >= right)
return;
int index = left + (rand() % (right - left)), i = left, j = right;
int pivot_index = index;
int pivot = a[index];
// storing index of element greater than pivot
i = getBig(a, i, right, pivot);
// storing index of element smaller than pivot
j = getSmall(a, j, left, pivot);
while (i <= j)
{
swap(&a[i], &a[j]);
i = getBig(a, i, right, pivot);
j = getSmall(a, j, left, pivot);
}
// after separating the smaller and greater elements, there are 3 cases
// possible
if (pivot_index > j && pivot_index > i)
{
// case 1. When the pivot element index is greater than both i and j
swap(&a[i], &a[pivot_index]);
random_quick(a, left, i - 1);
random_quick(a, i + 1, right);
}
else if (pivot_index < j && pivot_index < i)
{
// case 2. When the pivot element index is smaller than both i and j
swap(&a[j], &a[pivot_index]);
random_quick(a, left, j - 1);
random_quick(a, j + 1, right);
}
else
{
// the pivot element is at its origin position.
random_quick(a, left, pivot_index - 1);
random_quick(a, pivot_index + 1, right);
}
}
int main()
{
srand(time(0));
int num;
printf("Input number of elements you want to sort: ");
scanf("%d", &num);
printf("\nInput the numbers:\n");
int *arr = (int *)malloc(num * sizeof(int));
for (int i = 0; i < num; i++)
{
scanf("%d", &arr[i]);
}
random_quick(arr, 0, num - 1);
printf("\nSorted array: ");
for (int i = 0; i < num; i++)
{
printf("%d ", arr[i]);
}
free(arr);
printf("\n");
}
16) Selection Sort
#include <stdio.h>
#include <stdlib.h>
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void selectionSort(int *arr, int size) {
for (int i = 0; i < size - 1; i++) {
int min_index = i;
// Find the index of the minimum element in the remaining unsorted array
for (int j = i + 1; j < size; j++) {
if (arr[j] < arr[min_index]) {
min_index = j;
// Swap the found minimum element with the first element
swap(&arr[i], &arr[min_index]);
int main() {
int num;
printf("Input number of elements you want to sort: ");
scanf("%d", &num);
printf("\nInput the numbers:\n");
int *arr = (int *)malloc(num * sizeof(int));
for (int i = 0; i < num; i++) {
scanf("%d", &arr[i]);
selectionSort(arr, num);
printf("\nSorted array: ");
for (int i = 0; i < num; i++) {
printf("%d ", arr[i]);
free(arr);
printf("\n");
return 0;
}
18) Insertion Sort
#include <stdio.h>
#include <stdlib.h>
void insertionSort(int *arr, int size) {
int i, key, j;
for (i = 1; i < size; i++) {
key = arr[i];
j = i - 1;
// Move elements that are greater than key to one position ahead of their current position
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
arr[j + 1] = key;
int main() {
int num;
printf("Input number of elements you want to sort: ");
scanf("%d", &num);
printf("\nInput the numbers:\n");
int *arr = (int *)malloc(num * sizeof(int));
for (int i = 0; i < num; i++) {
scanf("%d", &arr[i]);
}
insertionSort(arr, num);
printf("\nSorted array: ");
for (int i = 0; i < num; i++) {
printf("%d ", arr[i]);
free(arr);
printf("\n");
return 0;
