SRTCT’S

SUMAN RAMESH TULSIANI TECHNICAL CAMPUS – FACULTY OF

ENGINEERING,
KHAMSHET
An ISO 9001:2015 Certified Institute
NAAC Accredited Institute

DEPARTMENT OF ARTIFICIAL INTELLIGENCE

&
DATA SCIENCE ENGINEERING

Academic Year:2024-25
Semesters -I

Class: SE

Subject: Data Structures

Laboratory
Subject In charge:

Prof. Anushka Joshi

Data Structures Laboratory

SRTTC FOE
 SRTCT’S
SUMAN RAMESH TULSIANI TECHNICAL CAMPUS –FACULTY OF ENGINEERING,
KHAMSHET
An ISO 9001:2015 Certified Institute
NAAC Accredited Institute
DEPARTMENT OF ARTIFICIAL INTELLIGENCE & DATA SCIENCE

INDEX
Department of AI-DS Engineering Class: S.E.
Sr. Date of Date of Page
Name of the Sign
No Experiment Conducti Checking No.
. on
Group-A
A-1
In second year computer engineering
1 class, group A student’s play cricket, group
B
students play badminton and group C
students play football.
Write a Python program using functions to
compute following: -
a) List of students who play both cricket
and badminton
b) List of students who play either cricket or
badminton but not both
c) Number of students who play neither
cricket nor badminton
d) Number of students who play cricket and
football but not badminton.

A-2
Write a Python program to store marks
2
scored in subject “Fundamental ofData
Structure” by N students in the class.
Write functions to compute following:
a) The average score of class
b) Highest score and lowest score of class
c) Count of students who were absent
for the test
Display mark with highest frequency

Data Structures Laboratory

SRTTC FOE
 A-9
Write a python program to compute
following computation on matrix:
3
a) Addition of two matrices
b) Subtraction of two matrices
c) Multiplication of two matrices
d) Transpose of a matrix

Data Structures Laboratory

SRTTC FOE
 Group - B
B-13
Write a python program to maintain club
members, sort on roll numbers in ascending
4
order. Write function “Ternary_Search” to
search whether particular student is
member
of club or not. Ternary search is modified
binary search that divides array into 3
halves
instead of two.

B-14
Write a pythonprogram to store first year
5 percentage of students in array. Write
function
for sorting array of floating point numbers
in ascending order using
a) Selection Sort
b) Bubble sort and display top five scores.

B-16
6 Write a Python program to store first year
percentage of students in array. Write
function for sorting array of floating-point
numbers in ascendingorder using quick sort
and display top five scores.
Group - C
C-19
Department of Computer Engineering has
student's club named 'Pinnacle Club'.
Students of second, third and final year of
department can be granted membership on
7
request. Similarly, one may cancel the
membership of club. First node is reserved
for president of club and last node is
reserved for secretary of club. Write C++
program to maintain club member ‘s
information using singly linked list. Store
student PRN and Name. Write functions to:
a) Add and delete the members as well as
president or even secretary. b) Compute
total number of members of club c) Display
members d) Two linked lists exists for two
divisions. Concatenate two lists.

Data Structures Laboratory

SRTTC FOE
 C-20
The ticket booking system of Cinemax
theater has to be implemented using C++
08 program. There are 10 rows and 7 seats in
each row. Doubly circular linked list has to
be maintained to keep track of free seats at
rows. Assume some random booking to
start with. Use array to store pointers (Head
pointer) to each row. On demand a) The list
of available seats is to be displayed b) The
seats are
to be booked c) The booking can be
cancelled.
Group- D
D-25
A palindrome is a string of character that‘s
the same forward and backward. Typically,
punctuation, capitalization, and spaces are
ignored. For example, “Poor Dan is in a
09
droop”
is a palindrome, as can be seen by
examining the characters “poor danisina
droop” and
observing that they are the same forward
and backward. One way to check for a
palindrome is to reverse the characters in
the string and then compare with them the
original-in a palindrome, the sequence will
be identical. Write C++ program with
functions
a) To print original string followed by
reversed string using stack
b) To check whether given string is
palindrome or not

D-26 In any language program mostly

syntax error occurs due to unbalancing
10 delimiter such as
(),{},[]. Write C++ program using stack to
check whether given expression is well
parenthesized or not.

Data Structures Laboratory

SRTTC FOE
 Group- E
E-29 Queues are frequently used in
computer programming, and a typical
11 example is the creation of a job queue
by an operating system. If the
operating system does not use
priorities, then the jobs are processed
in the order they enter the system.
Write C++ program for simulating job
queue. Write
functions to add job and delete job
from queue.
E-31 A double-ended queue (deque) is
a linear list in which additions and
12 deletions may be made at either end.
Obtain a data representation mapping
a deque into a one- dimensional array.
Write C++ program to
simulate deque with functions to add
and delete elements from either end of
the deque.
E-32 Pizza parlor accepting maximum
M orders. Orders are served in first
13 comefirst served basis. Order once
placed cannot be
cancelled. Write C++ program
tosimulate the system using circular
queue using array.

Data Structures Laboratory

SRTTC FOE
 SRTCT’S
SUMAN RAMESH TULSIANI TECHNICAL CAMPUS FACULTY OF
ENGINEERING,KHAMSHET
An ISO 9001:2015 Certified Institute
NAAC Accredited Institute
DEPARTMENT OF ARTIFICIAL INTELLIGENCE & DATA SCIENCE

Academic Year: 2024-25

CERTIFICATE

This is to certify that Mr. /Miss.

of Class S.E. AI-DS Roll No. has satisfactorily

completed practical of the subject “Data Structures Laboratory” for

Semester-I of Academic Year 2024 – 2025.

Date:

Prof. A.P.Joshi Dr.D.E.Upasani Prof.Dr. J. B. Sankpal

Subject Head Principal
Teacher Of Department

Data Structures Laboratory

SRTTC FOE
Data Structure and Lab (DSL)

DATA STRUCTURES LAB

(210246)

Teaching Cred Examination

Scheme it Scheme
TW: 25 Marks
PR: 04 02
Hours/Week PR: 50 Marks

Guidelines for Instructor's Manual

The instructor„s manual is to be developed as a hands-on resource and reference. The

instructor's manual need to include prologue (about university/program/ institute/
department/foreword/ preface etc), University syllabus, conduction & Assessment guidelines,
topics under consideration- concept, objectives, outcomes, set of typical
applications/practicals/ guidelines, and references.

Guidelines for Student Journal

The laboratory practicals are to be submitted by student in the form of journal. Journal
consists of prologue, Certificate, table of contents, and handwritten write-up of each
practical (Title, Objectives, Problem Statement, Outcomes, software & Hardware
requirements, Date of Completion, Assessment grade/marks and assessor's sign, Theory-
Concept in brief, algorithm, flowchart, test cases, conclusion/analysis. Program codes with
sample output of all perform practical‟s are to be submitted as softcopy.
As a conscious effort and little contribution towards Green IT and environment awareness,
attaching printed papers as part of write-ups and program listing to journal may be avoided.
Use of DVD containing students’ programs maintained by lab In-charge is highly encouraged.
For referenceone or two journals may be maintained with program prints at Laboratory.

Guidelines for Assessment

Continuous assessment of laboratory work is done based on overall performance and lab
practicals performance of student. Each lab practical assessment will assign grade/marks
based on parameters with appropriate weightage. Suggested parameters for overall
assessment as well as each labpractical assessment include- timely completion, performance,
innovation, efficient codes, punctuality and neatness.

Guidelines for Practical Examination

Both internal and external examiners should jointly set problem statements. During practical
assessment, the expert evaluator should give the maximum weightage to the satisfactory
implementation of the problem statement. The supplementary and relevant questions may be
asked at the time of evaluation to test the students for advanced learning, understanding of
the fundamentals, effective and efficient implementation. So,

.
Data Structure and Lab (DSL)

encouraging efforts, transparent evaluation and fair approach of the evaluator will not

appropriate use of Hungarian notation, proper indentation and comments. Use of open source
software is to be encouraged.

In addition to these, instructor may assign one real life application in the form of a mini-
project based on the concepts learned. Instructor may also set one practical or mini-project
that is suitableto respective branch beyond the scope of syllabus.

Set of suggested practical list is provided in groups- A, B, C, D, and E. Each student must
perform at least 13 practicals as at least 3 from group A, 3 from group B, 2 from group C, 2
from group D and 3 from group E.

Group A and B assignments should be implemented in Python without using

built-in methods for major functionality of assignment. Use List data structure of Python as
array. Group C, D and E assignments should be implemented in C++ language.

Operating System recommended: - 64-bit Open-source Linux or its derivative

Programming tools recommended: - Open-Source Python,

Programming tool:- like Jupyter Notebook, Pycharm, Spyder, G

.
 Experiment No-1
AIM:- To perform operations on set

TITLE:- In second year computer engineering class, group A student?s play cricket, Group
B students play badminton and group C students play football. Write a Python program
using functions to compute following: -
a) List of students who play both cricket and badminton
b) List of students who play either cricket or badminton but not both
c) Number of students who play neither cricket nor badminton
d) Number of students who play cricket and football but not badminton.

OBJECTIVES:-
1) To know the basics of set.
2) To perform operation on array.
3) To implement set operation using array

THEORY:-
Set Theory:
No restriction is placed on the nature of the objects in a set. They can be anything: points,
lines, numbers, people, countries, etc. Thus the mathematical meaning of the word set is the
same as the regular, nontechnical meaning of the word.
Examples of sets.
- All points in a given line segment
- Lines through a given point in space
- The set of all rational numbers
- Solutions of the equation 3x2 + 2y2 - 1 = 0
- Citizens of England
- Rivers of Mexico
Union of sets: The union of two sets A and B is the set consisting of all elements in A plus all
elements in B and is denoted by A∪B or A + B

Example: If A = {a, b, c, d} and B = {b, c, e, f, g} then A∪B = {a, b, c, d, e, f, g}. Intersection of

sets: The intersection of two sets A and B is the set consisting of all elements that occur in both A
and B (i.e. all elements common to both) and is denoted by A∩B, A · B or AB.
Example: If A = {a, b, c, d} and B = {b, c, e, f, g} then A∩B = {b, c}.
Difference of two sets: The set consisting of all elements of a set A that do not belong to a set
B is called the difference of A and B and denoted by A - B.

Example: If A = {a, b, c, d} and B = {b, c, e, f, g} then A - B = {a, d}.

Universal set U: Often a discussion involves subsets of some particular set called the
universe of discourse (or briefly universe), universal set or space. The elements of a space are
often called the points of the space. We denote the universal set by U.

Example: The set of all even integers could be considered a subset of a universal set
consisting of all the integers. Or they could be considered a subset of a universal set
consisting of all the rational numbers. Or of all the real numbers.

ALGORITHM:-
1) Start
2) Declare variable and string
3) Accept input from user
4) Define all functions and perform all operations
5) Display the output
6) Stop

CONCLUSION:-
 Experiment No-2
Practical Title: Write a python program to store marks for N students.
Aim: - Write a Python program to store marks scored in subject “Fundamental of Data
Structure” by N students in the class. Write functions to compute following:
a) The average score of class
b) Highest score and lowest score of class
c) Count of students who were absent for the test
d) Display mark with highest frequency

Prerequisite:
• Python Programming

Objectives:
To understand the use functions for N students, record.

Input: N number of students.

Outcome: Resulting average, highest and lowest marks operation.

Theory:
ARRAYS
Arrays a kind of data structure that can store a fixed-size sequential collection of elements of
the same type. An array is used to store a collection of data, but it is often more useful to
think of anarray as a collection of variables of the same type.
Instead of declaring individual variables, such as number0, number1, ..., and number99, you
declare one array variable such as numbers and use numbers [0], numbers [1], and ..., numbers
[99] to represent individual variables. A specific element in an array is accessed by an index.
All arrays consist of contiguous memory locations. The lowest address corresponds to the first
element and the highest address to the last element.

Declaring Arrays
To declare an array in C, a programmer specifies the type of the elements and the number of
elements required by an array as follows −
type arrayName [ arraySize ];

This is called a single-dimensional array. The arraySize must be an integer constant greater than
zero and type can be any valid C data type. For example, to declare a 10-element array called
balance of type double, use this statement −

double balance[10];
Data Structure and Lab SE Computer
(DSL) Engineering

Here balance is a variable array which is sufficient to hold up to 10 double numbers.

Initializing Arrays
You can initialize an array in C either one by one or using a single statement as follows −
double balance[5] = {1000.0, 2.0, 3.4, 7.0, 50.0};

Accessing Array Elements

An element is accessed by indexing the array name. This is done by placing the index of the element
within square brackets after the name of the array. For example −
double salary = balance[9];

Functions Used:
Write algorithm/pseudo code for each function.
a) The average score of class
b) Highest score and lowest score of class
c) Count of students who were absent for the test
d) Display mark with highest frequency

Algorithm:
WRITE ALGO.

Flowchart:
Here, draws flowchart of above algorithm.

Conclusion:
By this way, we can store the marks of N students sucessfully.

Questions:
1. Basics of python Programming.
2. What are functions?
3. What are the features of python Programming?
4. What are array?

.
 Experiment No-3

Practical Title: Perform different operations on Matrix.

Aim : Write a Python program to compute following computation on matrix:
a) Addition of two matrices
b) Subtraction of two matrices
c) Multiplication of two matrices
d) Transpose of a matrix

Pre-requisite:
• Knowledge of representing matrix in Python
• Knowledge of different operations that can be performed on matrix

Objectives:
• Compute the transpose of matrix
• Perform addition , subtraction and multiplication of two matrices.

Input:
Number of rows and columns of two matrices
Elements of both the matrices

Outcome:

• Transpose of a matrix

• Result of addition , subtraction and multiplication of both matrices.

Theory:
• Number of rows and columns of two matrices
• Elements of both the matrices
• Transpose of a matrix
• Result of addition , subtraction and multiplication of both matrices.

 2-dimension array –

write theory of 2-D array

 MatrixOperations (explain each operation in detail with example)
- Concept of matrix
- Addition
- Substraction
- Multiplication
- Transpose of matrix
 Algorithm:

1. Start
2. Input number of rows and columns of first matrix.
3. Input elements of first matrix.
4. Input number of rows and columns of second matrix.
5. Input elements of Second matrix.
6. Function to transpose first matrix i.e. the element at row r column c in the original is
placed at row c column r of the transpose.
7. Fuction to add, subtract and multiply two matrices.

Flowchart :
Draw flowchart for above algorithm

Conclusion:
By this way, we can perform various operations on matrix successfully.

Questions:
1.What is upper triangular matrix and lower triangular matrix?
2. How to find transpose of a matrix.
3. Different operations on matrix.
Data Structure and Lab (DSL) SE Computer Engineering

Practical
No:04(B)

Practical Title:. Write function Ternary_Search to search whether particular

student is member
of club or not.

Aim: Write a python program to maintain club members, sort on roll numbers in
ascending
order. Write function “Ternary_Search” to search whether particular student is
member
of club or not. Ternary search is modified binary search that divides array into 3
halves
instead of two.

Pre-requisite:

Knowledge of Searching Techniques

Objective:
To Search array of floating point numbers in ascending order using
A)Ternary Search

Input:
Size of array Elements of array

Theory :
- Write short theory of Seraching Techniques &it’s Type with its
advantages and disadvantages.
- Explain Ternary Search with example

Algorithm:
Steps to perform Ternary Search:
1. First, we compare the key with the element at mid1. If found equal, we
return mid1.
2. If not, then we compare the key with the element at mid2. If found equal, we
return mid2.
3. If not, then we check whether the key is less than the element at mid1. If yes,
then recur to the first part.
4. If not, then we check whether the key is greater than the element at mid2. If
yes, then recur to the third part.
5. If not, then we recur to the second (middle) part.
Data Structure and Lab (DSL) SE Computer Engineering

Flowchart :

Draw flowchart for above algorithms.

Conclusion:
By this way, we can perform searching of an array using Ternary Search technique.

Oral Question Bank:

1. Explain the Searching?

2. What are the different types of
searching techniques in data structures
3.Define the Ternary Search?
4. Define the Binary Search?
5. How many passes are required in Ternary Search?
6. What is the time complexity of Ternary Search
Data Structure and Lab (DSL) SE Computer Engineering

Practical No:05(B)
Practical Title: Sorting of an array using selection and bubble sort.
Aim: Write a Python program to store first year percentage of students in array. Write function for
sorting array of floating point numbers in ascending order using
a) Selection Sort

b) Bubble sort and display top five scores.of club.

Pre-requisite:

Knowledge of sorting techniques

Objective:
To sort array of floating point numbers in ascending order using
a) Selection Sort b) Bubble sort and display top five scores.

Input:
Size of array Elements of array

Theory :
- Write short theory of sorting with its advantages and disadvantages.
- Explain selection and bubble sort with example

Algorithm:
def bubbleSort(alist):
for passnum in range(len(alist)-1,0,-1):
for i in range(passnum):
if alist[i]>alist[i+1]:
temp = alist[i]
alist[i] = alist[i+1]
alist[i+1] = temp

alist = [54,26,93,17,77,31,44,55,20]
bubbleSort(alist)
print(alist)

def selectionSort(alist):
for fillslot in range(len(alist)-1,0,-1):
positionOfMax=0
for location in range(1,fillslot+1):
Data Structure and Lab (DSL) SE Computer Engineering

if alist[location]>alist[positionOfMax]:
positionOfMax = location

temp = alist[fillslot]
alist[fillslot] = alist[positionOfMax]
alist[positionOfMax] = temp

alist = [54,26,93,17,77,31,44,55,20]
selectionSort(alist)
print(alist)

Flowchart :

Draw flowchart for above algorithms.

Conclusion:
By this way, we can perform sorting of an array using selection and bubble sort.

Oral Question Bank:

1. Explain the sorting?

2. What are the different types of sorts in data structures
3.Define the bubble sort?
4. Define the selection sort?
5. How many passes are required in selection sort?
6. What is the time complexity of selecion and bubble sort?
Data Structure and Lab (DSL) SE Computer Engineering
GROUP - B
Data Structure and Lab (DSL)

Practical
No:05(B)
Practical Title: Sorting of an array using selection and bubble sort.
Aim: Write a Python program to store first year percentage of students in array. Write
function for sorting array of floating point numbers in ascending orderusing
a) Selection Sort
b)Bubble sort and display top five scores.of club.

Pre-requisite:

Knowledge of sorting techniques

Objective:
To sort array of floating point numbers in ascending order using
a) Selection Sort b) Bubble sort and display top five scores.

Input:
Size of array Elements of array

Theory :
- Write short theory of sorting with its advantages and disadvantages.
- Explain selection and bubble sort with example

Algorithm:
def bubbleSort(alist):
for passnum in range(len(alist)-1,0,-
1): for i in range(passnum):
if alist[i]>alist[i+1]:
temp = alist[i]
alist[i] = alist[i+1]
alist[i+1] = temp
Data Structure and Lab (DSL)

alist = [54,26,93,17,77,31,44,55,20]
bubbleSort(alist)
print(alist)

def selectionSort(alist):
for fillslot in range(len(alist)-1,0,-1):
positionOfMax=0
for location in range(1,fillslot+1)

if alist[location]>alist[positionOfMax]: positionOfMax = location

temp = alist[fillslot]
alist[fillslot] = alist[positionOfMax]
alist[positionOfMax] = temp

alist = [54,26,93,17,77,31,44,55,20]
selectionSort(alist) print(alist)
Data Structure and Lab (DSL)
SE Computer Engineering

Flowchart :

Draw flowchart for above algorithms.

Conclusion:
By this way, we can perform sorting of an array using selection and bubble sort.

Question Bank:

1. Explain the sorting?

2. What are the different types of sorts in data
structures 3.Define the bubble sort?
4. Define the selection sort?
5. How many passes are required in selection sort?
6. What is the time complexity of selecion and bubble sort?
Data Structure and Lab (DSL)
SE Computer Engineering

Practical
No:06(B)
Practical Title: Sorting array of floating point numbers in ascending order using quick
sort.

Aim: Write a Python program to store first year percentage of students in array. Write
function for sorting array of floating point numbers in ascending order using quick sort and
display top five scores.

Pre-requisite:

• Knowledge of sorting techniques

Objective:
• To sort array using quick sort

Input:
Size of array
First year percentage of students.

Outcome:
• To sort array using quick sort
• To display top five scores.

Theory :
- Explain concept of Quick sort in details.
- Advantages and disadvantages
- Example of quick sort.
- Time complexity.
Data Structure and Lab (DSL)
SE Computer Engineering

Algorithm:

def quickSort(alist):
quickSortHelper(alist,0,len(alist)-1)
def quickSortHelper(alist,first,last):
if first<last:
splitpoint = partition(alist,first,last)
quickSortHelper(alist,first,splitpoint-1)
quickSortHelper(alist,splitpoint+1,las
t)
def partition(alist,first,last):
pivotvalue = alist[first]
leftmark = first+1
rightmark = last
done = False
while not done:

while leftmark <= rightmark and alist[leftmark] <= pivotvalue

leftmark = leftmark + 1
while alist[rightmark] >= pivotvalue and rightmark >=
leftmark: rightmark = rightmark -1

if rightmark < leftmark:

done = True
else:
temp = alist[leftmark]
alist[leftmark] = alist[rightmark]
alist[rightmark] = temp
temp = alist[first]
alist[first] = alist[rightmark]
alist[rightmark] = temp
return rightmark
alist = [54,26,93,17,77,31,44,55,20]
quickSort(alist)
print(alist)
Data Structure and Lab (DSL)
SE Computer Engineering

Flowchart :

Draw flowchart for above algorithms.

Conclusion:
By this way, we can perform sorting array of floating point numbers in ascending order
using quick sort

Question Bank:
1. Explain the sorting?
2. What are the different types of sorts in data structures?
3. Define the quick sort?
5. How many passes are required in
quick sort? 6.What is the time complexity of
quick sort
GROUP - C
Data Structure and Lab (DSL)

Practical No : 07 (C)
Assignmet Title: Write C++ program to maintain club member‘s information using
singly linked list.
Aim: Department of Computer Engineering has student's 1/8 club named 'Pinnacle Club'.
Students of Second, third and final year of department can be granted membership on
request. Similarly one may cancel the membership of club. First node is reserved for
president of club and last node is reserved for secretary of club. Write C++ program to
maintain club member‘s information using singly linked list. Store student PRN and Name.
Write functions to
a) Add and delete the members as well as president or even secretary.
b) Compute total number of members of club
c) Display members
d) Display list in reverse order using recursion
e) Two linked lists exists for two divisions. Concatenate two lists

Input: Individual details

Output: Maintain information of the Club member's
Objectives:
To maintain club member's information by performing different operations
like add, delete, reverse, concatenate on singly linked list.

Theory:
Linked List : (write linked list definition and sinly linked list theory)
- Definition :
- Types of linked list
- Singly linked list (definition, concepts, advantages, disadvantages)
- Singly linked list as an ADT (Write pseudo code for each ADT)

- Algorithm

(Write your own algorithm for your program)

- Flowchart :
(draw your own flowchart for your algorithms)

Conclusion:
By this way, we can maintain club member‘s information using singly linked list.

.
Data Structure and Lab (DSL)

Questions: (No need to write answers)

1. What is a Linked list?

2. Can you represent a Linked list graphically?
3. How many pointers are required to implement a simple Linked list?
4. How many types of Linked lists are there?
5. How to represent a linked list node?
6. Describe the steps to insert data at the starting of a singly linked list.
7. How to insert a node at the end of Linked list?
8. How to delete a node from linked list?
9. How to reverse a singly linked list?
10. What is the difference between singly and doubly linked lists?
11.What are the applications that use Linked lists?

12. What will you prefer to use a singly or a doubly linked lists for traversing through
a list of elements?

.
Data Structure and Lab (DSL)

Practical No: 08 (C)

Practical Title: The ticket booking system of Cinemax theater has to be implemented using
C++ program. There are 10 rows and 7 seats in each row. Doubly circular linked
list has to be maintained to keep track of free seats at rows. Assume some
random booking to start with. Use array to store pointers (Head pointer) to each
row. On demand
a) The list of available seats is to be displayed
b) The seats are to be booked
c) The booking can be cancelled.

Pre-requisite:

• Knowledge of Doubly Circular Linked List

• Representation of Circular Linked list
• Knowledge of ticket booking

Objective:

• To perform Doubly Circular linked list for cinemax ticket booking.

• To display available seats.
• To book and cancel seats

Input:
Row no and seat no to book seat
Outcome:
• Diplay available seats to book movie ticket.
• Display status of Booked seat/ cancel seat.

.
Data Structure and Lab (DSL)

Theory :

Circular Doubly linked list : (write CDLL theory in details i.e. definition,
concepts, advantages, disadvantages.)

- Doubly Circular linked list as an ADT : (write pseudo code for each
operation)

- Algorithms :

(Write your own algorithms for your program)

- Flowchart :

(draw flowchart for above algorithms)

Conclusion:
By this way, we can book or cancel movie ticket using doubly Circular linked lists.

Questions: (No need to write answers)

1. What is Doubly Circular Linked List?

2. How to represent doubly circular linked list?
3. How to book or cancel seat?
3. What is doubly linked list?
4. How to insert and delete elements from doubly circulars linked list?

.
GROUP - D
Data Structure and Lab (DSL)

Practical No:09(D)

Practical Title: A palindrome string

Aim:A palindrome is a string of character that‘s the same forward and backward. Typically,
punctuation, capitalization, and spaces are ignored. For example, “Poor Dan is in a droop”
is a palindrome, as can be seen by examining the characters “poor danisina droop” and
observing that they are the same forward and backward. One way to check for a
palindrome is to reverse the characters in the string and then compare with them the
original-in a palindrome, the sequence will be identical. Write C++ program with
functions
a) To print original string followed by reversed string using stack
b) To check whether given string is palindrome or not

Pre-requisite:

• Basics of palindrome String

• Different operations that can be performed on Palindrome string

Objective:
a) To print original string followed by reversed string using stack
b) To check whether given string is palindrome or not

Input:
“Poor Dan is in a droop”
is a palindrome, as can be seen by examining the characters
“poor danisina droop” and observing that they are the same forward and backward.

Outcome:
To check whether given string is palindrome or not

.
Data Structure and Lab (DSL)

Theory :
- Write short theory of Palindrome string
-How do you solve a palindrome string problem?
-How do you find the palindrome of a string?
-How do you identify a palindrome?

Algorithms :
Write your own algorithms

Flowchart :
Draw flowchart for above algorithms.

Conclusion:
By this way, we can check To check whether given string is palindrome or not

.
Data Structure and Lab (DSL)

Practical No:10(D)

Practical Title: Write C++ program to check well form of parenthesis using stack.
Aim: In any language program mostly syntax error occurs due to unbalancing delimiter
such as (),
{},[]. Write C++ program using stack to check whether given expression is well
parenthesized or not.
Pre-requisite:

• Basics of stack.
• Different operations that can be performed on stack

Objective:
• To check whether the given expression is well parenthesized or not.

Input:
Expression using {},(),[].

Outcome:
• Result of checking well formedness of parenthesis.

Theory :
- Write short theory of stack.
- Write concept of well form parenthesis.
- Example of well form parenthesis.

Algorithms :
Write your own algorithms

Flowchart :
Draw flowchart for above algorithms.

Conclusion:
By this way, we can check well form of parenthesis using stack.

Question Bank:
1. What is Stack?
2. Which are the different operations that can be performed on stack?
3. Explain PUSH, POP operations on stack
4. What are the applications of stack?

.
GROUP - E
 Practical No:11 (E)

Practical Title: Perform different operations on Queue.

Aim: Queues are frequently used in computer programming, and a typical example is the
creation of a job queue by an operating system. If the operating system does not use
priorities, then the jobs are processed in the order they enter the system. Write C++
program for simulating job queue.Write functions to add job and delete job from queue.

Pre-requisite:

• Basics of Queue
• Different operations that can be performed on queue

Objective:
• To perform addition and deletion operations on queue.

Input:
Size of queue
Elements in quque

Outcome:
• Result of addition of job operation on queue.
• Result of deletion of job operation on queue.

Theory :

- Write theory of queue (definition, concepts, types, advantages,

disadvantages)
- Explain queue as an ADT. (writepseudo code)
 - Algorithms :

Step 1: Include all the header files which are used in the program and define a constant
'SIZE' with specific value.
Step 2: Declare all the user defined functions which are used in queue implementation.
Step 3: Create a one dimensional array with above defined SIZE (int queue[SIZE])
Step 4: Define two integer variables 'front' and 'rear' and initialize both with '-1'. (int front = -
1, rear
= -1)
Step 5: Then implement main method by displaying menu of operations list and make
suitable function calls to perform operation selected by the user on queue.

enQueue(value) - Inserting value into the queue:

In a queue data structure, enQueue() is a function used to insert a new element into
the queue. In a queue, the new element is always inserted at rear position. The enQueue()
function takes one integer value as parameter and inserts that value into the queue. We
can use the following steps to insert an element into the queue...

Step 1: Check whether queue is FULL. (rear == SIZE-1)

Step 2: If it is FULL, then display "Queue is FULL!!! Insertion is not possible!!!" and terminate
the function.
Step 3: If it is NOT FULL, then increment rear value by one (rear++) and set queue[rear] =
value.

deQueue() - Deleting a value from the Queue:

In a queue data structure, deQueue() is a function used to delete an element from
the queue. In a queue, the element is always deleted from front position. The deQueue()
function does not take any value as parameter. We can use the following steps to delete an
element from the queue...

Step 1: Check whether queue is EMPTY. (front == rear)

Step 2: If it is EMPTY, then display "Queue is EMPTY!!! Deletion is not possible!!!" and
terminate the function.
Step 3: If it is NOT EMPTY, then increment the front value by one (front ++). Then display
queue[front] as deleted element. Then check whether both front and rear are equal (front
== rear), ifit TRUE, then set both front and rear to '-1' (front = rear = -1).

display() - Displays the elements of a Queue:

We can use the following steps to display the elements of a queue...

Step 1: Check whether queue is EMPTY. (front == rear)

Step 2: If it is EMPTY, then display "Queue is EMPTY!!!" and terminate the function.
Step 3: If it is NOT EMPTY, then define an integer variable 'i' and set 'i = front+1'.
 Step 4: Display 'queue[i]' value and increment 'i' value by one (i++). Repeat the same
until 'i' value is equal to rear (i <= rear)

Flowchart:
Draw flowchart for above algorithms

Conclusion:
By this way, we can perform different operations on queue

Question Bank:
1. What is Queue?
2. What are the different operations that can be performed on queue?
3. Explain all the operations on queue
4. Which are different types of queues , Explain.
 Practical No:12(E)
Practical Title: Perform operations on Double ended queue.
Aim: A double-ended queue(deque) is a linear list in which additions and deletions may be
made at either end. Obtain a data representation mapping a deque into a one-dimensional
array. Write C++ program to simulate deque with functions to add and delete elements
from either end of the deque.

Pre-requisite:

• Knowledge of Queue
• Types of queue
• Knowledge of double ended queue and different operations that can be performed on it

Objective:
• To simulate deque with functions to add and delete elements from either end of the
deque.

Input:
Size of array Elements
in the queue
Outcome:
• Result of deque with functions to add and delete elements from either end of the
deque.

Theory :

Double-Ended Queue

A double-ended queue is an abstract data type similar to an simple queue, it allows you to
insert and delete from both sides means items can be added or deleted from the front or
rear end.

Algorithm for Insertion at rear end

Step -1: [Check for overflow]

if(rear==MAX) Print("Queue
is Overflow”); return;
Step-2: [Insert element]
else
rear=rear+1;
 q[rear]=no;
[Set rear and front pointer]

if rear=0
rear=1; if
front=0
front=1;
Step-3: return

Implementation of Insertion at rear end

void add_item_rear()
{
int num;
printf("\n Enter Item to insert : ");
scanf("%d",&num);
if(rear==MAX)
{
printf("\n Queue is Overflow");
return;
}
else
{
rear++;
q[rear]=num;
if(rear==0)
rear=1;
if(front==0)
front=1;
}
}

Algorithm for Insertion at font end

Step-1: [Check for the front position]

if(front<=1)
Print (“Cannot add item at front
end”); return;
Step-2: [Insert at front]
else
front=front-1;
q[front]=no;
Step-3: Return

Implementation of Insertion at font end

void add_item_front()
{
int num;
printf("\n Enter item to insert:");
scanf("%d",&num);
 if(front<=1)

{
printf("\n Cannot add item at front end");
return;
}
else
{
front--;
q[front]=num;
}
}

Algorithm for Deletion from front end

Step-1 [ Check for front pointer]
if front=0
print(" Queue is Underflow”);
return;
Step-2 [Perform deletion]
else
no=q[front];
print(“Deleted element is”,no);
[Set front and rear pointer]
if front=rear
front=0;
rear=0;
else
front=front+1;
Step-3 : Return

Implementation of Deletion from front end

void delete_item_front()
{
int num;
if(front==0)
{
printf("\n Queue is Underflow\n");
return;
}
else
{
num=q[front];
printf("\n Deleted item is %d\n",num);
if(front==rear)
{
front=0;
rear=0;
}
else
{
front++;
 }

}
}

Algorithm for Deletion from

rear end Step-1 : [Check for the
rear pointer] if rear=0
print(“Cannot delete value at rear
end”); return;
Step-2: [ perform deletion]
else
no=q[rear];
[Check for the front and rear
pointer] if front= rear
front=0;
rear=0;
else
rear=rear-1;
print(“Deleted element is”,no);
Step-3 : Return

Implementation of Deletion from rear end

void delete_item_rear()
{
int num;
if(rear==0)
{
printf("\n Cannot delete item at rear
end\n"); return;
}
else
{
num=q[rear];
if(front==rear)
{
front=0;
rear=0;
}
else
{
rear--;
printf("\n Deleted item is %d\n",num);
}
}
}
Algorithms :
Write your own algorithms

Flowchart :
Draw flowchart for above algorithms

Conclusion:
By this way, we can perform operations on double ended queue

Question Bank:

1. What is queue?
2. Types of queue
3. What is double ended queue?
4. How to insert the new node in Doubly Link List?
5. How to delete the node from front of Doubly Link List ?
6. How to delete the node from end of Doubly Link List ?
7. How to delete the node in between of Doubly Link List
 Practical No:13(E)
Practical Title: Perform operations on Circular queue.
Aim: Pizza parlor accepting maximum M orders. Orders are served in first come first
served basis. Order once placed cannot be cancelled. Write C++ program to
simulate the system using circular queue using array

Pre-requisite:

• Knowledge of Circular Queue

• Types of Circular queue
• Knowledge of Singly and double Circular queue and different operations.

Objective:
• To simulate circular queue with functions to add and delete elements from
Circular queue.
Input:
Accept order
Elements in the queue
Outcome:
• Result of Circular queue with functions to accept or cancel Pizza order.

Theory :

• Why Circular Queue?

In a normal Queue Data Structure, we can insert elements until queue becomes full. But once if queue
becomes full, we can’t insert the next element until all the elements are deleted from the queue. For
example consider the queue below...

After inserting all the elements into the queue…

Now consider the following situation after deleting three elements from the queue...
This situation also says that Queue is Full and we can’t insert the new element because, 'rear' is still at
last position. In above situation, even though we have empty positions in the queue we can’t make use
of them to insert new element. This is the major problem in normal queue data structure. To overcome
this problem we use circular queue data structure.
• What is a Circular Queue?
A Circular Queue can be defined as follows...

Circular Queue is a linear data structure in which the operations are performed based on FIFO (First In
First Out) principle and the last position is connected back to the first position to make a circle.

Graphical representation of a circular queue is as follows...

Implementation of Circular Queue:

To implement a circular queue data structure using array, we first perform the following steps
before we implement actual operations.

Step 1: Include all the header files which are used in the program and define a constant 'SIZE' with
specific value.
Step 2: Declare all user defined functions used in circular queue implementation.
Step 3: Create a one dimensional array with above defined SIZE (int cQueue[SIZE])
Step 4: Define two integer variables 'front' and 'rear' and initialize both with '-1'. (int front = -1, rear
= -1) Step 5: Implement main method by displaying menu of operations list and make suitable function
calls to perform operation selected by the user on circular queue.

enQueue(value) - Inserting value into the Circular Queue:

In a circular queue, enQueue() is a function which is used to insert an element into the circular queue.
In a circular queue, the new element is always inserted at rear position. The enQueue() function
takes one integer value as parameter and inserts that value into the circular queue. We can use the
following steps to insert an element into the circular queue...

Step 1: Check whether queue is FULL. ((rear == SIZE-1 && front == 0) || (front == rear+1))
Step 2: If it is FULL, then display "Queue is FULL!!! Insertion is not possible!!!" and terminate the
function.
Step 3: If it is NOT FULL, then check rear == SIZE - 1 && front != 0 if it is TRUE, then set rear = -1.

Step 4: Increment rear value by one (rear++), set queue[rear] = value and check 'front == -1' if it
is TRUE, then set front = 0.

deQueue() - Deleting a value from the Circular Queue:

In a circular queue, deQueue() is a function used to delete an element from the circular queue. In
a circular queue, the element is always deleted from front position. The deQueue() function
doesn't take any value as parameter. We can use the following steps to delete an element from
the circular queue...

Step 1: Check whether queue is EMPTY. (front == -1 && rear == -1)

Step 2: If it is EMPTY, then display "Queue is EMPTY!!! Deletion is not possible!!!" and terminate the
function. Step 3: If it is NOT EMPTY, then display queue[front] as deleted element and increment the
front value by one (front ++). Then check whether front == SIZE, if it is TRUE, then set front = 0. Then
check whether both front - 1 and rear are equal (front -1 == rear), if it TRUE, then set both front and
rear to '-1' (front = rear = -1).
display () - Displays the elements of a Circular Queue:
We can use the following steps to display the elements of a circular queue...

Step 1: Check whether queue is EMPTY. (front == -1)

Step 2: If it is EMPTY, then display "Queue is EMPTY!!!" and terminate the function.
Step 3: If it is NOT EMPTY, then define an integer variable 'i' and set 'i = front'.
Step 4: Check whether 'front <= rear', if it is TRUE, then display 'queue[i]' value and increment 'i'
value by one (i++). Repeat the same until 'i <= rear' becomes FALSE.
Step 5: If 'front <= rear' is FALSE, then display 'queue[i]' value and increment 'i' value by one (i++).
Repeat the same until'i <= SIZE - 1' becomes FALSE.
Step 6: Set i to 0.
Step 7: Again display 'cQueue[i]' value and increment i value by one (i++). Repeat the same until 'i
<= rear' becomes FALSE.

Algorithms :
Write your own algorithms

Flowchart :
Draw flowchart for above algorithms

Conclusion:

Hence we have learned how to implement Circular Queue and perform various operations on it.

Question Bank:

1. What is Circular queue?

2. Types of Circular queue
3. What is double ended queue?
4. How to insert the new node in Circular Link List?
5. How to delete the node from front of Circular Link List