Scribd
Upload
26 views25 pages

DS Practical Solution

The document provides implementations of various data structures and their operations in C, including stack and queue using arrays, as well as linked list operations. It covers push, pop, display for stack, and insert, delete, display for queue, along with linked list operations such as insertion at beginning and end, deletion, and displaying the list. Additionally, it includes a circular queue implementation with insert and display functionalities.

Uploaded by

stdsx146nissimt
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
26 views25 pages

DS Practical Solution

The document provides implementations of various data structures and their operations in C, including stack and queue using arrays, as well as linked list operations. It covers push, pop, display for stack, and insert, delete, display for queue, along with linked list operations such as insertion at beginning and end, deletion, and displaying the list. Additionally, it includes a circular queue implementation with insert and display functionalities.

Uploaded by

stdsx146nissimt
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 25

1.

Write algorithm and Perform PUSH operation on stack using Array implementation

#include<stdio.h>
#define MAX 5

// Function prototype
void push();

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

void main() {
int option;

do {
printf("\n__________ MENU __________\n");
printf("1. PUSH\n");
printf("2. Exit\n");
printf("__________________________\n");
printf("Enter your option: ");
scanf("%d", &option);

switch(option) {
case 1:
push();
break;

case 2:
printf("Exiting program...\n");
break;

default:
printf("INVALID OPTION\n");
}
} while(option != 2); // Add semicolon here
}

void push() {
int element;
if (top >= MAX - 1) {
printf("STACK OVERFLOW\n");
return;
}

printf("Enter element to push: ");


scanf("%d", &element);

top = top + 1;
stack[top] = element;

printf("Element %d pushed successfully.\n", element);


}

2. Write algorithm and Perform POP operation on stack using Array implementation

#include<stdio.h>
#define MAX 5

// Function prototypes
void push();
void pop();
void display();

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

void main() {
int option;

do {
printf("\n__________ MENU __________\n");
printf("1. PUSH\n");
printf("2. POP\n");
printf("3. EXIT\n");
printf("__________________________\n");
printf("Enter your option: ");
scanf("%d", &option);

switch(option) {
case 1:
push();
break;

case 2:
pop();
break;
case 3:
printf("Exiting program...\n");
break;

default:
printf("INVALID OPTION\n");
}
} while(option != 3);
}

void push() {
int element;
if (top >= MAX - 1) {
printf("STACK OVERFLOW\n");
return;
}

printf("Enter element to push: ");


scanf("%d", &element);

top = top + 1;
stack[top] = element;

printf("Element %d pushed successfully.\n", element);


}

void pop() {
int element;
if (top == -1) {
printf("STACK UNDERFLOW\n");
return;
}

element = stack[top];
top = top - 1;

printf("Element popped successfully: %d\n", element);


}

3. Performing following operations on Stack


i. PUSH
ii. POP
iii. Display

#include<stdio.h>
#define MAX 5

// Function prototypes
void push();
void pop();
void display();

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

void main() {
int option;

do {
printf("\n__________ MENU __________\n");
printf("1. PUSH\n");
printf("2. POP\n");
printf("3. DISPLAY\n");
printf("4. EXIT\n");
printf("__________________________\n");
printf("Enter your option: ");
scanf("%d", &option);

switch(option) {
case 1:
push();
break;

case 2:
pop();
break;

case 3:
display();
break;

case 4:
printf("Exiting program...\n");
break;

default:
printf("INVALID OPTION\n");
}
} while(option != 4);
}

void push() {
int element;
if (top >= MAX - 1) {
printf("STACK OVERFLOW\n");
return;
}

printf("Enter element to push: ");


scanf("%d", &element);

top = top + 1;
stack[top] = element;

printf("Element %d pushed successfully.\n", element);


}

void pop() {
int element;
if (top == -1) {
printf("STACK UNDERFLOW\n");
return;
}

element = stack[top];
top = top - 1;

printf("Element popped successfully: %d\n", element);


}

void display() {
int i;
if (top == -1) {
printf("STACK IS EMPTY\n");
return;
}

printf("Stack elements are:\n");


for(i = top; i >= 0; i--) {
printf("%d\n", stack[i]);
}
}
4. Perform Following operations on Queue using Array
i. Insert
ii. Delete
iii. Display

#include <stdio.h>
#define MAX 5 // Maximum size of Queue

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

// Function prototypes
void insert();
void delete_element();
void display();

void main() {
int choice;
do {
printf("\n------ MENU ------\n");
printf("1. Insert\n");
printf("2. Delete\n");
printf("3. Display\n");
printf("4. Exit\n");
printf("------------------\n");
printf("Enter your choice: ");
scanf("%d", &choice);

switch (choice) {
case 1:
insert();
break;
case 2:
delete_element();
break;
case 3:
display();
break;
case 4:
printf("Exiting program...\n");
break;
default:
printf("Invalid choice!\n");
}
} while (choice != 4);
}

void insert() {
int item;
if (rear == MAX - 1) {
printf("Queue Overflow! Cannot insert.\n");
return;
}
printf("Enter the element to insert: ");
scanf("%d", &item);

if (front == -1 && rear == -1) { // First element


front = 0;
rear = 0;
} else {
rear++;
}
queue[rear] = item;
printf("Inserted %d successfully.\n", item);
}

void delete_element() {
if (front == -1 || front > rear) {
printf("Queue Underflow! Cannot delete.\n");
return;
}
printf("Deleted element: %d\n", queue[front]);
front++;
}

void display() {
int i;
if (front == -1 || front > rear) {
printf("Queue is empty.\n");
return;
}
printf("Queue elements are: ");
for (i = front; i <= rear; i++) {
printf("%d ", queue[i]);
}
printf("\n");
}
5. Write algorithm and Perform Insert Operation on Queue using Array

Insert operation already in previous code

6. Perform following on Linked list


i. Insert at beginning
ii. Delete at End

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

void insert_at_begining(); // PROTOTYPE


void delete_at_end(); // PROTOTYPE

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

struct node *start = NULL;

void main() {
int option;
do {
printf("\n_____________MENU___________\n");
printf("1. Insert a node at the beginning\n");
printf("2. Delete a node at the end\n");
printf("3. Exit the program\n");
printf("____________________________\n");
printf("ENTER YOUR OPTION: ");
scanf("%d", &option);

switch(option) {
case 1:
insert_at_begining();
break;

case 2:
delete_at_end();
break;

case 3:
printf("Exiting the program...\n");
break;
default:
printf("INVALID CHOICE\n");
}
} while(option != 3); // ✅ CORRECTED
}

void insert_at_begining() {
struct node *temp;
temp = (struct node*)malloc(sizeof(struct node));
if (temp == NULL) {
printf("Out of memory\n");
return;
}

printf("ENTER THE VALUE TO BE INSERTED: ");


scanf("%d", &temp->data);
temp->next = start;
start = temp;

printf("ELEMENT INSERTED SUCCESSFULLY\n");


}

void delete_at_end() {
struct node *temp, *ptr;

if (start == NULL) {
printf("EMPTY LIST\n");
return;
} else if (start->next == NULL) {
ptr = start;
start = NULL;
printf("ELEMENT DELETED IS => %d\n", ptr->data);
free(ptr);
} else {
ptr = start;
while (ptr->next != NULL) {
temp = ptr;
ptr = ptr->next;
}
temp->next = NULL;
printf("ELEMENT DELETED IS => %d\n", ptr->data);
free(ptr);
}
}
7. Perform following on Linked list
i. Create a node
ii. Insert at the end
iii. Display

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

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

// Global pointer to start of list


struct node *start = NULL;

// Function declarations
void create_node();
void insert_at_end();
void display();

void main() {
int option;
do {
printf("\n_________ MENU _________\n");
printf("1. Create a node (if list is empty)\n");
printf("2. Insert at the end\n");
printf("3. Display the list\n");
printf("4. Exit\n");
printf("Enter your choice: ");
scanf("%d", &option);

switch(option) {
case 1:
create_node();
break;
case 2:
insert_at_end();
break;
case 3:
display();
break;
case 4:
printf("Exiting...\n");
break;
default:
printf("Invalid choice!\n");
}
} while(option != 4);
}

// i. Create first node


void create_node() {
if (start != NULL) {
printf("List already exists. Use insert option.\n");
return;
}

struct node *temp;


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

if (temp == NULL) {
printf("Memory allocation failed.\n");
return;
}

printf("Enter data: ");


scanf("%d", &temp->data);
temp->next = NULL;
start = temp;

printf("Node created successfully.\n");


}

// ii. Insert at the end


void insert_at_end() {
struct node *temp, *ptr;

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


if (temp == NULL) {
printf("Memory allocation failed.\n");
return;
}

printf("Enter data to insert: ");


scanf("%d", &temp->data);
temp->next = NULL;

if (start == NULL) {
start = temp;
} else {
ptr = start;
while (ptr->next != NULL) {
ptr = ptr->next;
}
ptr->next = temp;
}

printf("Node inserted at end.\n");


}

// iii. Display the list


void display() {
struct node *ptr;
if (start == NULL) {
printf("List is empty.\n");
return;
}

printf("Linked List: ");


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

8. Perform following on Linked list


i. Create a node
ii. Insert at any position
iii. Delete at beginning

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

struct node {
int data;
struct node *next;
};
struct node *start = NULL; // Global start pointer

// Function prototypes
void create_node();
void insert_at_position();
void delete_at_beginning();
void display();

void main() {
int choice;
do {
printf("\n------ MENU ------\n");
printf("1. Create First Node\n");
printf("2. Insert at Any Position\n");
printf("3. Delete at Beginning\n");
printf("4. Display List\n");
printf("5. Exit\n");
printf("------------------\n");
printf("Enter your choice: ");
scanf("%d", &choice);

switch (choice) {
case 1:
create_node();
break;
case 2:
insert_at_position();
break;
case 3:
delete_at_beginning();
break;
case 4:
display();
break;
case 5:
printf("Exiting program...\n");
break;
default:
printf("Invalid choice!\n");
}
} while (choice != 5);
}

void create_node() {
struct node *temp;
temp = (struct node *)malloc(sizeof(struct node));
if (temp == NULL) {
printf("Memory allocation failed!\n");
return;
}
printf("Enter data for first node: ");
scanf("%d", &temp->data);
temp->next = NULL;
if (start == NULL) {
start = temp;
printf("First node created successfully.\n");
} else {
printf("List already created. Use Insert option.\n");
free(temp);
}
}

void insert_at_position() {
struct node *temp, *ptr;
int pos, i = 1;

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


if (temp == NULL) {
printf("Memory allocation failed!\n");
return;
}

printf("Enter data to insert: ");


scanf("%d", &temp->data);
temp->next = NULL;

printf("Enter position to insert (starting from 1): ");


scanf("%d", &pos);

if (pos == 1) {
temp->next = start;
start = temp;
printf("Node inserted at beginning.\n");
} else {
ptr = start;
while (ptr != NULL && i < pos - 1) {
ptr = ptr->next;
i++;
}
if (ptr == NULL) {
printf("Position out of bounds!\n");
free(temp);
} else {
temp->next = ptr->next;
ptr->next = temp;
printf("Node inserted at position %d.\n", pos);
}
}
}

void delete_at_beginning() {
struct node *temp;
if (start == NULL) {
printf("List is empty, nothing to delete.\n");
return;
}
temp = start;
start = start->next;
printf("Deleted element: %d\n", temp->data);
free(temp);
}

void display() {
struct node *ptr;
if (start == NULL) {
printf("List is empty.\n");
return;
}
ptr = start;
printf("Linked List Elements: ");
while (ptr != NULL) {
printf("%d -> ", ptr->data);
ptr = ptr->next;
}
printf("NULL\n");
}

9. Perform insert operation on circular queue using array implementation and display result

#include <stdio.h>
#define MAX 5

// Function prototypes
void insert();
void display();

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

void main() {
int option;
do {
printf("\n_____ CIRCULAR QUEUE MENU _____\n");
printf("1. Insert\n");
printf("2. Display\n");
printf("3. Exit\n");
printf("Enter your choice: ");
scanf("%d", &option);

switch(option) {
case 1:
insert();
break;

case 2:
display();
break;

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

default:
printf("Invalid option!\n");
}
} while(option != 3);
}

// Insert (Enqueue) Operation


void insert() {
int item;

// Check for overflow


if ((front == 0 && rear == MAX - 1) || (front == rear + 1)) {
printf("Queue Overflow (Full)\n");
return;
}

printf("Enter the element to insert: ");


scanf("%d", &item);

// First insertion
if (front == -1) {
front = 0;
rear = 0;
}
else if (rear == MAX - 1 && front != 0) {
rear = 0; // wrap around
}
else {
rear = rear + 1;
}

queue[rear] = item;
printf("Inserted %d successfully.\n", item);
}

// Display Circular Queue


void display() {
int i;

if (front == -1) {
printf("Queue is empty.\n");
return;
}

printf("Queue elements are: ");


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

printf("\n");
}

10. Perform following operations on Queue using linked list implementation


i. Enqueue
ii. Dequeue
iii. Peak

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

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

// Global front and rear pointers


struct node *front = NULL;
struct node *rear = NULL;

// Function declarations
void enqueue();
void dequeue();
void peek();
void display();

void main() {
int option;

do {
printf("\n_________ QUEUE MENU _________\n");
printf("1. Enqueue (Insert)\n");
printf("2. Dequeue (Delete)\n");
printf("3. Peek (Front element)\n");
printf("4. Display Queue\n");
printf("5. Exit\n");
printf("Enter your choice: ");
scanf("%d", &option);

switch(option) {
case 1:
enqueue();
break;

case 2:
dequeue();
break;

case 3:
peek();
break;

case 4:
display();
break;

case 5:
printf("Exiting program...\n");
break;

default:
printf("Invalid option!\n");
}

} while(option != 5);
}

// i. Enqueue operation
void enqueue() {
int value;
struct node *temp;

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


if (temp == NULL) {
printf("Memory allocation failed!\n");
return;
}

printf("Enter value to enqueue: ");


scanf("%d", &value);

temp->data = value;
temp->next = NULL;

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

printf("Value %d enqueued successfully.\n", value);


}

// ii. Dequeue operation


void dequeue() {
struct node *temp;

if (front == NULL) {
printf("Queue Underflow! (Empty queue)\n");
return;
}

temp = front;
front = front->next;

printf("Dequeued element: %d\n", temp->data);


free(temp);

if (front == NULL) {
rear = NULL;
}
}

// iii. Peek operation


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

// Display the queue


void display() {
struct node *ptr = front;

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

printf("Queue elements: ");


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

printf("\n");
}
11. Perform following operations on Stack using linked list implementation
i. PUSH
ii. POP
iii. PEAK

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

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

struct node *top = NULL;

// Function prototypes
void push();
void pop();
void peek();
void display();

void main() {
int choice;
do {
printf("\n------ MENU ------\n");
printf("1. PUSH (Insert)\n");
printf("2. POP (Delete)\n");
printf("3. PEEK (Top Element)\n");
printf("4. Display Stack\n");
printf("5. Exit\n");
printf("------------------\n");
printf("Enter your choice: ");
scanf("%d", &choice);

switch (choice) {
case 1:
push();
break;
case 2:
pop();
break;
case 3:
peek();
break;
case 4:
display();
break;
case 5:
printf("Exiting program...\n");
break;
default:
printf("Invalid choice!\n");
}
} while (choice != 5);
}

void push() {
struct node *temp;
int item;

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


if (temp == NULL) {
printf("Memory allocation failed!\n");
return;
}

printf("Enter element to push: ");


scanf("%d", &item);

temp->data = item;
temp->next = top;
top = temp;
printf("%d pushed successfully.\n", item);
}

void pop() {
struct node *temp;
if (top == NULL) {
printf("Stack Underflow! Cannot pop.\n");
return;
}

temp = top;
printf("Popped element: %d\n", temp->data);
top = top->next;
free(temp);
}
void peek() {
if (top == NULL) {
printf("Stack is empty. No top element.\n");
return;
}
printf("Top element is: %d\n", top->data);
}

void display() {
struct node *temp;
if (top == NULL) {
printf("Stack is empty.\n");
return;
}
printf("Stack elements: ");
temp = top;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}

12. Implement a program to evaluate postfix Expression

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

#define MAX 100

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

// Function prototypes
void push(int);
int pop();
int evaluatePostfix(char[]);

void main() {
char expr[MAX];
int result;

printf("Enter a postfix expression (e.g., 23*54*+9-): ");


scanf("%s", expr);

result = evaluatePostfix(expr);

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


}

void push(int item) {


if (top == MAX - 1) {
printf("Stack Overflow!\n");
exit(1);
}
stack[++top] = item;
}

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

int evaluatePostfix(char expr[]) {


int i, op1, op2, result;

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


if (isdigit(expr[i])) {
push(expr[i] - '0'); // Convert char to int
} else {
op2 = pop();
op1 = pop();

switch (expr[i]) {
case '+':
result = op1 + op2;
break;
case '-':
result = op1 - op2;
break;
case '*':
result = op1 * op2;
break;
case '/':
result = op1 / op2;
break;
default:
printf("Invalid operator %c\n", expr[i]);
exit(1);
}
push(result);
}
}
return pop();
}

You might also like