1

Concepts of Data Structure

 2

*Array Implementation*

•Write a program to insert, delete, and search an element

in a one-dimensional array.

#include <iostream>

using namespace std;

void displayArray(int arr[], int n) {

cout << "Array elements: ";

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

cout << arr[i] << " ";

cout << endl;

void insertElement(int arr[], int &n, int pos, int value) {

for (int i = n; i > pos; i--) {

arr[i] = arr[i - 1];

arr[pos] = value;

n++;

void deleteElement(int arr[], int &n, int pos) {

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

arr[i] = arr[i + 1];

}
 3

n--;

void searchElement(int arr[], int n, int key) {

bool found = false;

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

if (arr[i] == key) {

cout << "Element " << key << " found at index " << i << "." << endl;

found = true;

break;

if (!found)

cout << "Element " << key << " not found in array." << endl;

int main() {

int arr[100], n;

cout << "Enter number of elements: ";

cin >> n;

cout << "Enter " << n << " elements:\n";

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

cin >> arr[i];

displayArray(arr, n);
 4

// Insertion

int insertPos, insertVal;

cout << "\nEnter position to insert: ";

cin >> insertPos;

cout << "Enter value to insert: ";

cin >> insertVal;

insertElement(arr, n, insertPos, insertVal);

cout << "After insertion:\n";

displayArray(arr, n);

// Deletion

int deletePos;

cout << "\nEnter position to delete: ";

cin >> deletePos;

deleteElement(arr, n, deletePos);

cout << "After deletion:\n";

displayArray(arr, n);

// Search

int key;

cout << "\nEnter element to search: ";

cin >> key;

searchElement(arr, n, key);

return 0;

}
 *Stack using Array*
5

•Write a program to implement a stack using arrays with push, pop,

and display operations.

#include <iostream>

using namespace std;

#define MAX 100

class Stack {

private:

int arr[MAX];

int top;

public:

Stack() {

top = -1;

// Push function

void push(int value) {

if (top >= MAX - 1) {

cout << "Stack Overflow!" << endl;

return;

arr[++top] = value;
 6

cout << value << " pushed into the stack." << endl;

// Pop function

void pop() {

if (top < 0) {

cout << "Stack Underflow!" << endl;

return;

cout << arr[top--] << " popped from the stack." << endl;

// Display function

void display() {

if (top < 0) {

cout << "Stack is empty!" << endl;

return;

cout << "Stack elements (top to bottom): ";

for (int i = top; i >= 0; i--) {

cout << arr[i] << " ";

cout << endl;

};

int main() {
 7

Stack s;

// Demonstrating stack operations

s.push(10);

s.push(20);

s.push(30);

s.display(); // Display current stack

s.pop(); // Pop top element

s.display(); // Display after popping

return 0;

// Output

10 pushed into the stack.

20 pushed into the stack.

30 pushed into the stack.

Stack elements (top to bottom): 30 20 10

30 popped from the stack.

Stack elements (top to bottom): 20 10

 *Queue using Array* 8

•Write a program to implement a linear queue using arrays with

enqueue, dequeue, and display operations.

#include <iostream>

using namespace std;

#define MAX 100

class Queue {

private:

int arr[MAX];

int front, rear;

public:

Queue() {

front = -1;

rear = -1;

// Enqueue operation

void enqueue(int value) {

if (rear == MAX - 1) {

cout << "Queue Overflow!" << endl;

return;

}
 9

if (front == -1) front = 0; // First element

arr[++rear] = value;

cout << value << " enqueued into the queue." << endl;

// Dequeue operation

void dequeue() {

if (front == -1 || front > rear) {

cout << "Queue Underflow!" << endl;

return;

cout << arr[front++] << " dequeued from the queue." << endl;

// Reset queue if all elements are dequeued

if (front > rear) {

front = -1;

rear = -1;

// Display operation

void display() {

if (front == -1 || front > rear) {

cout << "Queue is empty!" << endl;

return;
 10

cout << "Queue elements (front to rear): ";

for (int i = front; i <= rear; i++) {

cout << arr[i] << " ";

cout << endl;

};

int main() {

Queue q;

// Demonstrate queue operations

q.enqueue(10);

q.enqueue(20);

q.enqueue(30);

q.display(); // Show elements

q.dequeue(); // Remove one element

q.display(); // Show remaining elements

return 0;

// Output
 11

10 enqueued into the queue.

20 enqueued into the queue.

30 enqueued into the queue.

Queue elements (front to rear): 10 20 30

10 dequeued from the queue.

Queue elements (front to rear): 20 30

 *Circular Queue* 12

•Write a program to implement a circular queue using arrays.

#include <iostream>

using namespace std;

#define MAX 5 // Size of the circular queue

class CircularQueue {

private:

int arr[MAX];

int front, rear;

public:

CircularQueue() {

front = -1;

rear = -1;

// Enqueue operation

void enqueue(int value) {

if ((front == 0 && rear == MAX - 1) || (rear + 1 == front)) {

cout << "Queue Overflow! (Circular queue is full)" << endl;

return;

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

front = rear = 0;
 13

} else if (rear == MAX - 1 && front != 0) {

rear = 0;

} else {

rear++;

arr[rear] = value;

cout << value << " enqueued into the circular queue." << endl;

// Dequeue operation

void dequeue() {

if (front == -1) {

cout << "Queue Underflow! (Circular queue is empty)" << endl;

return;

cout << arr[front] << " dequeued from the circular queue." << endl;

if (front == rear) {

front = rear = -1; // Queue is now empty

} else if (front == MAX - 1) {

front = 0;

} else {

front++;

}
 14

// Display operation

void display() {

if (front == -1) {

cout << "Queue is empty!" << endl;

return;

cout << "Circular Queue elements: ";

if (rear >= front) {

for (int i = front; i <= rear; i++)

cout << arr[i] << " ";

} else {

for (int i = front; i < MAX; i++)

cout << arr[i] << " ";

for (int i = 0; i <= rear; i++)

cout << arr[i] << " ";

cout << endl;

};

int main() {

CircularQueue cq;

// Demonstrate circular queue operations

cq.enqueue(10);
 15

cq.enqueue(20);

cq.enqueue(30);

cq.enqueue(40);

cq.enqueue(50); // Should show overflow

cq.display();

cq.dequeue();

cq.dequeue();

cq.display();

cq.enqueue(60);

cq.enqueue(70); // Should fit due to circular nature

cq.display();

return 0;

// Output
10 enqueued into the circular queue.

20 enqueued into the circular queue.

30 enqueued into the circular queue.

40 enqueued into the circular queue.

Queue Overflow! (Circular queue is full)

 16

Circular Queue elements: 10 20 30 40

10 dequeued from the circular queue.

20 dequeued from the circular queue.

Circular Queue elements: 30 40

60 enqueued into the circular queue.

70 enqueued into the circular queue.

Circular Queue elements: 30 40 60 70

 *Linked List Operations* 17

• Write a program to create a singly linked list and perform

insertion, deletion, and traversal.

#include <iostream>

#include <forward_list>

using namespace std;

int main() {

forward_list<int> list;

// Insertion at the beginning

list.push_front(30);

list.push_front(20);

list.push_front(10);

cout << "List after insertion: ";

for (int val : list)

cout << val << " ";

cout << endl;

// Deletion of a specific value

list.remove(20); // removes all occurrences of 20

cout << "List after deleting 20: ";

for (int val : list)

cout << val << " ";

 18

cout << endl;

// Inserting at a specific position (after a given iterator)

auto it = list.before_begin(); // iterator to position before beginning

advance(it, 2); // move iterator two steps

list.insert_after(it, 25); // insert after 2nd position

cout << "List after inserting 25: ";

for (int val : list)

cout << val << " ";

cout << endl;

return 0;

// Output

List after insertion: 10 20 30

List after deleting 20: 10 30

List after inserting 25: 10 30 25

 *Doubly Linked List* 19

• Write a program to implement a doubly linked list with insertions

and deletions at both ends.

#include <iostream>

#include <list>

using namespace std;

int main() {

list<int> dll;

// Insertion at both ends

dll.push_front(20);

dll.push_back(40);

dll.push_front(10);

dll.push_back(50);

cout << "List after insertions: ";

for (int val : dll)

cout << val << " ";

cout << endl;

// Deletion from both ends

dll.pop_front(); // removes 10

dll.pop_back(); // removes 50

cout << "List after deletions: ";

for (int val : dll)

 20

cout << val << " ";

cout << endl;

return 0;

// Output
List after insertions: 10 20 40 50

List after deletions: 20 40

 *Stack using Linked List* 21

•Write a program to implement a stack using a linked list.

#include <iostream>

using namespace std;

// Node structure

struct Node {

int data;

Node* next;

};

// Stack class using linked list

class Stack {

private:

Node* top;

public:

Stack() {

top = nullptr;

// Push operation

void push(int value) {

Node* newNode = new Node();

newNode->data = value;

newNode->next = top;
 22

top = newNode;

cout << value << " pushed to stack." << endl;

// Pop operation

void pop() {

if (top == nullptr) {

cout << "Stack Underflow!" << endl;

return;

Node* temp = top;

cout << top->data << " popped from stack." << endl;

top = top->next;

delete temp;

// Display stack

void display() {

if (top == nullptr) {

cout << "Stack is empty." << endl;

return;

cout << "Stack (top to bottom): ";

Node* temp = top;

while (temp != nullptr) {

cout << temp->data << " ";

temp = temp->next;
 23

cout << endl;

};

int main() {

Stack s;

s.push(10);

s.push(20);

s.push(30);

s.display();

s.pop();

s.display();

return 0;

// Output
10 pushed to stack.

20 pushed to stack.

30 pushed to stack.

Stack (top to bottom): 30 20 10

30 popped from stack.

Stack (top to bottom): 20 10

 24
*Binary Search*
•Write a program to perform binary search on a sorted array.
#include <iostream>

using namespace std;

// Binary search function

int binarySearch(int arr[], int size, int key) {

int low = 0, high = size - 1;

while (low <= high) {

int mid = (low + high) / 2;

if (arr[mid] == key)

return mid; // Element found

if (arr[mid] < key)

low = mid + 1;

else

high = mid - 1;

return -1; // Element not found

int main() {

int arr[] = {5, 10, 15, 20, 25, 30, 35};

int size = sizeof(arr) / sizeof(arr[0]);

int key = 20;

 25

int result = binarySearch(arr, size, key);

if (result != -1)

cout << "Element " << key << " found at index " << result << "." << endl;

else

cout << "Element " << key << " not found in the array." << endl;

return 0;

// Output

Element 20 found at index 3.

 *Sorting Algorithms* 26

• Write a program to sort an array using the *Bubble Sort* and

*Selection Sort* algorithms.

#include <iostream>

using namespace std;

// Function to display array

void displayArray(int arr[], int size) {

for (int i = 0; i < size; i++)

cout << arr[i] << " ";

cout << endl;

// Bubble Sort

void bubbleSort(int arr[], int size) {

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

bool swapped = false;

for (int j = 0; j < size - i - 1; j++) {

if (arr[j] > arr[j + 1]) {

// Swap adjacent elements

swap(arr[j], arr[j + 1]);

swapped = true;

if (!swapped)

break; // Array is already sorted

}
 27

// Selection Sort

void selectionSort(int arr[], int size) {

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

int minIdx = i;

for (int j = i + 1; j < size; j++) {

if (arr[j] < arr[minIdx])

minIdx = j;

// Swap the found minimum element with the first element

swap(arr[i], arr[minIdx]);

int main() {

int arr1[] = {64, 25, 12, 22, 11};

int arr2[] = {64, 25, 12, 22, 11};

int size = sizeof(arr1) / sizeof(arr1[0]);

cout << "Original array: ";

displayArray(arr1, size);

// Bubble Sort

bubbleSort(arr1, size);

cout << "Array after Bubble Sort: ";

displayArray(arr1, size);
 28

// Selection Sort

selectionSort(arr2, size);

cout << "Array after Selection Sort: ";

displayArray(arr2, size);

return 0;

// Output

Original array: 64 25 12 22 11

Array after Bubble Sort: 11 12 22 25 64

Array after Selection Sort: 11 12 22 25 64

 *Binary Search Tree (BST)*
29

•Write a program to implement a Binary Search Tree with insert,

search, and in-order traversal functions.

#include <iostream>

using namespace std;

// Node structure

struct Node {

int data;

Node* left;

Node* right;

Node(int value) {

data = value;

left = right = nullptr;

};

// BST class

class BST {

private:

Node* root;

// Helper for insertion

Node* insert(Node* node, int value) {

if (node == nullptr)

return new Node(value);

 30

if (value < node->data)

node->left = insert(node->left, value);

else if (value > node->data)

node->right = insert(node->right, value);

return node;

// Helper for search

bool search(Node* node, int key) {

if (node == nullptr)

return false;

if (node->data == key)

return true;

if (key < node->data)

return search(node->left, key);

else

return search(node->right, key);

// Helper for in-order traversal

void inOrder(Node* node) {

if (node == nullptr)

return;

inOrder(node->left);

cout << node->data << " ";

 31

inOrder(node->right);

public:

BST() {

root = nullptr;

void insert(int value) {

root = insert(root, value);

void search(int key) {

if (search(root, key))

cout << key << " is present in the BST." << endl;

else

cout << key << " is NOT found in the BST." << endl;

void displayInOrder() {

cout << "In-order Traversal: ";

inOrder(root);

cout << endl;

};

int main() {
 32

BST tree;

// Inserting elements

tree.insert(50);

tree.insert(30);

tree.insert(70);

tree.insert(20);

tree.insert(40);

tree.insert(60);

tree.insert(80);

// In-order traversal

tree.displayInOrder();

// Searching values

tree.search(40);

tree.search(90);

return 0;

// Output

In-order Traversal: 20 30 40 50 60 70 80

40 is present in the BST.

90 is NOT found in the BST.