Data Structure Laboratory (SE)

DEPARTMENT OF COMPUTER ENGINEERING

BRAHMA VALLEY COLLEGE OF ENGINEERING AND
RESEARCH INSTITUTE NASHIK

Second Year of Computer Engineering

(2019 Course)

Data Structures Laboratory

(210247)

SAVITRIBAI PHULE PUNE UNIVERSITY

A.Y 2024-25

BVCOE&RI, Nashik
Data Structure Laboratory (SE)

Savitribai Phule Pune University

Second Year of Computer Engineering (2019 Course)
210247: Data Structures Laboratory
Teaching Scheme: Credit02 Examination Scheme:
PR: 04 Hours/Week TW: 25 Marks
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'smanual need
to include prologue (about University/program/ institute/ department/foreword/ preface), University syllabus,
conduction & Assessment guidelines, topics under consideration- concept, objectives, outcomes, set of typical
applications/assignments/ guidelines, and
references.
Guidelines for Student's Laboratory Journal
The laboratory assignments 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 assignment (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, Test Data Set(if applicable),
mathematical model (if applicable), conclusion/analysis. Program codes with sample output of all
performed assignments 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 Laboratory In-charge is highly encouraged.
For reference one or two journals may be maintained with program prints at Laboratory.

Guidelines for Laboratory /TW Assessment

Continuous assessment of laboratory work is done based on overall performance and Laboratory assignments
performance of student. Each Laboratory assignment assessment will assign grade/marks based on parameters
with appropriate weightage. Suggested parameters for overall assessment as well as each Laboratory
assignment assessment include- timely completion,
performance, innovation, efficient codes, punctuality and neatness.
Guidelines for Laboratory Conduction
The instructor is expected to frame the assignments by understanding the prerequisites, technological aspects,
utility and recent trends related to the topic. The assignment framingpolicy need to address the average
students and inclusive of an element to attract and promote the intelligent students. The instructor may set
multiple sets of assignments and distribute amongbatches of students. It is appreciated if the assignments are
based on real world problems/applications. Encourage students for appropriate use of Hungarian notation,
proper indentation and comments. Use of open source software is to be encouraged. In addition tothese,
instructor may assign one real life application in the form of a mini-project based on the concepts learned.
Instructor may also set one assignment or mini-project that is suitable to respective branch beyond the scope
of syllabus.
Set of suggested assignment list is provided in groups- A, B, C, D, and E. Each student must perform at least
13 assignments as at least 3 from group A, 3 from group B, 2 from group C, 2from 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 andE 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++/GCC,

BVCOE&RI, Nashik
Data Structure Laboratory (SE)

Suggested List of Laboratory Experiments/Assignments

Sr.
Group A
No.
In second year computer engineering class, group A student’s play cricket, group Bstudents
play badminton and group C students play football.
Write a Python program using functions to compute following: -
List of students who play both cricket and badminton
1 List of students who play either cricket or badminton but not both
Number of students who play neither cricket nor badminton
Number of students who play cricket and football but not badminton.
(Note- While realizing the group, duplicate entries should be avoided, Do not use SET
built-in functions)
Write a Python program to store marks scored in subject “Fundamental of DataStructure”
by N students in the class. Write functions to compute following:
The average score of class
2
Highest score and lowest score of class
Count of students who were absent for the test
Display mark with highest frequency
Write a Python program for department library which has N books, write functions for
following:
3 Delete the duplicate entries
Display books in ascending order based on cost of books
Count number of books with cost more than 500.
Copy books in a new list which has cost less than 500.
Write a Python program that computes the net amount of a bank account based a transaction
log from console input. The transaction log format is shown as following: D 100 W 200
(Withdrawal is not allowed if balance is going negative. Write functions for withdraw and
deposit) D means deposit while W means withdrawal.
pose the following input is supplied to the program: D
4
300
D 300
W 200
D 100
Then, the output should be: 500
Write a Python program to compute following operations on String:
To display word with the longest length
To determines the frequency of occurrence of particular character in the string
5
To check whether given string is palindrome or not
To display index of first appearance of the substring
To count the occurrences of each word in a given string
It is decided that weekly greetings are to be furnished to wish the students having their
birthdays in that week. The consolidated sorted list with desired categorical informationis
to be provided to the authority. Write a python program to store students PRNs with date
6 and month of birth. Let List_A and List_B be the two list for two SE Computer divisions.
Lists are sorted on date and month. Merge these two lists into third list
“List_SE_Comp_DOB” resulting in sorted information about Date of Birth of SE Computer
students

BVCOE&RI, Nashik
Data Structure Laboratory (SE)

Write a python Program for magic square. A magic square is an n * n matrix of the integers
1 to n2 such that the sum of each row, column, and diagonal is the same. The figure given
below is an example of magic square for case n=5. In this example, the common sum is 65.

Write a python program that determines the location of a saddle point of matrix if one
8 exists. An m x n matrix is said to have a saddle point if some entry a[i][j] is the smallest
value in row i and the largest value in j.
Write a python program to compute following computation on matrix:
Addition of two matrices
9 Subtraction of two matrices
Multiplication of two matrices
Transpose of a matrix
Write a python program for sparse matrix realization and operations on it- Transpose,
10
Fast Transpose and addition of two matrices
Group B
Write a pythonprogram to store roll numbers of student in array who attended training
program in random order. Write function for searching whether particular student attended
training program or not, using Linear search and Sentinel search.
11
Write a python program to store roll numbers of student array who attended training program
in sorted order. Write function for searching whether particular studentattended training
program or not, using Binary search and Fibonacci search
Write a python program to store names and mobile numbers of your friends in sorted order
on names. Search your friend from list using binary search (recursive and non- recursive).
Insert friend if not present in phonebook
12
Write a python program to store names and mobile numbers of your friends in sorted
order on names. Search your friend from list using Fibonacci search. Insert friend if not
present in phonebook.
Write a python program to maintain club members, sort on roll numbers in ascending order.
13 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.

Write a pythonprogram to store first year percentage of students in array. Write functionfor
sorting array of floating point numbers in ascending order using
14
Selection Sort
Bubble sort and display top five scores.
Write a python program to store second year percentage of students in array. Write
function for sorting array of floating point numbers in ascending order using
15
Insertion sort
Shell Sort and display top five scores

BVCOE&RI, Nashik
Data Structure Laboratory (SE)

Write a python program to store first year percentage of students in array. Write function
16 for sorting array of floating point numbers in ascending order using quick sort and displaytop
five scores.
Write a python program to store 12th class percentage of students in array. Write
17 function for sorting array of floating point numbers in ascending order using bucket sortand
display top five scores.

Write python program to store 10th class percentage of students in array. Write functionfor
18 sorting array of floating point numbers in ascending order using radix sort and display
top five scores
Group C
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 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:
19
Add and delete the members as well as president or even secretary.
Compute total number of members of club
Display members
Two linked lists exists for two divisions. Concatenate two lists.

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
20 store pointers (Head pointer) to each row. On demand
The list of available seats is to be displayed
The seats are to be booked
The booking can be cancelled.
Write C++ program for storing appointment schedule for day. Appointments are booked
randomly using linked list. Set start and end time and min and max duration for visit slot.
Write functions for-
Display free slots
21
Book appointment
Cancel appointment ( check validity, time bounds, availability)
Sort list based on time
Sort list based on time using pointer manipulation
Second year Computer Engineering class, set A of students like Vanilla Ice-cream and set
B of students like butterscotch ice-cream. Write C++ program to store two sets using linked
list. compute and display-
22
Set of students who like both vanilla and butterscotch
Set of students who like either vanilla or butterscotch or not both
Number of students who like neither vanilla nor butterscotch
Write C++ program for storing binary number using doubly linked lists. Write functions-
23 To compute 1‘s and 2‘s complement
Add two binary numbers
Write C++ program to realize Set using Generalized Liked List (GLL)
24
e.g. A ={ a, b, {c, d,e, {}, {f,g}, h, I, {j,k}, l, m}. Store and print as set notation.
Group D

BVCOE&RI, Nashik
Data Structure Laboratory (SE)

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
25 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-
To print original string followed by reversed string using stack
To check whether given string is palindrome or not

In any language program mostly syntax error occurs due to unbalancing delimiter such as
26 (),{},[]. Write C++ program using stack to check whether given expression is well
parenthesized or not.
Implement C++ program for expression conversion as infix to postfix and its evaluation
using stack based on given conditions:
27 Operands and operator, both must be single character.
Input Postfix expression must be in a desired format.
Only '+', '-', '*' and '/ ' operators are expected.
A classic problem that can be solved by backtracking is called the Eight Queens problem,
which comes from the game of chess. The chess board consists of 64 square arranged in an
8 by 8 grid. The board normally alternates between black and white square, but this is not
relevant for the present problem. The queen can move as far as she wants in any direction,
28
as long as she follows a straight line, Vertically, horizontally, or diagonally. Write C++
program with recursive function for generating all possible configurations for 4-queen's
problem.

Group E
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
29
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.
Write program to implement a priority queue in C++ using an inorder list to store the items
in the queue. Create a class that includes the data items (which should be template) and the
30 priority (which should be int). The inorder list should contain these objects, with operator <=
overloaded so that the items with highest priority appear at the
beginning of the list (which will make it relatively easy to retrieve the highest item.)
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.
31
Write C++ program to simulate deque with functions to add and
delete elements from either end of the deque.
Pizza parlor accepting maximum M orders. Orders are served in first come first served
32 basis. Order once placed cannot be cancelled. Write C++ program to simulate the system
using circular queue using array.

BVCOE&RI, Nashik
Data Structure Laboratory (SE)

Practical No:04(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.

Software Requirements:

Jupiter Notebook, PyCharm, Spyder C++,

Input:
Size of array Elements of array

Theory:

- Write short theory of sorting with its advantages and disadvantages.

Sorting refers to the process of arranging a collection of data items in a specific order, usually in
ascending or descending order. It is a fundamental operation in computer science, used to organize
data to improve the efficiency of other algorithms such as searching, merging, and more. Sorting can
be performed using various algorithms, each with different time complexities and practical use cases.

Types of Sorting

Bubble Sort: A simple comparison-based algorithm that repeatedly swaps adjacent elements if they
are in the wrong order.

Selection Sort: Involves selecting the minimum (or maximum) element from the unsorted part of the
array and swapping it with the first unsorted element.

Insertion Sort: Builds the sorted array one element at a time, by picking the next element and placing
it in the correct position among the previously sorted elements.

Merge Sort: A divide-and-conquer algorithm that splits the array into smaller subarrays, recursively
sorts them, and then merges the sorted subarrays.

Quick Sort: A divide-and-conquer algorithm that selects a pivot element, partitions the array into
two subarrays (one with elements less than the pivot and one with elements greater than the pivot),
and recursively sorts the subarrays.

BVCOE&RI, Nashik
Data Structure Laboratory (SE)
Heap Sort: Converts the array into a binary heap data structure, then sorts the array by repeatedly
extracting the maximum element from the heap.

Advantages of Sorting

Efficiency in Searching: Sorted data allows for faster searching techniques, such as binary search,
which significantly reduces the time complexity from O(n) to O(log n).

Data Organization: Sorted data is easier to analyze and visualize, especially for tasks such as
reporting, data mining, or other analytics.

Prepares Data for Other Algorithms: Many algorithms (e.g., merging algorithms, dynamic
programming algorithms) work more efficiently on sorted data.

Stability: Some sorting algorithms (e.g., Merge Sort, Insertion Sort) are stable, meaning that they
preserve the relative order of equal elements.

Disadvantages of Sorting

Time Complexity: Sorting can be time-consuming. For example, Bubble Sort and Selection Sort
have O(n²) time complexity in the worst case, making them inefficient for large datasets.

Space Complexity: Algorithms like Merge Sort require additional space for the recursive subarrays,
leading to higher space complexity (O(n) in the case of Merge Sort).

Unnecessary Sorting: In cases where the data is already nearly sorted, algorithms like Insertion Sort
can be more efficient than Merge Sort or Quick Sort. However, for large datasets, the overhead of
sorting might not justify the benefits.

Sensitive to Input Data: Certain algorithms, like Quick Sort, can perform poorly if the pivot
selection is not ideal, resulting in O(n²) time complexity in the worst case.

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):
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]

BVCOE&RI, Nashik
Data Structure Laboratory (SE)
selectionSort(alist) print(alist)

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?

BVCOE&RI, Nashik
Data Structure Laboratory (SE)

Practical No :05(B)
Practical Title : Sorting of an array using insertion and shell sort

Aim: Write a Python program to store second year percentage of students in array. Write function for
sorting array of floating point numbers in ascending order using
a) Insertion sort
b) Shell Sort and display top five scores

Pre-requisite:
a. Knowledge of sorting techniques

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

c. Sorted list of elements

d. Top five scores.

Software Requirements:

Jupiter Notebook, PyCharm, Spyder C++,

Input:
Size of array Elements of array

Theory:
 sorting.

Sorting refers to rearrangement of a given array or list of elements according to a

comparison operator on the elements. The comparison operator is used to decide the new
order of elements in the respective data structure.

- Explain insertion and shell sort with example

Insertion sort:
Insertion Sort is a simple comparison-based sorting algorithm that builds the sorted list one element
at a time. It works similarly to the way you might sort playing cards in your hands. The idea is to take
each element from the unsorted portion of the array and insert it into its correct position in the already
sorted portion. Example of Insertion Sort:

Let’s sort the array [12, 11, 13, 5, 6] using Insertion Sort.

First Pass:

Current element: 11.

Compare 11 with 12 (the first element).

BVCOE&RI, Nashik
Data Structure Laboratory (SE)
11 is smaller than 12, so shift 12 to the right.

Insert 11 in the first position.

Array after the first pass: [11, 12, 13, 5, 6].

Second Pass:

Current element: 13.

Compare 13 with 12. 13 is larger, so leave it in its position.

Array after the second pass: [11, 12, 13, 5, 6].

Third Pass:

Current element: 5.

Compare 5 with 13. 5 is smaller, so shift 13 to the right.

Compare 5 with 12. 5 is smaller, so shift 12 to the right.

Compare 5 with 11. 5 is smaller, so shift 11 to the right.

Insert 5 at the first position.

Array after the third pass: [5, 11, 12, 13, 6].

Fourth Pass:

Current element: 6.

Compare 6 with 13. 6 is smaller, so shift 13 to the right.

Compare 6 with 12. 6 is smaller, so shift 12 to the right.

Compare 6 with 11. 6 is smaller, so shift 11 to the right.

Insert 6 at the second position.

Array after the fourth pass: [5, 6, 11, 12, 13].

The array is now sorted.

Final Sorted Array: [5, 6, 11, 12, 13]

Shell sort:

Shell Sort is an improvement on Insertion Sort. It generalizes the concept of insertion sort by allowing
the comparison and movement of elements that are far apart, which helps to break the "bad" behaviour
of Insertion Sort (where elements are only compared to neighbours). This leads to faster sorting for
larger datasets. Shell Sort works by using a sequence of gap values to compare elements at a certain

BVCOE&RI, Nashik
Data Structure Laboratory (SE)
distance apart and then gradually reducing the gap size until it becomes 1, at which point the algorithm
behaves like Insertion Sort Example of Shell Sort:

Let’s sort the array [12, 34, 54, 2, 3] using Shell Sort with a gap sequence of 3, 1.

Gap = 3:

Compare elements that are 3 positions apart.

Compare 12 and 2 (positions 0 and 3). 12 > 2, so swap them: [2, 34, 54, 12, 3].

Compare 34 and 3 (positions 1 and 4). 34 > 3, so swap them: [2, 3, 54, 12, 34].

Now, the array is partially sorted.

Gap = 1:

Perform a regular insertion sort.

Compare 3 and 2 (positions 1 and 0). 3 > 2, so no change.

Compare 54 and 3 (positions 2 and 1). 54 > 3, so no change.

Compare 12 and 54 (positions 3 and 2). 12 < 54, so swap them: [2, 3, 12, 54, 34].

Compare 34 and 54 (positions 4 and 3). 34 < 54, so swap them: [2, 3, 12, 34, 54].

Now the array is fully sorted.

Final Sorted Array: [2, 3, 12, 34, 54]

Algorithm:

def selectionSort(alist):
for fillslot in range(len(alist)-1,0,-1):
positionOfMax=0 for location in range(1,fillslot+1):
if a
list[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)
def shellSort(alist):
sublistcount = len(alist) //2
while
sublistcount > 0:
for
startposition in range(sublistcount):
BVCOE&RI, Nashik
Data Structure Laboratory (SE)
gapInsertionSort(alist,startposition,sublistcount)
print("After increments of size",sublistcount,"The list is",alist)
sublistcount = sublistcount // 2
def
gapInsertionSort(alist,start,gap):
for i in range(start+gap,len(alist),gap):
currentvalue = alist[i] position = i
while
position>=gap and alist[position-gap]>currentvalue:
alist[position]=alist[position-gap]
position = position-gap
alist[position]=currentvalue

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

Conclusion:
By this way, we can sort percentage of students in array using insertion sort and shell sort.

Question Bank:
1. Explain the sorting?
2. What are the different types of sorts in data structures
3.Define the insertion sort?
4. Define the shell sort?
5. How many passes are required in insertion and shell sort?
6. What is the time complexity of insertion and shell sort?

BVCOE&RI, Nashik
Data Structure Laboratory (SE)
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

Software Requirements:

Jupiter Notebook, PyCharm, Spyder C++,

Input:
Size of array
First year percentage of students.
Outcome:
• To sort array using quick sort
• To display top five scores.

Theory :

Quick sort
Quick Sort is a divide-and-conquer algorithm that works by selecting a pivot element from the array
and partitioning the other elements into two subarrays. One subarray contains elements smaller than
the pivot, and the other contains elements greater than the pivot. The subarrays are then sorted
recursively.

Advantages of Quick Sort:

Efficient for Large Data Sets: Quick Sort is one of the fastest sorting algorithms, especially for large
datasets. Its average time complexity is O(n log n), making it much faster than algorithms like Bubble
Sort or Selection Sort (O(n²)).

In-Place Sorting: Quick Sort requires only a small, constant amount of extra space (O(log n) due to
recursive calls), making it memory-efficient compared to algorithms like Merge Sort, which requires
O(n) additional space.

Cache Efficiency: Due to its partitioning nature, Quick Sort exhibits good cache performance. It
tends to access contiguous memory locations more often, which is beneficial for performance on
modern hardware.

Scalability: Quick Sort works well on large datasets and can be parallelized, which can further
improve performance on multi-core processors.

Disadvantages of Quick Sort:

BVCOE&RI, Nashik
Data Structure Laboratory (SE)
Worst-case Time Complexity: The worst-case time complexity of Quick Sort is O(n²), which occurs
when the pivot is poorly chosen (e.g., when the pivot is always the smallest or largest element, leading
to unbalanced partitions). This can happen if the input array is already sorted or nearly sorted.

Unstable Sort: Quick Sort is not a stable sort, meaning that it does not necessarily preserve the
relative order of equal elements in the sorted array. For example, if two equal elements appear in the
original array, their relative order may not be preserved after sorting.

Overhead of Recursion: In practice, Quick Sort may suffer from the overhead of recursive calls. If
the depth of recursion becomes too large, it may lead to stack overflow issues in languages that don’t
optimize tail recursion.

Not Adaptive: Quick Sort does not perform particularly well on nearly sorted arrays. In such cases,
algorithms like Insertion Sort may be more efficient.

- Time complexity.

Best Case: O(n log n) – Occurs when the pivot divides the array into nearly equal-sized subarrays.

Average Case: O(n log n) – This is the expected time complexity for a random input array, where
the pivot divides the array approximately in half.

Worst Case: O(n²) – Occurs when the pivot selection is poor, such as when the pivot is always the
smallest or largest element, causing unbalanced partitions.

Time Complexity Breakdown:

Partitioning takes O(n) time (since it processes each element of the array once).

Each recursive call reduces the size of the problem roughly by half, leading to O(log n) levels of
recursion.

So, in the best and average cases, Quick Sort performs O(n log n) work. In the worst case, if the pivot
does not divide the array well, it results in O(n²).

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,last)
def partition(alist,first,last):
pivotvalue = alist[first] l
eftmark = first+1 rightmark = last done = False while not done:
while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
leftmark = leftmark + 1
BVCOE&RI, Nashik
Data Structure Laboratory (SE)
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)

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

Question:
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?

BVCOE&RI, Nashik
Data Structure Laboratory (SE)

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.

Software Requirements:

Jupiter Notebook, PyCharm, Spyder C++,

Theory:

A linked list is a linear data structure where elements (also called nodes) are stored in separate
memory locations. Unlike arrays, the nodes in a linked list are not stored in contiguous memory
locations. Each node contains two components:

Data: The actual information stored in the node.

Pointer/Reference: A reference or pointer to the next node in the sequence (in the case of a singly
linked list, or it may reference both the next and previous nodes in the case of a doubly linked list).

Linked lists allow efficient insertions and deletions since elements can be added or removed without
the need to s Types of Linked Lists

Singly Linked List (SLL):

A singly linked list consists of nodes, where each node contains data and a pointer to the next node.
The last node's pointer is set to NULL, indicating the end of the list.

Doubly Linked List (DLL):

In a doubly linked list, each node contains data, a pointer to the next node, and a pointer to the previous
node, allowing traversal in both directions.

BVCOE&RI, Nashik
Data Structure Laboratory (SE)
Circular Linked List:

In a circular linked list, the last node's pointer points back to the first node instead of NULL. Circular
linked lists can be singly or doubly linked.

Circular Singly Linked List (CSLL):

A type of circular linked list where each node points to the next node, and the last node points back
to the first node.

Circular Doubly Linked List (CDLL):

A combination of circular and doubly linked list where each node points to both the next and previous
nodes, and the first node is linked to the last node, and vice versa.

shift other elements, which is common in array-based data structures.

Singly Linked List (SLL)

Definition:

A Singly Linked List is a type of linked list where each node contains:

Data: The actual value the node holds.

Next pointer: A reference to the next node in the list. If a node is the last node, its next pointer is set
to NULL.

A singly linked list allows traversal in only one direction (from the first node to the last node).

Concepts of Singly Linked List:

Head: The first node in the linked list. This is the entry point to access the entire list.

Tail: The last node in the linked list. Its next pointer is NULL.

Node: Each element in the list that holds data and a reference to the next node.

Traversal: Moving from the head node to the last node (or NULL), accessing each node one by one.

Insertion: Adding a node at the beginning, middle, or end of the list.

Deletion: Removing a node from the beginning, middle, or end of the list.

Advantages of Singly Linked List:

Dynamic Size: Linked lists allow dynamic memory allocation, meaning the list size can grow or
shrink as needed without wasting memory.

Efficient Insertion/Deletion: Inserting or deleting a node in a linked list (especially at the beginning
or middle) is much faster compared to arrays because no shifting of elements is required.

BVCOE&RI, Nashik
Data Structure Laboratory (SE)
No Wasted Space: Unlike arrays, linked lists do not need a predefined size, so no extra space is wasted
if the list doesn't fill the entire allocated space.

Disadvantages of Singly Linked List:

Random Access: Linked lists do not support random access. To access a specific element, you must
traverse the list from the beginning, which takes O(n) time.

Extra Memory: Each node requires extra memory for storing the pointer/reference to the next node.
This leads to higher memory overhead compared to arrays.

Complexity in Implementation: Manipulating pointers in a linked list is more complex than dealing
with arrays, especially when handling edge cases like empty lists, single-node lists, or deleting the
last node.

Singly Linked List as an Abstract Data Type (ADT)

An Abstract Data Type (ADT) defines a data structure purely in terms of its operations without
specifying the implementation details. For a Singly Linked List (SLL), the ADT would include the
following operations:

Insert: Add a new node at the beginning, end, or after a specified node.

Delete: Remove a node from the beginning, end, or a specified position.

Search: Find if a given element exists in the list.

Traversal: Visit all nodes in the list to process or print them.

Size: Return the number of nodes in the list.

Is Empty: Check if the list is empty.

Conclusion:
By this way, we can maintain club member‘s information using singly linked list.
Questions:
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?

BVCOE&RI, Nashik
Data Structure Laboratory (SE)

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

Software Requirements:

Jupiter Notebook, PyCharm, Spyder C++,

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

Theory :

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

Circular Doubly Linked List (CDLL)

Definition:

A Circular Doubly Linked List (CDLL) is a type of linked list where:

Each node contains three parts:

Data: The actual data or value held by the node.

Next Pointer: A reference to the next node in the sequence.

Prev Pointer: A reference to the previous node in the sequence.

BVCOE&RI, Nashik
Data Structure Laboratory (SE)
In a circular doubly linked list, both the first node's previous pointer points to the last node, and the
last node's next pointer points to the first node. This circular structure allows traversal to loop back
to the starting point once we reach the end.

This structure allows for traversal in both directions (forward and backward) and is especially useful
in applications where you need a circular structure (e.g., a playlist or a round-robin scheduler).

Concepts of Circular Doubly Linked List (CDLL):

Head Node: The first node in the circular doubly linked list.

Tail Node: The last node in the circular doubly linked list. The tail node's next pointer points to the
head node, and the head node's previous pointer points to the tail.

Traversal: The list can be traversed in both directions (from head to tail and vice versa).

Circular Nature: The tail node is linked back to the head, and the head node is linked back to the
tail, making the list circular.

Structure of a Node in CDLL:

+ + + +

| Data | Next | Prev |

+ + + +

| Data | Points | Points |

+ + + +

Advantages of Circular Doubly Linked List:

Bidirectional Traversal: Unlike singly linked lists, CDLL allows easy traversal in both directions
(from the head to the tail and vice versa). This can be especially useful for certain applications like
undo/redo functionality or doubly linked playlists.

Circular Nature: The circular structure allows for a continuous loop, which can be beneficial in
scenarios like round-robin scheduling or maintaining a playlist where after the last element, the first
element is accessed again.

Efficient Insertions and Deletions: Insertions and deletions can be done efficiently from both ends
(head and tail), especially if the list is maintained as a circular structure. This reduces the need for
traversal in some cases.

No Null Pointers: In a CDLL, there are no NULL references for the next and prev pointers, making
it simpler to write algorithms that rely on looping through the entire list.

Disadvantages of Circular Doubly Linked List:

Memory Overhead: Each node in a circular doubly linked list requires two pointers (next and prev),
as opposed to a singly linked list, which only requires one. This results in higher memory usage.

BVCOE&RI, Nashik
Data Structure Laboratory (SE)
Complex Implementation: Managing the head and tail pointers, as well as handling edge cases like
an empty list or single-node list, can make the implementation more complex compared to singly
linked lists.

More Pointer Management: Since both forward and backward traversal pointers need to be
maintained and properly updated during insertions and deletions, there is a higher risk of pointer-
related bugs (e.g., incorrect linking).

Circular Doubly Linked List as an ADT (Abstract Data Type)

The Circular Doubly Linked List (CDLL) can be treated as an ADT and defined with the following
operations:

Insert at the Beginning: Adds a new node at the head of the list.

Insert at the End: Adds a new node at the tail of the list.

Delete from the Beginning: Removes the node at the head of the list.

Delete from the End: Removes the node at the tail of the list.

Search: Searches for a given value in the list.

Traverse Forward: Traverses the list from head to tail.

Traverse Backward: Traverses the list from tail to head.

Size: Returns the number of nodes in the list.

Is Empty: Checks if the list is empty.

Questions:
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?

BVCOE&RI, Nashik
Data Structure Laboratory (SE)

Practical No:09(D)
Practical Title: Write C++ program to check well formedness 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.

Software Requirements:

Jupiter Notebook, PyCharm, Spyder C++,

Input:
Expresstion using {},(),[].
Outcome:
• Result of checking well formedness of parenthesis.

Theory :

. A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. This means that
the element added last to the stack will be the first one to be removed. Think of it like a stack of plates
where you can only add or remove the top plate.

Basic Operations of Stack:

Push: Adds an element to the top of the stack.

Pop: Removes the top element from the stack.

Peek/Top: Returns the top element without removing it.

IsEmpty: Checks whether the stack is empty.

Size: Returns the number of elements in the stack.

Stacks are commonly used in situations such as:

Reversing data (e.g., reversing a string).

Implementing recursive function calls.

Parsing expressions (e.g., balancing parentheses).

Backtracking algorithms.

BVCOE&RI, Nashik
Data Structure Laboratory (SE)
Types of Stack Implementations:

Array-based Stack: Uses a fixed-size array to implement a stack.

Linked List-based Stack: Each stack node points to the next node, with the top element pointing to
the first node.

Concept of Well-Formed Parentheses

A string containing parentheses (or any type of bracket) is said to be well-formed if:

Each opening parenthesis has a matching closing parenthesis.

The parentheses are correctly nested, meaning the parentheses must close in the reverse order of their
opening.

For example, the string "(())" is well-formed because each opening parenthesis ( has a corresponding
closing parenthesis ), and they are correctly nested.

Conditions for Well-formed Parentheses:

Every opening parenthesis ( must have a corresponding closing parenthesis ).

The closing parenthesis ) should occur after the matching opening parenthesis (.

The parentheses must be properly nested, i.e., no closing parenthesis should appear before a matching
opening parenthesis.

Example of Well-Formed Parentheses

Well-formed examples:

() : One pair of parentheses, correctly matched.

(()) : Nested pairs of parentheses.

(()()) : Correctly nested with multiple pairs.

(((()))) : Deeply nested and correctly formed.

Not well-formed examples:

( : Missing closing parenthesis.

(() : One closing parenthesis is missing.

()) : Closing parenthesis comes before opening one.

())( : Improper nesting.

Algorithm to Check for Well-formed Parentheses Using Stack

BVCOE&RI, Nashik
Data Structure Laboratory (SE)
The most common approach to check for well-formed parentheses is using a stack. The algorithm
works as follows:

Traverse the string from left to right.

For each character:

If the character is an opening parenthesis (, push it onto the stack.

If the character is a closing parenthesis ), pop an element from the stack. If the stack is empty, it
means there is no matching opening parenthesis, so the string is not well-formed.

After traversing the entire string, if the stack is empty, the parentheses are well-formed. Otherwise,
there are unmatched opening parentheses, and the string is not well-formed.

Pseudo Code:

function is Valid Parentheses(str):

stack = empty stack

for each character c in str:

if c is '(': // Opening parenthesis

push stack, '('else if c is ')'://Closing

parenthesis if stack is empty:

return False // No opening parenthesis to match

else:

pop stack // Pop the last opening parenthesis

if stack is empty:

return True // All parentheses matched

else:

return False // Some opening parentheses are unmatched

Algorithm Explanation:

Push Operation: When encountering an opening parenthesis (, push it onto the stack to mark the start
of a new pair.

Pop Operation: When encountering a closing parenthesis ), check if there is an opening parenthesis
to match by popping from the stack. If the stack is empty when trying to pop, it indicates there is no
matching opening parenthesis, so the string is not well-formed.

BVCOE&RI, Nashik
Data Structure Laboratory (SE)
Final Check: After the loop ends, check if the stack is empty. If the stack is empty, it means all
opening parentheses have been matched and closed correctly. Otherwise, there are unmatched
opening parentheses left in the stack, so the string is not well-formed.

Conclusion:
By this way, we can check well formedness of parenthesis using stack.
Question:
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?

BVCOE&RI, Nashik
Data Structure Laboratory (SE)

Practical No:10 (D)

Practical Title: Write a C++ program for expression conversion as infix to postfix and its evaluation
using stack

Aim: Implement C++ program for expression conversion as infix to postfix and its evaluation using stack
based on given conditions
i. Operands and operator, both must be single character.
ii. Input Postfix expression must be in a desired format.
iii. Only '+', '-', '*' and '/ ' operators are expected

Pre-requisite:
• Basics of stack.
• Different operations that can be performed on stack

Objective:
• To convert the expression from infix to postfix
• Evaluate the expression

Software Requirements:

Jupiter Notebook, PyCharm, Spyder C++,

Input:
Infix expression
Outcome:
• Equivalent postfix expression
• Result of evaluation of an expression.

Theory :

A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. This means that
the most recently added element is the first one to be removed, similar to a stack of plates where you
can only add or remove the top plate.

Basic Operations of Stack:

Push: Adds an element to the top of the stack.

Pop: Removes the top element from the stack.

Peek/Top: Returns the top element of the stack without removing it.

IsEmpty: Checks if the stack is empty.

Size: Returns the number of elements in the stack.

Stacks are commonly used in a variety of applications, such as:

BVCOE&RI, Nashik
Data Structure Laboratory (SE)
Expression evaluation (infix, postfix, prefix).

Undo functionality in applications.

Function call management in recursive algorithms.

Backtracking algorithms (e.g., maze solvers, puzzle solvers).

Infix to Postfix Expression Conversion

The infix expression is the usual mathematical notation where operators are placed between operands
(e.g., A + B). The postfix notation (also known as Reverse Polish Notation, RPN) places the operator
after the operands (e.g., A B +).

In order to evaluate an infix expression using a computer, it is usually converted to postfix. This is
because evaluating postfix expressions can be done more easily using a stack, and postfix notation
removes the need for parentheses to indicate precedence.

Conversion Algorithm (Infix to Postfix):

Operands (A-Z, 0-9): Directly add operands to the postfix expression.

Left Parenthesis (: Push to the stack to signify that a sub-expression starts.

Right Parenthesis ): Pop from the stack until the left parenthesis ( is encountered, which is discarded.

Operators (+, -, *, /): Pop operators from the stack to the postfix expression if the operator at the top
of the stack has greater precedence, then push the current operator onto the stack.

End of Expression: Pop all remaining operators in the stack to the postfix expression.

Operator Precedence:

^ (Exponentiation): Highest precedence.

*, /: Medium precedence.

+, -: Lowest precedence.

Parentheses () are used to alter the default precedence.

Example of Infix to Postfix Conversion

Consider the infix expression:

Infix: A + B * C

Step 1: Operand A is added to the postfix expression → Postfix: A

Step 2: Operator + is pushed to the stack → Stack: +

Step 3: Operand B is added to the postfix expression → Postfix: A B

BVCOE&RI, Nashik
Data Structure Laboratory (SE)
Step 4: Operator * is pushed to the stack (because * has higher precedence than +) → Stack: + *

Step 5: Operand C is added to the postfix expression → Postfix: A B C

Step 6: No more operands; pop all remaining operators from the stack to the postfix expression →
Postfix: A B C * +

Final Postfix: A B C * +

Algorithm to Convert Infix to Postfix

Here is the algorithm to convert an infix expression to a postfix expression using a stack:

Algorithm:

Initialize an empty stack and an empty list for the postfix expression.

For each character in the infix expression:

If the character is an operand (letter or number), append it to the postfix expression.

If the character is an operator, pop operators from the stack to the postfix expression until an operator
with lower precedence or a left parenthesis is found, then push the current operator onto the stack.

If the character is a left parenthesis (, push it to the stack.

If the character is a right parenthesis ), pop from the stack to the postfix expression until a left
parenthesis is encountered.

After processing all characters, pop any remaining operators from the stack to the postfix expression.

Return the postfix expression.

Conclusion:
By this way, we can perform expression conversion as infix to postfix and its evaluation using stack
Question :
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?
5. What is infix, postfix and prefix expression?
6. Conversion – infix to postfix, infix to prefix , etc.
7. Evaluation of infix, postfix and prefix expression

BVCOE&RI, Nashik
Data Structure Laboratory (SE)

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.

Software Requirements:

Jupiter Notebook, PyCharm, Spyder G++,

Input:
Size of queue Elements in queue

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

Theory :

A queue is a linear data structure that follows the First In, First Out (FIFO) principle. This means
that the first element added to the queue will be the first one to be removed, similar to a line of
people waiting at a ticket counter.

The queue operates in two main areas:

Front: The end where elements are dequeued (removed).

Rear: The end where elements are enqueued (added).

Basic Operations of a Queue:

Enqueue: Adds an element to the rear of the queue.

Dequeue: Removes an element from the front of the queue.

Front/Peek: Returns the front element without removing it.

IsEmpty: Checks whether the queue is empty.

Size: Returns the number of elements in the queue.

BVCOE&RI, Nashik
Data Structure Laboratory (SE)
Queues are widely used in scenarios where resources are shared or tasks need to be processed in the
order they arrive, such as:

Scheduling processes in operating systems.

Handling requests in web servers.

Print job management in printers.

Concepts of Queue:

FIFO (First In, First Out): The first element added to the queue will be the first one to be removed.
This order is maintained throughout the operations of enqueue and dequeue.

Front and Rear:

The front of the queue is where elements are dequeued from.

The rear of the queue is where elements are enqueued to.

Empty Queue: A queue is empty when the number of elements is zero, i.e., no elements to dequeue.

A queue is a linear data structure that follows the First In, First Out (FIFO) principle. This means
that the first element added to the queue will be the first one to be removed, similar to a line of
people waiting at a ticket counter. The queue operates in two main areas:

Front: The end where elements are dequeued (removed).

Rear: The end where elements are enqueued (added).

Basic Operations of a Queue:

Enqueue: Adds an element to the rear of the queue.

Dequeue: Removes an element from the front of the queue.

Front/Peek: Returns the front element without removing it.

IsEmpty: Checks whether the queue is empty.

Size: Returns the number of elements in the queue.

Queues are widely used in scenarios where resources are shared or tasks need to be processed in the
order they arrive, such as:

Scheduling processes in operating systems.

Handling requests in web servers.

Print job management in printers.

Concepts of Queue:

BVCOE&RI, Nashik
Data Structure Laboratory (SE)
FIFO (First In, First Out): The first element added to the queue will be the first one to be removed.
This order is maintained throughout the operations of enqueue and dequeue.

Front and Rear:

The front of the queue is where elements are dequeued from.

The rear of the queue is where elements are enqueued to.

Empty Queue: A queue is empty when the number of elements is zero, i.e., no elements to dequeue.

Types of Queue:

Simple Queue:

A basic queue where elements are added at the rear and removed from the front.

Limitations: In a simple queue, once an element is dequeued, it leaves empty space at the front,
which can lead to inefficient use of memory.

Circular Queue:

A variation of the simple queue, where the last element points back to the first element, forming a
circle. This eliminates wasted space when elements are dequeued.

The front and rear pointers wrap around the queue, making it more efficient in utilizing memory.

Double-Ended Queue (Deque):

A queue where insertion and deletion operations can be performed at both ends (front and rear).

Deques can be implemented using two stacks or a linked list.

Priority Queue:

In this type of queue, each element is associated with a priority value. Elements are dequeued based
on their priority rather than the order they were enqueued.

Max-priority queue: The element with the highest priority is dequeued first.

Min-priority queue: The element with the lowest priority is dequeued first.

Advantages of Queue:

Orderly Processing: Ensures that elements are processed in the order they arrive, which is crucial
in many real-world applications (e.g., printer queues, process scheduling).

Fairness: Provides fair access to shared resources by serving elements on a first-come, first-served
basis.

Efficiency in Task Management: Useful in situations where tasks are processed sequentially (e.g.,
network packet management, request handling in web servers).

BVCOE&RI, Nashik
Data Structure Laboratory (SE)
Disadvantages of Queue:

Limited Access: Elements can only be added at the rear and removed from the front, so direct access
to elements is not possible.

Fixed Size (in array-based implementation): If the queue reaches its maximum size, no more
elements can be added until some are dequeued.

Memory Wastage: In a simple queue, memory can be wasted when elements are dequeued but the
front of the queue doesn't reset, leading to inefficient memory usage. This problem is resolved in
circular queues.

Queue as an Abstract Data Type (ADT)

A Queue ADT is an abstraction that defines the operations and behavior of a queue without
specifying the underlying implementation details (array, linked list, etc.).

Queue ADT Operations:

Enqueue: Adds an element to the rear of the queue.

Dequeue: Removes an element from the front of the queue.

Front/Peek: Returns the front element without removing it.

IsEmpty: Checks if the queue is empty.

Size: Returns the number of elements in the queue.

Clear: Removes all elements from the queue.

Simple Queue:

A basic queue where elements are added at the rear and removed from the front.

Limitations: In a simple queue, once an element is dequeued, it leaves empty space at the front,
which can lead to inefficient use of memory.

Circular Queue:

A variation of the simple queue, where the last element points back to the first element, forming a
circle. This eliminates wasted space when elements are dequeued.

The front and rear pointers wrap around the queue, making it more efficient in utilizing memory.

Double-Ended Queue (Deque):

A queue where insertion and deletion operations can be performed at both ends (front and rear).

Deques can be implemented using two stacks or a linked list.

Priority Queue:

BVCOE&RI, Nashik
Data Structure Laboratory (SE)
In this type of queue, each element is associated with a priority value. Elements are dequeued based
on their priority rather than the order they were enqueued.

Max-priority queue: The element with the highest priority is dequeued first.

Min-priority queue: The element with the lowest priority is dequeued first.

Advantages of Queue:

Orderly Processing: Ensures that elements are processed in the order they arrive, which is crucial
in many real-world applications (e.g., printer queues, process scheduling).

Fairness: Provides fair access to shared resources by serving elements on a first-come, first-served
basis.

Efficiency in Task Management: Useful in situations where tasks are processed sequentially (e.g.,
network packet management, request handling in web servers).

Disadvantages of Queue:

Limited Access: Elements can only be added at the rear and removed from the front, so direct access
to elements is not possible.

Fixed Size (in array-based implementation): If the queue reaches its maximum size, no more
elements can be added until some are dequeued.

Memory Wastage: In a simple queue, memory can be wasted when elements are dequeued but the
front of the queue doesn't reset, leading to inefficient memory usage. This problem is resolved in
circular queues.

Queue as an Abstract Data Type (ADT)

A Queue ADT is an abstraction that defines the operations and behavior of a queue without
specifying the underlying implementation details (array, linked list, etc.).

Queue ADT Operations:

Enqueue: Adds an element to the rear of the queue.

Dequeue: Removes an element from the front of the queue.

Front/Peek: Returns the front element without removing it.

Is Empty: Checks if the queue is empty.

Size: Returns the number of elements in the queue.

Clear: Removes all elements from the queue.

Algorithms :

BVCOE&RI, Nashik
Data Structure Laboratory (SE)
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), if it 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 3: Display 'queue[i]' value and increment 'i' value by one (i++). Repeat the same until 'i' value is
equal to rear (i <= rear)

Conclusion:
By this way, we can perform different operations on queue
Question :
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.

BVCOE&RI, Nashik
Data Structure Laboratory (SE)

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.

Software Requirements:

Jupiter Notebook, PyCharm, Spyder G++,

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()
{

BVCOE&RI, Nashik
Data Structure Laboratory (SE)
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
{
BVCOE&RI, Nashik
Data Structure Laboratory (SE)
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
Implement

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

BVCOE&RI, Nashik
Data Structure Laboratory (SE)
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

BVCOE&RI, Nashik
 Data Structure Laboratory (SE)

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.

Software Requirements:

Jupiter Notebook, PyCharm, Spyder G++,

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...

BVCOE&RI, Nashik
 Data Structure Laboratory (SE)

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:

BVCOE&RI, Nashik
 Data Structure Laboratory (SE)

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 ?

BVCOE&RI, Nashik