1.

Write a program to convert the Sparse Matrix into non-zero form and
vice versa.

Algorithm for Option 1: Sparse to Non-Zero Form

Input: A matrix with mostly zero elements

Output: Triplet representation (row, column, value) of non-zero elements

1. Start
2. Prompt user to enter the number of rows and columns.
3. Create a 2D matrix and read values from the user.
4. Display the original matrix.
5. For each element in the matrix:
 If the element is not zero:
 Print the row index, column index, and the value.
6. End

Algorithm for Option 2: Non-Zero Form to Sparse Matrix

Input: Triplet representation of non-zero values (row, col, value)

Output: Reconstructed sparse matrix

1. Start
2. Prompt user to enter the number of rows and columns.
3. Create a 2D matrix and initialize all elements to zero.
4. Ask user to input the number of non-zero elements.
5. For each non-zero element:
 Read row index, column index, and value.
 Place the value at the correct position in the matrix.
6. Display the reconstructed matrix.
7. End

CODE:

#include<iostream>

Page | 1
using namespace std;

class SparseMatrix {

public:

int row, col;

int matrix[10][10];

void getSparseMatrix() {

cout << "Enter the number of rows: ";

cin >> row;

cout << "Enter the number of columns: ";

cin >> col;

cout << "Enter the elements of the sparse matrix:" << endl;

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

for (int j = 0; j < col; j++) {

cin >> matrix[i][j];

void printSparseMatrix()

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

for (int j = 0; j < col; j++)

Page | 2
 cout << matrix[i][j] << " ";

cout << endl;

void toNonZeroForm()

cout << "Non-zero form:" << endl;

cout << "Row\tColumn\tValue" << endl;

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

for (int j = 0; j < col; j++)

if (matrix[i][j] != 0)

cout << i << "\t" << j << "\t" << matrix[i][j] << endl;

void fromNonZeroForm(int nonZero[][3], int size)

// Initialize the sparse matrix with zeros

Page | 3
 for (int i = 0; i < row; i++)

for (int j = 0; j < col; j++)

matrix[i][j] = 0;

// Populate the sparse matrix with non-zero values

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

matrix[nonZero[i][0]][nonZero[i][1]] = nonZero[i][2];

cout << "Sparse matrix:" << endl;

printSparseMatrix();

};

int main() {

SparseMatrix sm;

int choice;

cout << "Enter your choice (1 for sparse to non-zero, 2 for non-zero to

sparse): ";

cin >> choice;

if (choice == 1)

Page | 4
 {

[Link]();

cout << "Sparse matrix:" << endl;

[Link]();

[Link]();

else if (choice == 2)

cout << "Enter the number of rows: ";

cin >> [Link];

cout << "Enter the number of columns: ";

cin >> [Link];

int nonZero[10][3];

int size;

cout << "Enter the number of non-zero elements: ";

cin >> size;

cout << "Enter the non-zero elements (row, column, value):" <<

endl;

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

cin >> nonZero[i][0] >> nonZero[i][1] >> nonZero[i][2];

[Link](nonZero, size);

} else {

Page | 5
 cout << "Invalid choice." << endl;

return 0;

OUTPUT:

Enter your choice (1 for sparse to non-zero, 2 for non-zero to

sparse): 1

Enter the number of rows: 3

Enter the number of columns: 3

Enter the elements of the sparse matrix:

1 0 0

0 0 2

0 3 0

Sparse matrix:

1 0 0

0 0 2

0 3 0

Non-zero form:

Row Column Value

0 0 1

1 2 2

2 1 3

Page | 6
Enter your choice (1 for sparse to non-zero, 2 for non-zero to
sparse): 2

Enter the number of rows: 3

Enter the number of columns: 3

Enter the number of non-zero elements: 3

Enter the non-zero elements (row, column, value):

0 0 1

1 2 2

2 1 3

Sparse matrix:

1 0 0

0 0 2

0 3 0

BRIEF DISCUSSION:

1. Conversion to Triplet Form

A sparse matrix typically contains a high number of zero values. To save space and
improve processing time, we can convert the matrix to a triplet format, which only
stores the row index, column index, and non-zero value. This is useful in memory-
constrained systems or in applications like graphics and scientific computations.

2. Reconstruction from Triplet Form

Given the triplet data, the original matrix can be reconstructed by creating a matrix of
appropriate size and inserting the non-zero values at the specified positions. This is
crucial when we want to perform matrix operations using the actual 2D structure after
compact storage.

Page | 7
2. Write a program to implement Lower Triangular Matrix using one-
dimensional array.

ALGORITHM :

1. Start

2. Read the size n of the square matrix from the user.

3. Create an object matrix of class LowerTriangularMatrix with size n.

4. Inside the constructor:

 Initialize array matrix[10] to zero.

 The array size needed is (n * (n + 1)) / 2 (number of elements in lower
triangular matrix).

5. inputMatrix():

 For every row i from 0 to n-1:

 For every column j from 0 to i:
 Compute the index in the 1D array: index = (i * (i + 1)) / 2 + j.
 Prompt the user and store the input at that index.

6. displayMatrix():

 For every row i from 0 to n-1:

 For every column j from 0 to n-1:
 If i >= j (i.e., in lower triangle):
 Compute index: index = (i * (i + 1)) / 2 + j.
 Print the stored element.
 Else print 0.

7. End.

Code:
#include<iostream>

using namespace std;

class LowerTriangularMatrix

Page | 8
{

private:

int n;

int matrix[10];

public:

LowerTriangularMatrix(int size)

n = size;

for (int i = 0; i < (n * (n + 1)) / 2; i++)

matrix[i] = 0;

void inputMatrix()

cout << "Enter the elements of the lower triangular matrix:" << endl;

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

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

int index = (i * (i + 1)) / 2 + j;

cout << "Enter element [" << i << "][" << j << "]: ";

cin >> matrix[index];

void displayMatrix()

Page | 9
 for (int i = 0; i < n; i++)

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

if (i >= j)

int index = (i * (i + 1)) / 2 + j;

cout << matrix[index] << " ";

} else

cout << "0 ";

cout << endl;

};

int main() {

int n;

cout << "Enter the size of the matrix: ";

cin >> n;

LowerTriangularMatrix matrix(n);

[Link]();

cout << "Lower Triangular Matrix:" << endl;

[Link]();

return 0;

Page | 10
OUTPUT:

Enter the size of the matrix: 4

Enter the elements of the lower triangular matrix:

Enter element [0][0]: 8

Enter element [1][0]: 6

Enter element [1][1]: 2

Enter element [2][0]: 4

Enter element [2][1]: 7

Enter element [2][2]: 5

Enter element [3][0]: 3

Enter element [3][1]: 9

Enter element [3][2]: 5

Enter element [3][3]: 6

Lower Triangular Matrix:

8 0 0 0

6 2 0 0

4 7 5 0

3 9 5 6

BRIEF DISCUSSION:

This C++ program works with lower triangular matrices — matrices where all elements
above the main diagonal are zero.

Instead of using a full 2D array, it saves space by storing only the needed elements in a
1D array.

This method saves memory and is useful when working with large matrices that have a
lot of zero values.

Page | 11
3. Write a program to implement Upper Triangular Matrix using one-
dimensional array .

ALGORITHM :

1. Start the program.

2. Input the size n of the matrix from the user.

[Link] an object of the class UpperTriangularMatrix with size n.

4. Inside the constructor:

 Store n.
 Initialize the 1D array of size n(n+1)/2 elements with 0.

5. Call inputMatrix() function:

 For each row i from 0 to n-1

 For each column j from i to n-1 (only upper triangle including diagonal)
 Calculate index as (j * (j + 1)) / 2 + i
 Input the element and store at that index in the array.

6. Call displayMatrix() function:

 For each row i from 0 to n-1

 For each column j from 0 to n-1
 If i <= j, calculate index and print the element
 Else, print 0 (as it's the lower triangle)

7. End

CODE:
#include <iostream>

using namespace std;

class UpperTriangularMatrix

private:

int n;

Page | 12
 int matrix[10];

public:

UpperTriangularMatrix(int size)

n = size;

for (int i = 0; i < (n * (n + 1)) / 2; i++)

matrix[i] = 0;

void inputMatrix() {

cout << "Enter the elements of the upper triangular matrix:" << endl;

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

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

int index = (j * (j + 1)) / 2 + i;

cout << "Enter element [" << i << "][" << j << "]: ";

cin >> matrix[index];

void displayMatrix() {

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

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

if (i <= j)

Page | 13
 {

int index = (j * (j + 1)) / 2 + i;

cout << matrix[index] << " ";

} else {

cout << "0 ";

cout << endl;

};

int main() {

int n;

cout << "Enter the size of the matrix: ";

cin >> n;

UpperTriangularMatrix matrix(n);

[Link]();

cout << "Upper Triangular Matrix:" << endl;

[Link]();

return 0;

OUTPUT:

Enter the size of the matrix: 3

Enter the elements of the upper triangular matrix:

Enter element [0][0]: 5

Enter element [0][1]: 8

Enter element [0][2]: 7

Page | 14
Enter element [1][1]: 9

Enter element [1][2]: 6

Enter element [2][2]: 2

Upper Triangular Matrix:

5 8 7

0 9 6

0 0 2

BRIEF DISCUSSION:

This program is used to store and display an upper triangular matrix more efficiently
using a 1D array instead of a full 2D array.

 In an upper triangular matrix, all the elements below the diagonal are 0.
 To save space, the program only stores the non-zero elements (those on or above
the diagonal).
 It uses a formula to convert 2D positions to 1D indexes, so it knows where to
store or find each element.
 When displaying the matrix, it prints the stored numbers in the right positions,
and prints 0 for the elements below the diagonal.

This method reduces memory usage and works well for square matrices where many
elements are zero.

Page | 15
4. Write a program to implement Symmetric Matrix using one-dimensional
array .

ALGORITHM :

1. Start
2. Input the size n of the matrix.
3. Calculate the required size of the 1D array:

Size=n(n+1)2

4. Create a 1D array of that size and initialize all elements to 0.

5. For input:
 Loop through rows i = 0 to n-1
 For each row, loop through columns j = i to n-1 (upper triangle only)
 Use formula:

index=j(j+1)2+i

Store input at that index.

6. For output:
 Loop through all rows i and columns j
 If i ≤ j:
Use index = j(j+1)/2 + i
 Else:
Use index = i(i+1)/2 + j
 Display the value.
7. End

CODE :

#include <iostream>

using namespace std;

class SymmetricMatrix

Page | 16
 {

private:

int n;

int matrix[10];

public:

SymmetricMatrix(int size)

n = size;

for (int i = 0; i < (n * (n + 1)) / 2; i++)

matrix[i] = 0;

void inputMatrix()

cout << "Enter the elements of the symmetric matrix:" << endl;

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

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

int index = (j * (j + 1)) / 2 + i;

cout << "Enter element [" << i << "][" << j << "]: ";

cin >> matrix[index];

Page | 17
 }

void displayMatrix()

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

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

if (i <= j)

int index = (j * (j + 1)) / 2 + i;

cout << matrix[index] << " ";

} else {

int index = (i * (i + 1)) / 2 + j;

cout << matrix[index] << " ";

cout << endl;

};

int main() {

Page | 18
 int n;

cout << "Enter the size of the matrix: ";

cin >> n;

SymmetricMatrix matrix(n);

[Link]();

cout << "Symmetric Matrix:" << endl;

[Link]();

return 0;

OUTPUT:

Enter the size of the matrix: 4

Enter the elements of the symmetric matrix:

Enter element [0][0]: 5

Enter element [0][1]: 9

Enter element [0][2]: 5

Enter element [0][3]: 2

Enter element [1][1]: 4

Enter element [1][2]: 3

Enter element [1][3]: 6

Enter element [2][2]: 8

Enter element [2][3]: 7

Enter element [3][3]: 9

Page | 19
Symmetric Matrix:

5 9 5 2

9 4 3 6

5 3 8 7

2 6 7 9

BRIEF DISCUSSION :

This program demonstrates how to efficiently store and display a symmetric matrix
using a one-dimensional array instead of a two-dimensional one. It’s a smart way to
save memory and understand how symmetric matrices work in programming.

Page | 20
5. Write a program to represent a polynomial using array. Also, add two
polynomials represented using array.

ALGORITHM :
[Link]

[Link] a class poly

Declare:

 Integer array a[20] to store polynomial coefficients.

 Integer n to store the degree of the polynomial.

Step 3: Define input() function

 Ask user to input the degree n.

 Loop from 0 to n:
 Read n+1 coefficients into array a.

Step 4: Define display() function

 Print the polynomial in human-readable format.

 Start from the highest degree and print terms in the form:

ax^n + bx^(n-1) + ... + constant

 Skip zero coefficients.

Step 5: Define addpoly(poly obj)

 Create a temporary poly object r to store result.

 Compare degrees of both polynomials (n and obj.n).

For matching degrees:

 Add corresponding coefficients.

For unmatched degrees:

 Copy remaining coefficients from the polynomial with higher degree.

Set r.n as the maximum of n and obj.n.

Return r.

Page | 21
Step 6: In main()

 Create three objects: p1, p2, p.

 Call input() for p1 and p2 to read polynomials.
 Call display() to show entered polynomials.
 Add polynomials using p = [Link](p2);
 Display result using [Link]().

Step 7: End

CODE :
#include<iostream>

using namespace std;

class poly

private:

int a[20],n;

public:

poly addpoly(poly obj)

poly r;

if(n>obj.n)

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

r.a[i]=a[i]+obj.a[i];

for(int i=obj.n+1;i<=n;i++)

r.a[i]=a[i];

r.n=n;

else if (n < obj.n)

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

Page | 22
 {

r.a[i] = a[i] + obj.a[i];

for (int i = n + 1; i <= obj.n; i++)

r.a[i] = obj.a[i];

r.n = obj.n;

else

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

r.a[i] = a[i] + obj.a[i];

r.n = obj.n;

return (r);

void input()

cout <<"\nEnter degree of polynomial: ";

cin >> n;

cout <<"\nEnter " << n+1 << " coefficients:";

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

cin >> a[i];

void display()

cout<<"\n Polynomial = ";

for(int i=n;i>=0;i--)

Page | 23
 {

if(a[i]!=0)

if(i==0)

cout<<a[i]<<" + " ;

else if(i==1)

cout<<a[i]<<"x + ";

else

cout<<a[i]<<"x^"<<i<<" + ";

else

continue;

cout<<"\b\b ";

};

int main()

poly p1, p2, p;

cout << "\n Enter first polynomial:\n";

[Link]();

[Link]();

Page | 24
 cout << "\n Enter second polynomial:\n";

[Link]();

[Link]();

p= [Link](p2);

cout << "\n Resultant polynomial after addition:\n";

[Link]();

return 0;

OUTPUT:
Enter first polynomial:
Enter degree of polynomial: 3
Enter 4 coefficients:1
2
3
4
Polynomial = 4x^3 + 3x^2 + 2x + 1
Enter second polynomial:
Enter degree of polynomial: 4
Enter 5 coefficients:4
5
6
4
3
Polynomial = 3x^4 + 4x^3 + 6x^2 + 5x + 4

Resultant polynomial after addition:

Polynomial = 3x^4 + 8x^3 + 9x^2 + 7x +

Page | 25
BRIEF DISCUSSION :
This program adds two polynomials using a class in C++. Each polynomial is stored in
an array where the index shows the power of x, and the value is the coefficient. The user
enters the degree and coefficients of two polynomials. The program adds them term by
term using the addpoly() function and stores the result in a new polynomial. The
display() function prints the polynomials in a readable form like 5x^2 + 3x + 2. This
program shows how object-oriented programming can be used to handle polynomial
operations in a simple way.

Page | 26
6. Implement the following using a Singly Linked List.

i) Insertion-in the beginning, at the end, after a specific position and after a
specific element of the list.

ii) Deletion- from the beginning, from the end, from a specific position and
a specific element of the list.

iii) Search a given element.

iv)Reverse the list.

ALGORITHM :
1. Start the Program .

2. Define a class Node:

Members:

int data — stores the value.

Node* next — pointer to the next node.

Constructor:

 Initializes data with given value.

 Sets next = NULL.

3. Define a class SinglyLinkedList:

Private Member:

Node* head — pointer to the first node of the list.

Public Member Functions:

Constructor: Initializes head = NULL

4. Insertion Operations

At Beginning:

 Create new node.

Page | 27
  Set new node’s next to head.
 Update head to new node.

At End:

 Create new node.

 If list is empty, set head = new node.
 Else, traverse to the last node and update its next to new node.

After Position:

 Traverse to the given position.

 Insert new node after that position by adjusting pointers.

After Element:

 Find the node with the given data.

 Insert new node after that node.

5. Deletion Operations

From Beginning:

 Check if list is empty.

 Update head to head->next.
 Delete the first node.

From End:

 Check if list is empty or has one node.

 Else, traverse to second last node and delete the last node.

From Specific Position:

 Traverse to one node before the given position.

 Adjust links to skip and delete the target node.

Delete Specific Element:

 Find the node before the one containing the target value.
 Adjust pointers to skip and delete that node.

6. Search Operation

Page | 28
  Traverse from head and compare each node’s data.
 If match found, print position.
 Else, show "not found" message.

7. Reverse Operation

 Initialize three pointers: prev = NULL, curr = head, next = NULL.

 Loop through the list:
 Save curr->next in next.
 Reverse the link: curr->next = prev.
 Move prev and curr one step forward.
 After loop, set head = prev.

8. Display Operation

 Traverse list from head and print each data value until NULL.

9. End of Program .

CODE :
#include <iostream>

using namespace std;

class Node

public:

int data;

Node* next;

Node(int val)

data = val;

next = NULL;

};

class SinglyLinkedList

Page | 29
{

private:

Node* head;

public:

SinglyLinkedList()

head = NULL;

// Insert at beginning

void insertAtBeginning(int val)

Node* newNode = new Node(val);

newNode->next = head;

head = newNode;

// Insert at end

void insertAtEnd(int val)

Node* newNode = new Node(val);

if (head == NULL)

head = newNode;

return;

Node* temp = head;

while (temp->next != NULL)

Page | 30
 temp = temp->next;

temp->next = newNode;

// Insert after a specific position

void insertAfterPosition(int val, int pos)

Node* newNode = new Node(val);

if (head == NULL || pos < 1)

cout << "Invalid position.\n";

delete newNode;

return;

Node* temp = head;

for (int i = 1; i < pos; ++i)

if (temp == NULL)

cout << "Position out of range.\n";

delete newNode;

return;

temp = temp->next;

if (temp == NULL)

Page | 31
 cout << "Position out of range.\n";

delete newNode;

return;

newNode->next = temp->next;

temp->next = newNode;

// Insert after a specific element

void insertAfterElement(int val, int element)

Node* temp = head;

while (temp != NULL && temp->data != element)

temp = temp->next;

if (temp == NULL)

cout << "Element not found.\n";

return;

Node* newNode = new Node(val);

newNode->next = temp->next;

temp->next = newNode;

// Delete from beginning

void deleteFromBeginning()

Page | 32
 {

if (head == NULL)

cout << "List is empty.\n";

return;

Node* temp = head;

head = head->next;

delete temp;

// Delete from end

void deleteFromEnd()

if (head == NULL)

cout << "List is empty.\n";

return;

if (head->next == NULL)

delete head;

head = NULL;

return;

Node* temp = head;

while (temp->next->next != NULL)

Page | 33
 temp = temp->next;

delete temp->next;

temp->next = NULL;

// Delete from specific position

void deleteFromPosition(int pos)

if (head == NULL || pos < 1)

cout << "Invalid position.\n";

return;

if (pos == 1)

deleteFromBeginning();

return;

Node* temp = head;

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

if (temp == NULL)

cout << "Position out of range.\n";

return;

temp = temp->next;

Page | 34
 }

if (temp == NULL || temp->next == NULL)

cout << "Position out of range.\n";

return;

Node* del = temp->next;

temp->next = del->next;

delete del;

// Delete a specific element

void deleteElement(int val)

if (head == NULL)

cout << "List is empty.\n";

return;

if (head->data == val)

deleteFromBeginning();

return;

Node* temp = head;

while (temp->next != NULL && temp->next->data != val)

temp = temp->next;

Page | 35
 if (temp->next == NULL)

cout << "Element not found.\n";

return;

Node* del = temp->next;

temp->next = del->next;

delete del;

// Search an element

void search(int val)

Node* temp = head;

int pos = 1;

while (temp != NULL)

if (temp->data == val)

cout << "Element found at position: " << pos << endl;

return;

temp = temp->next;

++pos;

cout << "Element not found.\n";

// Reverse the list

void reverseList()

Page | 36
 {

Node* prev = NULL;

Node* curr = head;

Node* next = NULL;

while (curr != NULL)

next = curr->next;

curr->next = prev;

prev = curr;

curr = next;

head = prev;

// Display the list

void display()

Node* temp = head;

cout << "List: ";

while (temp != NULL)

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

temp = temp->next;

cout << "NULL\n";

};

Page | 37
// Main function

int main() {

SinglyLinkedList list;

int choice, value, pos, element;

do {

cout << "1. Insert at Beginning\n";

cout << "2. Insert at End\n";

cout << "3. Insert after Position\n";

cout << "4. Insert after Element\n";

cout << "5. Delete from Beginning\n";

cout << "6. Delete from End\n";

cout << "7. Delete from Position\n";

cout << "8. Delete Element\n";

cout << "9. Search Element\n";

cout << "10. Reverse List\n";

cout << "11. Display List\n";

cout << "12. Exit\n";

cout << "Enter choice: ";

cin >> choice;

switch (choice)

case 1:

cout << "Enter value: ";

cin >> value;

[Link](value);

Page | 38
 break;

case 2:

cout << "Enter value: ";

cin >> value;

[Link](value);

break;

case 3:

cout << "Enter value and position: ";

cin >> value >> pos;

[Link](value, pos);

break;

case 4:

cout << "Enter value and element: ";

cin >> value >> element;

[Link](value, element);

break;

case 5:

[Link]();

break;

case 6:

[Link]();

break;

case 7:

cout << "Enter position: ";

cin >> pos;

[Link](pos);

break;

case 8:

Page | 39
 cout << "Enter element to delete: ";

cin >> element;

[Link](element);

break;

case 9:

cout << "Enter element to search: ";

cin >> value;

[Link](value);

break;

case 10:

[Link]();

break;

case 11:

[Link]();

break;

case 12:

cout << "Exiting...\n";

break;

default:

cout << "Invalid choice.\n";

} while (choice != 12);

return 0;

OUTPUT:

1. Insert at Beginning

2. Insert at End

3. Insert after Position

Page | 40
4. Insert after Element

5. Delete from Beginning

6. Delete from End

7. Delete from Position

8. Delete Element

9. Search Element

10. Reverse List

11. Display List

12. Exit

Enter choice: 1

Enter value: 10

1. Insert at Beginning

2. Insert at End

3. Insert after Position

4. Insert after Element

5. Delete from Beginning

6. Delete from End

7. Delete from Position

8. Delete Element

9. Search Element

10. Reverse List

11. Display List

12. Exit

Enter choice: 2

Enter value: 20

1. Insert at Beginning

Page | 41
2. Insert at End

3. Insert after Position

4. Insert after Element

5. Delete from Beginning

6. Delete from End

7. Delete from Position

8. Delete Element

9. Search Element

10. Reverse List

11. Display List

12. Exit

Enter choice: 1

Enter value: 30

1. Insert at Beginning

2. Insert at End

3. Insert after Position

4. Insert after Element

5. Delete from Beginning

6. Delete from End

7. Delete from Position

8. Delete Element

9. Search Element

10. Reverse List

11. Display List

12. Exit

Enter choice: 3

Page | 42
Enter value and position: 40 2

1. Insert at Beginning

2. Insert at End

3. Insert after Position

4. Insert after Element

5. Delete from Beginning

6. Delete from End

7. Delete from Position

8. Delete Element

9. Search Element

10. Reverse List

11. Display List

12. Exit

Enter choice: 11

List: 30 -> 10 -> 40 -> 20 -> NULL

1. Insert at Beginning

2. Insert at End

3. Insert after Position

4. Insert after Element

5. Delete from Beginning

6. Delete from End

7. Delete from Position

8. Delete Element

9. Search Element

10. Reverse List

11. Display List

Page | 43
12. Exit

Enter choice: 10

1. Insert at Beginning

2. Insert at End

3. Insert after Position

4. Insert after Element

5. Delete from Beginning

6. Delete from End

7. Delete from Position

8. Delete Element

9. Search Element

10. Reverse List

11. Display List

12. Exit

Enter choice: 11

List: 20 -> 40 -> 10 -> 30 -> NULL

1. Insert at Beginning

2. Insert at End

3. Insert after Position

4. Insert after Element

5. Delete from Beginning

6. Delete from End

7. Delete from Position

8. Delete Element

9. Search Element

10. Reverse List

Page | 44
11. Display List

12. Exit

Enter choice: 9

Enter element to search: 40

Element found at position: 2

1. Insert at Beginning

2. Insert at End

3. Insert after Position

4. Insert after Element

5. Delete from Beginning

6. Delete from End

7. Delete from Position

8. Delete Element

9. Search Element

10. Reverse List

11. Display List

12. Exit

Enter choice: 5

1. Insert at Beginning

2. Insert at End

3. Insert after Position

4. Insert after Element

5. Delete from Beginning

6. Delete from End

7. Delete from Position

8. Delete Element

Page | 45
9. Search Element

10. Reverse List

11. Display List

12. Exit

Enter choice: 7

Enter position: 3

1. Insert at Beginning

2. Insert at End

3. Insert after Position

4. Insert after Element

5. Delete from Beginning

6. Delete from End

7. Delete from Position

8. Delete Element

9. Search Element

10. Reverse List

11. Display List

12. Exit

Enter choice: 11

List: 40 -> 10 -> NULL

1. Insert at Beginning

2. Insert at End

3. Insert after Position

4. Insert after Element

5. Delete from Beginning

6. Delete from End

Page | 46
7. Delete from Position

8. Delete Element

9. Search Element

10. Reverse List

11. Display List

12. Exit

Enter choice: 12

Exiting...

BRIEF DISCUSSION :

This C++ program implements a singly linked list using object-oriented principles with
two classes: Node and SinglyLinkedList.

The Node class models the fundamental unit of the list.

The SinglyLinkedList class encapsulates the operations on the list such as insertions,
deletions, search, reverse, and display.

The program supports interactive menu-driven operations, allowing the user to test and
visualize how the list changes dynamically with each operation.

All memory management is handled properly using new and delete. Edge cases such as
operations on an empty list or invalid positions are also checked and handled gracefully.

Page | 47
7. Implement the following using a Doubly Linked List.

i) ) Insertion-in the beginning, at the end, after a specific position and after
a specific element of the list.

ii) Deletion- from the beginning, from the end, from a specific position and
a specific element of the list.

ALGORITHM :

1. Start the Program

2. Define a Class Node:

Data Members:

int data – stores the value of the node.

Node* prev – pointer to the previous node.

Node* next – pointer to the next node.

Constructor:

 Initializes data with the provided value.

 Sets both prev and next to NULL.

3. Define a Class DoublyLinkedList:

Private Member:

Node* head – points to the first node in the list.

Public Member Functions:

Constructor initializes head = NULL.

4. Insertion Operations

a) Insert at Beginning

 Input the value.

 Create a new node.

Page | 48
  If head is not NULL, set head->prev to the new node and new Node-> next to
head.
 Update head to the new node.

b) Insert at End

 Input the value.

 Create a new node.
 If the list is empty, make head = newNode.
 Else, traverse to the last node and update its next to newNode and new Node->
prev to last node.

c) Insert After a Specific Position

 Input position and value.

 Traverse to the node at the specified position.
 Create a new node and insert it after the found node by updating the links.

d) Insert After a Specific Element

 Input the target element and the new value.

 Search for the node with the target element.
 Insert new node after that node by adjusting pointers.

5. Deletion Operations

a) Delete from Beginning

 If the list is empty, return.

 Move head to head->next.
 If new head exists, set head->prev = NULL.
 Delete the old head node.

b) Delete from End

 If list is empty, return.

 If only one node, delete it and set head = NULL.
 Else, traverse to last node, update second last node’s next = NULL and delete the
last node.

c) Delete from Specific Position

Page | 49
  Input the position.
 Traverse to the node at the given position.
 Adjust the previous and next pointers to unlink the node.
 Delete the node.

d) Delete a Specific Element

 Input the value to delete.

 Search for the node with the matching data.
 Adjust previous and next node links.
 Delete the matched node.

6. Display the List

 Traverse from head to end.

 Print each node’s data followed by <->.
 Print NULL at the end.

7. End the Program .

CODE:
#include <iostream>

using namespace std;

class Node

public:

int data;

Node* prev;

Node* next;

Node(int value)

data=value;

prev=NULL;

next=NULL;

Page | 50
 }

};

class DoublyLinkedList

private:

Node* head;

public:

DoublyLinkedList()

head=NULL;

void insertAtBeginning()

int data;

cout<<"Enter data to insert at beginning: ";

cin>>data;

Node* newNode=new Node(data);

if(head)

head->prev=newNode;

newNode->next=head;

head=newNode;

void insertAtEnd()

int data;

cout<<"Enter data to insert at end: ";

Page | 51
 cin>>data;

Node* newNode=new Node(data);

if(!head)

head=newNode;

return;

Node* temp=head;

while(temp->next)

temp=temp->next;

temp->next=newNode;

newNode->prev=temp;

void insertAfterPosition()

int position,data;

cout<<"Enter position (0-based) after which to insert: ";

cin>>position;

cout<< "Enter data to insert: ";

cin>>data;

if(position<0)

return;

Node* temp=head;

int index=0;

while(temp&&index<position)

temp=temp->next;

index++;

Page | 52
 }

if(!temp)

return;

Node* newNode=new Node(data);

newNode->next=temp->next;

newNode->prev=temp;

if(temp->next)

temp->next->prev=newNode;

temp->next=newNode;

void insertAfterElement()

int element,data;

cout<<"Enter element after which to insert: ";

cin>>element;

cout<< "Enter data to insert: ";

cin>>data;

Node* temp=head;

while(temp&&temp->data!=element)

temp=temp->next;

if(!temp)

return;

Node* newNode=new Node(data);

newNode->next=temp->next;

newNode->prev=temp;

if (temp->next)

temp->next->prev=newNode;

temp->next=newNode;

Page | 53
}

void deleteFromBeginning()

if(!head)

return;

Node* temp=head;

head=head->next;

if(head)

head->prev=NULL;

delete temp;

cout << "Deleted node from beginning.\n";

void deleteFromEnd()

if(!head)

return;

Node* temp=head;

if(!temp->next)

delete temp;

head=NULL;

return;

while(temp->next)

temp=temp->next;

temp->prev->next=NULL;

delete temp;

cout<<"Deleted node from end.\n";

Page | 54
}

void deleteFromPosition()

int position;

cout<<"Enter position (0-based) to delete: ";

cin>>position;

if(position<0||!head)

return;

Node* temp=head;

int index=0;

while(temp&&index<position)

temp=temp->next;

index++;

if(!temp)

return;

if(temp->prev)

temp->prev->next=temp->next;

else

head=temp->next;

if(temp->next)

temp->next->prev=temp->prev;

delete temp;

cout<<"Deleted node from position "<<position<<".\n";

void deleteElement()

Page | 55
 int element;

cout<<"Enter element to delete: ";

cin>>element;

Node* temp=head;

while(temp&&temp->data!=element)

temp=temp->next;

if(!temp)

return;

if(temp->prev)

temp->prev->next=temp->next;

else

head=temp->next;

if(temp->next)

temp->next->prev=temp->prev;

delete temp;

cout<<"Deleted element "<<element<<".\n";

void display()

Node* temp=head;

if(!temp)

cout<<"List is empty!\n";

return;

while(temp)

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

Page | 56
 temp=temp->next;

cout<<"NULL\n";

};

int main()

DoublyLinkedList dll;

int ch;

do {

cout << "1. Insert at Beginning\n";

cout << "2. Insert at End\n";

cout << "3. Insert after Position\n";

cout << "4. Insert after Element\n";

cout << "5. Delete from Beginning\n";

cout << "6. Delete from End\n";

cout << "7. Delete from Position\n";

cout << "8. Delete Element\n";

cout << "9. Display List\n";

cout << "10. Exit\n";

cout << "Enter your choice: ";

cin >> ch;

switch (ch)

case 1:

[Link]();

break;

case 2:

Page | 57
 [Link]();

break;

case 3:

[Link]();

break;

case 4:

[Link]();

break;

case 5:

[Link]();

break;

case 6:

[Link]();

break;

case 7:

[Link]();

break;

case 8:

[Link]();

break;

case 9:

[Link]();

break;

case 10: cout << "Exiting...\n";

break;

default: cout << "Invalid choice.\n";

} while (ch!=10);

Page | 58
 return 0;

OUTPUT:

1. Insert at Beginning

2. Insert at End

3. Insert after Position

4. Insert after Element

5. Delete from Beginning

6. Delete from End

7. Delete from Position

8. Delete Element

9. Display List

10. Exit

Enter your choice: 1

Enter data to insert at beginning: 10

1. Insert at Beginning

2. Insert at End

3. Insert after Position

4. Insert after Element

5. Delete from Beginning

6. Delete from End

7. Delete from Position

8. Delete Element

9. Display List

10. Exit

Enter your choice: 2

Page | 59
Enter data to insert at end: 20

1. Insert at Beginning

2. Insert at End

3. Insert after Position

4. Insert after Element

5. Delete from Beginning

6. Delete from End

7. Delete from Position

8. Delete Element

9. Display List

10. Exit

Enter your choice: 1

Enter data to insert at beginning: 30

1. Insert at Beginning

2. Insert at End

3. Insert after Position

4. Insert after Element

5. Delete from Beginning

6. Delete from End

7. Delete from Position

8. Delete Element

9. Display List

10. Exit

Enter your choice: 3

Enter position (0-based) after which to insert: 2

Enter data to insert: 40

Page | 60
1. Insert at Beginning

2. Insert at End

3. Insert after Position

4. Insert after Element

5. Delete from Beginning

6. Delete from End

7. Delete from Position

8. Delete Element

9. Display List

10. Exit

Enter your choice: 9

30 <-> 10 <-> 20 <-> 40 <-> NULL

1. Insert at Beginning

2. Insert at End

3. Insert after Position

4. Insert after Element

5. Delete from Beginning

6. Delete from End

7. Delete from Position

8. Delete Element

9. Display List

10. Exit

Enter your choice: 5

Deleted node from beginning.

1. Insert at Beginning

2. Insert at End

Page | 61
3. Insert after Position

4. Insert after Element

5. Delete from Beginning

6. Delete from End

7. Delete from Position

8. Delete Element

9. Display List

10. Exit

Enter your choice: 8

Enter element to delete: 10

Deleted element 10.

1. Insert at Beginning

2. Insert at End

3. Insert after Position

4. Insert after Element

5. Delete from Beginning

6. Delete from End

7. Delete from Position

8. Delete Element

9. Display List

10. Exit

Enter your choice: 7

Enter position (0-based) to delete: 2

1. Insert at Beginning

2. Insert at End

3. Insert after Position

Page | 62
4. Insert after Element

5. Delete from Beginning

6. Delete from End

7. Delete from Position

8. Delete Element

9. Display List

10. Exit

Enter your choice: 9

20 <-> 40 <-> NULL

1. Insert at Beginning

2. Insert at End

3. Insert after Position

4. Insert after Element

5. Delete from Beginning

6. Delete from End

7. Delete from Position

8. Delete Element

9. Display List

10. Exit

Enter your choice: 10

Exiting...

BRIEF DISCUSSION :

This C++ program implements a doubly linked list using two classes: Node and
DoublyLinkedList. Each node stores data along with pointers to both the previous and
next nodes, allowing bidirectional traversal. The list supports various operations
including insertion (at beginning, end, after a position or element), deletion (from
beginning, end, a position or by value), and displaying the list. All operations are

Page | 63
handled using proper pointer updates, and edge cases like empty lists or invalid
positions are managed safely. The program uses a menu-driven approach, making it
interactive and easy to test.

Page | 64
8. Write a program to perform Stack operations using Array .

ALGORITHM :

1. Start

2. Initialize Stack

 Create an integer array A[SIZE] of fixed size.

 Initialize a variable top = -1 (indicating the stack is empty).

3. Loop Menu Until Exit

Show menu with options:

1: Push

2: Pop

3: Display

4: Exit

4. If User Chooses Push

 Check if top == SIZE - 1 (Stack Full)

 If yes, print "Stack overflow".
 Else:

Read item from user.

Increment top by 1.

Set A[top] = item.

5. If User Chooses Pop

 Check if top == -1 (Stack Empty)

 If yes, print "Stack underflow".
 Else:

Print A[top] as popped item.

Page | 65
Decrement top.

6. If User Chooses Display

Check if top == -1

If yes, print "Stack underflow".

Else:

Loop from top to 0 and print each element.

7. If User Chooses Exit

Terminate the program.

CODE:
#include<iostream>

#include<stdlib.h>

using namespace std;

#define SIZE 5

class Stack

private: int A[SIZE],top;

public:

Stack()

top=-1;

void push()

if(top==SIZE-1)

cout<<"\nStack overflow,item cannot be pushed";

Page | 66
 }

else

int item;

cout<<"\nEnter the item to push:";

cin>>item;

top=top+1;

A[top]=item;

void pop()

if(top==-1)

cout<<"\nStack underflow,item cannot be popped";

else

cout<<"\nPopped item is:"<<A[top];

top=top-1;

void display()

if(top==-1)

cout<<"\nStack underflow,item cannot be displayed";

Page | 67
 else

int i;

cout<<"\nStack elements are:-\n";

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

cout<<A[i]<<"\n";

};

int main()

Stack s;

int ch;

while(1)

cout<<"\n1 for push";

cout<<"\n2 for pop";

cout<<"\n3 for display";

cout<<"\n4 for exit";

cout<<"\nEnter your choice:";

cin>>ch;

switch(ch)

case 1:[Link]();

break;

case 2:[Link]();

Page | 68
 break;

case 3:[Link]();

break;

case 4:exit(0);

return 0;

OUTPUT:

1 for push

2 for pop

3 for display

4 for exit

Enter your choice:1

Enter the item to push:10

1 for push

2 for pop

3 for display

4 for exit

Enter your choice:1

Enter the item to push:20

1 for push

2 for pop

3 for display

4 for exit

Enter your choice:1

Page | 69
Enter the item to push:30

1 for push

2 for pop

3 for display

4 for exit

Enter your choice:3

Stack elements are:-

30

20

10

1 for push

2 for pop

3 for display

4 for exit

Enter your choice:2

Popped item is:30

1 for push

2 for pop

3 for display

4 for exit

Enter your choice:2

Popped item is:20

1 for push

2 for pop

3 for display

4 for exit

Page | 70
Enter your choice:3

Stack elements are:-

10

1 for push

2 for pop

3 for display

4 for exit

Enter your choice:2

Popped item is:10

1 for push

2 for pop

3 for display

4 for exit

Enter your choice:2

Stack underflow,item cannot be popped

1 for push

2 for pop

3 for display

4 for exit

Enter your choice:3

Stack underflow,item cannot be displayed

1 for push

2 for pop

3 for display

4 for exit

Enter your choice:4

Page | 71
BRIEF DISCUSSION :

This program demonstrates a basic static stack implementation using an array in C++.

Main components of the program are :

 Class Structure :
 Stack class encapsulates the stack data and operations.
 Array A[SIZE] holds the stack elements.
 top indicates the index of the topmost element.

 Operations :
 Push(): Adds an element at the top. It checks for overflow.
 Pop(): Removes the top element and checks for underflow.
 Display(): Prints all elements from top to bottom.

Page | 72
9. Write a program to perform Queue operations using Array .

ALGORITHM :

1. Initialization :

rear = -1

front = -1

This sets the queue as empty initially.

2. Insert Operation :

Step 1: If rear = = SIZE - 1, then

 Queue is full (Overflow) .

else

Step 2: Read the item from the user.

Step 3: Increment rear by 1.

Step 4: A[rear] = item

Step 5: If front == -1 (i.e., first insertion), set front = 0.

3. Delete Operation :

Step 1: If front == -1

 Queue is empty (Underflow).

else

Step 2: Display A[front] as the deleted item.

Step 3: Increment front by 1.

Step 4: If front > rear, set both front and rear back to -1 (queue becomes empty).

4. Display Operation :

Step 1: If front == -1

Page | 73
  Queue is empty, return.

Step 2: Loop from i = front to rear

 Display A[i]

5. Main Function Execution :

Step 1: Create a Queue object.

Step 2: Loop infinitely:

 Show menu options to the user.

 Read the user's choice.
 Call insert, delete, display, or exit depending on the choice.

CODE :
#include<iostream>

#include<stdlib.h>

using namespace std;

#define SIZE 5

class Queue

private: int A[SIZE],rear,front;

public:

Queue()

rear=-1;

front=-1;

void insert()

if(rear==SIZE-1)

Page | 74
 cout<<"\nQueue overflow,item cannot be inserted";

else

int item;

cout<<"\nEnter the item:";

cin>>item;

rear=rear+1;

A[rear]=item;

if(front==-1)

front=front+1;

void Delete()

if(front==-1)

cout<<"\nQueue underflow,item cannot be deleted";

else

cout<<"\nDeleted item is:"<<A[front];

front=front+1;

if(front>rear)

Page | 75
 front=-1;

rear=-1;

void display()

if(front==-1)

cout<<"\nQueue underflow,item cannot be displayed";

else

int i;

cout<<"\nQueue elements are:-";

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

cout<<A[i]<<" ";

};

int main()

Queue q;

int ch;

while(1)

cout<<"\n1 for insert";

Page | 76
 cout<<"\n2 for delete";

cout<<"\n3 for display";

cout<<"\n4 for exit";

cout<<"\nEnter your choice:";

cin>>ch;

switch(ch)

case 1:[Link]();

break;

case 2:[Link]();

break;

case 3:[Link]();

break;

case 4:exit(0);

return 0;

OUTPUT :

1 for insert

2 for delete

3 for display

4 for exit

Enter your choice:1

Enter the item:10

1 for insert

Page | 77
2 for delete

3 for display

4 for exit

Enter your choice:1

Enter the item:20

1 for insert

2 for delete

3 for display

4 for exit

Enter your choice:1

Enter the item:30

1 for insert

2 for delete

3 for display

4 for exit

Enter your choice:3

Queue elements are:-10 20 30

1 for insert

2 for delete

3 for display

4 for exit

Enter your choice:2

Deleted item is:10

1 for insert

2 for delete

3 for display

Page | 78
4 for exit

Enter your choice:2

Deleted item is:20

1 for insert

2 for delete

3 for display

4 for exit

Enter your choice:3

Queue elements are:-30

1 for insert

2 for delete

3 for display

4 for exit

Enter your choice:2

Deleted item is:30

1 for insert

2 for delete

3 for display

4 for exit

Enter your choice:2

Queue underflow,item cannot be deleted

1 for insert

2 for delete

3 for display

4 for exit

Enter your choice:3

Page | 79
Queue underflow,item cannot be displayed

1 for insert

2 for delete

3 for display

4 for exit

Enter your choice:4

BRIEF DISCUSSION :

This program is a menu-driven implementation of a static linear queue using an array .

This program :

 Implements basic queue operations: Insert (Enqueue), Delete (Dequeue), and

Display.
 Uses front and rear pointers to manage the queue.
 Checks for overflow and underflow conditions.
 Menu-driven UI allows the user to perform operations repeatedly.

Page | 80
10. Write a program to perform Circular Queue operations using Array .

ALGORITHM :

Step 1: Initialization :

 Define a class circularq with:

 An integer array A[SIZE] to store elements.
 Two integer variables: front and rear, initialized to -1.

Step 2: Insert Operation :

 If (rear + 1) % SIZE == front, then queue is full (overflow).

 Else:

Input item to insert.

If queue is empty (front == -1 and rear == -1):

Set both front and rear to 0.

 Else:

Set rear = (rear + 1) % SIZE.

Store item in A[rear].

Step 3: Delete Operation

 If front == -1 and rear == -1, the queue is empty (underflow).

 Else:

Retrieve item at A[front].

If front == rear, only one item was in queue:

Reset both front and rear to -1.

 Else:

Set front = (front + 1) % SIZE.

Step 4: Display Operation

 If queue is empty (front == -1 and rear == -1), print underflow.

Page | 81
  Else:

Start from front and loop to rear (circularly).

Print each element in the range using % SIZE for wrapping around.

Step 5: Main Menu

Repeatedly display a menu with 4 options:

1. Insert

2. Delete

3. Display

4. Exit

CODE :
#include<iostream>

#include<stdlib.h>

using namespace std;

#define SIZE 5

class circularq

private: int A[SIZE],rear,front;

public:

circularq()

rear=-1;

front=-1;

void insert()

if((rear+1)%SIZE==front)

Page | 82
 {

cout<<"\nCircular queue overflow,item cannot be

inserted";

else

int item;

cout<<"\nEnter value:";

cin>>item;

if((rear==-1)&&(front==-1))

rear=0;

front=0;

else

rear=(rear+1)%SIZE;

A[rear]=item;

void Delete()

if((rear==-1)&&(front==-1))

cout<<"\nCircular queue underflow,item cannot be

deleted";

Page | 83
 else

int del;

del=A[front];

cout<<"\nDeleted:"<<del;

if(rear==front)

rear=-1;

front=-1;

else

front=(front+1)%SIZE;

void display()

if((rear==-1)&&(front==-1))

cout<<"\nCircular queue underflow,item cannot be

displayed";

else

int i;

i=front;

cout<<"\nCircular queue elements are:-";

Page | 84
 while(1)

cout<<"["<<A[i]<<"]"<<" ";

if(i==rear)

break;

i=(i+1)%SIZE;

};

int main()

circularq cq;

int ch;

while(1)

cout<<"\n1 for insert";

cout<<"\n2 for delete";

cout<<"\n3 for display";

cout<<"\n4 for exit";

cout<<"\nEnter your choice:";

cin>>ch;

switch(ch)

case 1:[Link]();

break;

Page | 85
 case 2:[Link]();

break;

case 3:[Link]();

break;

case 4:exit(0);

return 0;

OUTPUT :

1 for insert

2 for delete

3 for display

4 for exit

Enter your choice:1

Enter value:10

1 for insert

2 for delete

3 for display

4 for exit

Enter your choice:1

Enter value:20

1 for insert

2 for delete

3 for display

4 for exit

Enter your choice:1

Page | 86
Enter value:30

1 for insert

2 for delete

3 for display

4 for exit

Enter your choice:1

Enter value:40

1 for insert

2 for delete

3 for display

4 for exit

Enter your choice:1

Enter value:50

1 for insert

2 for delete

3 for display

4 for exit

Enter your choice:3

Circular queue elements are:-[10] [20] [30] [40] [50]

1 for insert

2 for delete

3 for display

4 for exit

Enter your choice:2

Deleted:10

1 for insert

Page | 87
2 for delete

3 for display

4 for exit

Enter your choice:1

Enter value:60

1 for insert

2 for delete

3 for display

4 for exit

Enter your choice:3

Circular queue elements are:-[20] [30] [40] [50] [60]

1 for insert

2 for delete

3 for display

4 for exit

Enter your choice:4

BRIEF DISCUSSION :

This program shows the implementation of circular queue using Array.

A circular queue prevents unused space that occurs in a linear queue after multiple
insertions and deletions.

% SIZE is used to wrap around the array indices when the end is reached.

front and rear are managed carefully to distinguish between empty and full states.

Page | 88
11. Write a program to perform Stack operations using Linked List .
ALGORITHM :
1. Initialize Stack:
 Create a class stack with a private member top, initialized to NULL
in the constructor.
2. Push Operation:
 Create a new node.
 Input data from the user.
 Set new node’s data to the input and its next pointer to current top.
 Update top to point to the new node.
3. Pop Operation:
 If top is NULL, display "Stack is empty".
 Else:
Store top in a temporary pointer.
Print the data of top.
Update top to the next node.
Delete the temporary node.
4. Display Operation:
 If top is NULL, display "Stack is empty".
 Else:
Traverse the linked list from top to NULL, printing each node's
data.
5. Menu-driven Main Function:
 Repeatedly display menu options: push, pop, display, and exit.
 Perform operation based on user’s choice using switch.

CODE :
#include<iostream>

#include<stdlib.h>

using namespace std;

Page | 89
class Node

public:

int data;

Node *next;

};

class stack

Node *top;

public:

stack()

top=NULL;

void push()

Node *temp;

int v;

temp=new Node();

cout<<"\nEnter data:";

cin>>v;

temp->data=v;

temp->next=top;

top=temp;

void pop()

if(top==NULL)

cout<<"\nStack is empty";

else

Node *p=top;

Page | 90
 cout<<top->data<<" is deleted";

top=top->next;

delete p;

void display()

if(top==NULL)

cout<<"\nStack is empty";

else

Node *i=top;

while(i!=0)

cout<<"\n["<<i->data<<"]";

i=i->next;

};

int main()

stack s;

int ch;

while(1)

cout<<"\n1 for push";

cout<<"\n2 for pop";

cout<<"\n3 for display";

cout<<"\n4 for exit";

cout<<"\nEnter your choice:";

cin>>ch;

Page | 91
 switch(ch)

case 1:[Link]();

break;

case 2:[Link]();

break;

case 3:[Link]();

break;

case 4:exit(0);

return 0;

OUTPUT :
1 for push

2 for pop

3 for display

4 for exit

Enter your choice:1

Enter data:10

1 for push

2 for pop

3 for display

4 for exit

Enter your choice:1

Enter data:20

1 for push

2 for pop

3 for display

Page | 92
4 for exit

Enter your choice:1

Enter data:30

1 for push

2 for pop

3 for display

4 for exit

Enter your choice:3

[30]

[20]

[10]

1 for push

2 for pop

3 for display

4 for exit

Enter your choice:2

30 is deleted

1 for push

2 for pop

3 for display

4 for exit

Enter your choice:3

[20]

[10]

1 for push

2 for pop

Page | 93
3 for display

4 for exit

Enter your choice:2

20 is deleted

1 for push

2 for pop

3 for display

4 for exit

Enter your choice:2

10 is deleted

1 for push

2 for pop

3 for display

4 for exit

Enter your choice:2

Stack is empty

1 for push

2 for pop

3 for display

4 for exit

Enter your choice:3

Stack is empty

1 for push

2 for pop

3 for display

4 for exit

Page | 94
Enter your choice:4

BRIEF DISCUSSION :

This program demonstrates a linked list-based stack implementation using classes in

C++.

It uses a Node structure (as a class) to hold integer data and a pointer to the next node.

The stack class encapsulates stack operations: push(), pop(), and display().

Page | 95
12. Write a program to perform Queue operations using Linked List.

ALGORITHM :

1. Insert Operation

 Create a new node.

 Read data from the user and store it in the node.
 Set node’s next pointer to NULL.
 If rear is NULL:

front = rear = new node (Queue is empty)

 Else:

rear->next = new node

rear = new node

2. Delete Operation

 Check if front is NULL:

If yes, print "Queue underflow"

 Else:

Store front node in a temp pointer

Move front to front->next

If front becomes NULL after deletion, set rear = NULL

Print deleted data

Delete the temp node

3. Display Operation

 Check if front is NULL:

If yes, print "Queue underflow

 Else:

Initialize temp = front

Page | 96
 While temp is not NULL:

Print temp->data

Move to next node (temp = temp->next)

4. Main Menu Loop

 Loop infinitely
 Display menu
 Read user’s choice
 Use switch-case to call corresponding function:

Case 1: Insert

Case 2: Delete

Case 3: Display

Case 4: Exit program

CODE :
#include<iostream>

#include<stdlib.h>

using namespace std;

class Node

public:

int data;

Node *next;

};

class Queue

Node *front;

Node *rear;

public:

Page | 97
Queue()

front=NULL;

rear=NULL;

void insert()

int v;

Node *temp=new Node();

cout<<"\nEnter data:";

cin>>v;

temp->data=v;

temp->next=NULL;

if(rear==NULL)

front=rear=temp;

else

rear->next=temp;

rear=temp;

void Delete()

if(front==NULL)

cout<<"\nQueue underflow,data cannot be deleted";

Page | 98
 }

else

Node *temp;

temp=front;

front=front->next;

if(front==NULL)

rear=NULL;

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

delete temp;

void display()

if(front==NULL)

cout<<"\nQueue underflow,data cannot be displayed";

else

Node *temp=front;

cout<<"\nQueue:-";

while(temp!=NULL)

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

temp=temp->next;

Page | 99
 }

};

int main()

Queue q;

int ch;

while(1)

cout<<"\n1 for insert";

cout<<"\n2 for delete";

cout<<"\n3 for display";

cout<<"\n4 for exit";

cout<<"\nEnter your choice:";

cin>>ch;

switch(ch)

case 1:[Link]();

break;

case 2:[Link]();

break;

case 3:[Link]();

break;

case 4:exit(0);

return 0;

Page | 100
}

OUTPUT:

1 for insert

2 for delete

3 for display

4 for exit

Enter your choice:1

Enter data:10

1 for insert

2 for delete

3 for display

4 for exit

Enter your choice:1

Enter data:20

1 for insert

2 for delete

3 for display

4 for exit

Enter your choice:1

Enter data:30

1 for insert

2 for delete

3 for display

4 for exit

Enter your choice:3

Queue:-10 20 30

Page | 101
1 for insert

2 for delete

3 for display

4 for exit

Enter your choice:2

10 is deleted

1 for insert

2 for delete

3 for display

4 for exit

Enter your choice:2

20 is deleted

1 for insert

2 for delete

3 for display

4 for exit

Enter your choice:3

Queue:-30

1 for insert

2 for delete

3 for display

4 for exit

Enter your choice:2

30 is deleted

1 for insert

2 for delete

Page | 102
3 for display

4 for exit

Enter your choice:2

Queue underflow,data cannot be deleted

1 for insert

2 for delete

3 for display

4 for exit

Enter your choice:3

Queue underflow,data cannot be displayed

1 for insert

2 for delete

3 for display

4 for exit

Enter your choice:4

BRIEF DISCUSSION :

This program demonstrates a basic Queue implementation using a singly linked list in
C++. The advantage of using linked lists is dynamic memory allocation, which allows
the queue to grow or shrink in size during runtime without wasting memory.

Page | 103
13. Write a program to perform Double ended queue operations using
Array.

ALGORITHM :
1. Initialization :
 Set front = -1 and rear = -1.
2. Insert at Rear
 Function: insertrear()
Check if rear == SIZE - 1:
Overflow, cannot insert.
If both front and rear == -1:
Set both to 0.
Else:
Increment rear and insert the item.
3. Delete from Rear
 Function: deleterear()
If both front and rear == -1:
Underflow, nothing to delete.
Save the item at rear.
If front == rear:
Reset both to -1 (deque becomes empty).
Else:
Decrement rear.
4. Insert at Front
 Function: insertfront()
If front == 0:
Overflow, no space at front.
If both front and rear == -1:
Set both to 0.
Else:

Page | 104
 Decrement front and insert the item.
5. Delete from Front
 Function: deletefront()
If both front and rear == -1:
Underflow, nothing to delete.
Save the item at front.
If front == rear:
Reset both to -1 (deque becomes empty).
Else:
Increment front.
6. Display
 Function: display()
If deque is empty (front == -1 and rear == -1):
Print underflow.
Else:
Loop from front to rear and print all elements.
7. Main Menu Loop
 Function: main()
Show menu with options to perform all deque operations.
Use a loop to allow repeated user interaction until exit is
chosen.

CODE :
#include<iostream>

#include<stdlib.h>

using namespace std;

#define SIZE 5

class Deque

private: int A[SIZE],rear,front;

Page | 105
public:

Deque()

rear=-1;

front=-1;

void insertrear()

if((rear==(SIZE-1)))

cout<<"\nDeque overflow,item cannot be inserted

from rear";

else

int item;

cout<<"\nEnter data:";

cin>>item;

if((rear==-1)&&(front==-1))

rear=0;

front=0;

else

rear=rear+1;

A[rear]=item;

Page | 106
 }

void deleterear()

if((rear==-1)&&(front==-1))

cout<<"\nDeque underflow,item cannot be deleted

from rear";

else

int del;

del=A[rear];

if(rear==front)

rear=-1;

front=-1;

else

rear=rear-1;

cout<<"\n"<<del<<" is deleted from rear";

void insertfront()

if(front==0)

Page | 107
 {

cout<<"\nDeque overflow,item cannot be inserted

from front";

else

int item;

cout<<"\nEnter value:";

cin>>item;

if((rear==-1)&&(front==-1))

rear=0;

front=0;

else

front=front-1;

A[front]=item;

void deletefront()

if((rear==-1)&&(front==-1))

cout<<"\nDeque underflow,item cannot be deleted

from front";

Page | 108
 else

int del;

del=A[front];

if(rear==front)

rear=-1;

front=-1;

else

front=front+1;

cout<<"\n"<<del<<" is deleted from front";

void display()

if((rear==-1)&&(front==-1))

cout<<"\nDeque underflow,item cannot be displayed";

else

int i;

cout<<"\nDeque elements are:-";

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

Page | 109
 cout<<"["<<A[i]<<"]"<<" ";

};

int main()

Deque dq;

int ch;

while(1)

cout<<"\n1 for insert from rear";

cout<<"\n2 for delete from rear";

cout<<"\n3 for insert from front";

cout<<"\n4 for delete from front";

cout<<"\n5 for display";

cout<<"\n6 for exit";

cout<<"\nEnter your choice:";

cin>>ch;

switch(ch)

case 1:[Link]();

break;

case 2:[Link]();

break;

case 3:[Link]();

break;

case 4:[Link]();

Page | 110
 break;

case 5:[Link]();

break;

case 6:exit(0);

return 0;

OUTPUT :

1 for insert from rear

2 for delete from rear

3 for insert from front

4 for delete from front

5 for display

6 for exit

Enter your choice:1

Enter data:10

1 for insert from rear

2 for delete from rear

3 for insert from front

4 for delete from front

5 for display

6 for exit

Enter your choice:1

Enter data:20

1 for insert from rear

Page | 111
2 for delete from rear

3 for insert from front

4 for delete from front

5 for display

6 for exit

Enter your choice:5

Deque elements are:-[10] [20]

1 for insert from rear

2 for delete from rear

3 for insert from front

4 for delete from front

5 for display

6 for exit

Enter your choice:4

10 is deleted from front

1 for insert from rear

2 for delete from rear

3 for insert from front

4 for delete from front

5 for display

6 for exit

Enter your choice:3

Enter value:30

1 for insert from rear

2 for delete from rear

3 for insert from front

Page | 112
4 for delete from front

5 for display

6 for exit

Enter your choice:5

Deque elements are:-[30] [20]

1 for insert from rear

2 for delete from rear

3 for insert from front

4 for delete from front

5 for display

6 for exit

Enter your choice:2

20 is deleted from rear

1 for insert from rear

2 for delete from rear

3 for insert from front

4 for delete from front

5 for display

6 for exit

Enter your choice:5

Deque elements are:-[30]

1 for insert from rear

2 for delete from rear

3 for insert from front

4 for delete from front

5 for display

Page | 113
6 for exit

Enter your choice:6

BRIEF DISCUSSION :

This C++ program demonstrates a basic double-ended queue (Deque) using an array of
fixed size (SIZE = 5). It allows:

 Insertion and deletion from both front and rear ends

 Display of all current elements

Page | 114