DATA

STRUCTURE
Darshan P
Dept of MCA
RRCE
DATA STRUCTURE
MCA(I SEM)
Darshan P
 Syllabus
Module 2
 Recursion
 Factorial
 GCD
 Fibonacci Sequence,
 Tower of Hanoi.
 Queue: Definition
 Representation
 Queue Variants: Circular Queue, Priority Queue, Double Ended Queue;
 Applications of Queues.
 Programming Examples
RECURSION

◦Recursion is a programming technique where a function calls itself directly or

indirectly in order to solve a problem.
◦This technique involves breaking down a larger problem into smaller, similar
sub-problems, until reaching a base case where the solution is trivial.
◦Recursion is commonly used in algorithms where a problem can be solved by
dividing it into smaller instances of the same problem.
◦It often simplifies code and makes it more elegant, but improper use can lead
to stack overflow errors or inefficient solutions.
PROPERTIES OF RECURSION
[Link] the function: Start by defining the function, giving it a name that reflects
its purpose.
[Link] Case: Inside the function, you typically have a conditional statement that
checks for a base case, which is the simplest scenario where the function can return
a result without further recursion. This prevents the function from infinitely calling
itself.
[Link] Case: If the base case is not met, the function calls itself with modified
arguments to solve a smaller version of the problem. This is called the recursive
case.
[Link] Value: Ensure that each branch of the function returns a value. In the base
case, you directly return a value. In the recursive case, you return the result of
calling the function recursively.
EXAMPLE

◦Void fun()
◦{
◦…………
◦Fun();
◦…………
◦}
Advantage of Recursion
[Link] adds clarity and (sometimes) reduces the time needed to write and debug code (but
doesn't necessarily reduce space requirements or speed of execution).
[Link] time complexity.
[Link] better in solving problems based on tree structures.
[Link] unnecessary calling of functions.
[Link] Recursion one can solve problems in easy way while its iterative solution is very big
and complex.
[Link] useful when applying the same solution.
Disadvantage of Recursion
It is usually slower due to the overhead of maintaining the stack.
It usually uses more memory for the stack.
Recursive methods will often throw a Stack OverflowException when
processing big sets. Recursive loops don't have this problem though.
Recursion uses more processor time.
It is difficult to find errors.
It may lead to infinite loops.
Application of Recursion
◦Divide and conquer technique.
Quick sort, Merge sort
◦Tree Traversal
Preorder, In order , Post order
◦Reversing the string.
◦Evaluating the exponent
Factorial of a Number
What is Factorial
◦In programming, a factorial refers to the product of all positive integers from
1 to a given number.
◦For example, the factorial of 5 (denoted as 5!) is calculated as 5 x 4 x 3 x 2 x 1,
which equals 120.
GCD
◦ The greatest common divisor (GCD) of two or more numbers is the greatest common factor
number that divides them, exactly. It is also called the highest common factor (HCF).
◦ For example, the greatest common factor of 15 and 10 is 5, since both the numbers can be
divided by 5. 15/5 = 3. 10/5 = 2
Different methods to find GCD

◦Middle school Procedure

◦Euclidean Algorithm
◦Repetatitive subtraction method
◦Consecutive integer checking
GCD using Middle school method
◦The algorithm to find GCD using Middle School procedure GCD (m, n):
[Link] the prime factorization of m.
[Link] the prime factorization of n.
[Link] all the common prime factors.
[Link] the product of all the common prime factors and return it as
gcd (m, n).
Euclidean Algorithm

◦ Algorithm: gcd(a,b)
◦ Step 1: if b=0 then perform do next step otherwise go to step 3
◦ Step 2:return b as GCD of two numbers
◦ Step 3:Set a=b and b=a%b and repeat step 1

◦ a if b=0
◦ Gcd(a,b)=
◦ gcd(b,a%b) if b>0
Repetatitive subtraction method

◦Algorithm gcd(a,b)
◦Step 1: if a=b then perform next step otherwise go to step 3.
◦Step 2:Return a as GCD of a and b
◦Step 3:if a>b then Set ‘a=a-b’ otherwise set ‘b=b-a’.
◦Step 4:Repeat step 1.
Fibonacci Series
◦ The Fibonacci series is a series of elements where, the previous two elements are added to get
the next element, starting with 0 and 1. In this article, we will learn how to print Fibonacci
Series in Java up to the N term, where N is the given number.

◦ Input: N = 10
Output: 0 1 1 2 3 5 8 13 21 34
Explanation: Here first term of Fibonacci is 0 and second is 1, so that 3rd term = first(o) +
second(1) etc and so on.
Tower of Honai
◦ Tower of Hanoi is a mathematical puzzle where we have three rods (A, B, and C) and N disks.
Initially, all the disks are stacked in decreasing value of diameter i.e., the smallest disk is
placed on the top and they are on rod A. The objective of the puzzle is to move the entire stack
to another rod (here considered C), obeying the following simple rules:
• Only one disk can be moved at a time.
• Each move consists of taking the upper disk from one of the stacks and placing it on top of
another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
• No disk may be placed on top of a smaller disk.
◦Input: 2
Output: Disk 1 moved from A to B
Disk 2 moved from A to C
Disk 1 moved from B to C
◦Input: 3
Output: Disk 1 moved from A to C
Disk 2 moved from A to B
Disk 1 moved from C to B
Disk 3 moved from A to C
Disk 1 moved from B to A
Disk 2 moved from B to C
Disk 1 moved from A to C
Queue
Queue
◦The data structure which permits the insertion at one and deletion at
another end, known as Queue.
◦End at which deletion is occurs is known as FRONT end and
another end at which insertion occurs is known as REAR end.
◦Queue is also called as First In First Out (FIFO)
 Enqueue()
◦ Inserts an element at the end of the queue i.e. at the rear end.
◦ The following steps should be taken to enqueue (insert) data into a queue:
• Check if the queue is full.
• If the queue is full, return overflow error and exit.
• If the queue is not full, increment the rear pointer to point to the next empty space.
• Add the data element to the queue location, where the rear is pointing.
• return success.
Dequeue()

◦This operation removes and returns an element that is at the front end of the
queue.
◦The following steps are taken to perform the dequeue operation:
• Check if the queue is empty.
• If the queue is empty, return the underflow error and exit.
• If the queue is not empty, access the data where the front is pointing.
• Increment the front pointer to point to the next available data element.
• The Return success.
Front()

◦ This operation returns the element at the front end without removing it.
◦ The following steps are taken to perform the front operation:
• If the queue is empty return the most minimum value.
• otherwise, return the front value.
Rear()

◦ This operation returns the element at the rear end without removing it.
◦ The following steps are taken to perform the rear operation:
• If the queue is empty return the most minimum value.
• otherwise, return the rear value.
IsEmpty():

◦ This operation returns a boolean value that indicates whether the queue is empty or not.
◦ The following steps are taken to perform the Empty operation:
• check if front value is equal to -1 or not, if yes then return true means queue is empty.
• Otherwise return false, means queue is not empty
Queue Variants

◦Ordinary Queue
◦Circular Queue
◦Priority Queue
◦Double Ended Queue
Linear Queue
◦ A linear queue, often simply referred to as a "queue," is a fundamental data structure in
computer science that follows the First In, First Out (FIFO) principle. It operates much like a
queue in real life—items are added to the back of the queue and removed from the front. This
means that the first item to be inserted into the queue is the first to be removed.
Disadvantage
[Link] Size: Most implementations of linear queues use arrays, which have a fixed size. This
limitation means that if the queue becomes full, further enqueue operations are not possible,
leading to a situation known as "queue overflow." In contrast, dynamic data structures like
linked lists can grow dynamically, avoiding this limitation.
[Link] Waste: If the queue size is fixed to accommodate the maximum expected number of
elements, it may lead to memory wastage if the queue is not consistently full. This is because
the allocated memory for the queue remains unused when the queue is not at full capacity.
Circular Queue
◦ A circular queue, also known as a ring buffer, is a variation of the linear queue that addresses
some of the limitations of the linear queue, particularly the issue of memory wastage and the
need for expensive resizing operations. In a circular queue, the last element of the queue is
connected back to the first element, forming a circle.
[Link] Use of Memory: In a circular queue, when an element is dequeued, the space it
occupied becomes available for future enqueue operations. This means that memory usage is
more efficient compared to linear queues, where space at the beginning of the queue remains
unused after dequeuing elements.
[Link] Resizing Overhead: Circular queues typically have a fixed size, and they avoid the need
for resizing operations present in dynamic linear queues. Since the size is fixed, there's no
need to reallocate memory or shift elements when enqueuing or dequeuing.
Disadvantage
[Link] Size: Like linear queues implemented with arrays, circular queues have
a fixed size determined at initialization. If the queue becomes full, further
enqueue operations are not possible, leading to a situation known as "queue
overflow."
[Link] Capacity: The capacity of a circular queue is limited by the size of
the underlying array. If the number of elements exceeds this capacity, overflow
occurs, and additional elements cannot be added until space becomes
available.
Priority Queue
◦ A priority queue is a data structure that stores elements along with their associated priorities. Unlike
traditional queues, where elements are retrieved in the order they were added (FIFO), in a priority
queue, elements are retrieved based on their priority. The element with the highest (or lowest,
depending on the implementation) priority is dequeued first.
[Link]-based Ordering: Elements are stored in the queue based on their priority. Higher priority
elements are dequeued before lower priority elements.
[Link] Operations: Priority queues support operations such as insertion (enqueue), deletion of the
highest priority element (dequeue), and possibly updating the priority of elements.
[Link] Strict Ordering: While priority queues do impose an ordering based on priorities, they typically
don't enforce strict ordering among elements with the same priority. This allows for more flexibility in
handling elements with equal priority.
[Link] Operations: Priority queues are designed to efficiently support operations such as insertion
and deletion of the highest priority element. Depending on the implementation, these operations can
have different time complexities.
Disadvantage
◦ Complexity of Implementation: Some implementations of priority queues, such as Fibonacci
heaps, can be complex to implement and understand. This complexity can make it challenging to
debug and maintain code using priority queues, especially for less experienced developers.
◦ Limited Support for Dynamic Priorities: Many priority queue implementations assume static
priorities assigned to elements. If priorities change frequently during the lifetime of the queue,
maintaining the heap property or rebalancing the data structure to reflect priority changes can be
inefficient.
◦ Memory Overhead: Some priority queue implementations, such as Fibonacci heaps, may incur
higher memory overhead compared to simpler data structures like binary heaps or sorted lists.
This overhead can be a disadvantage in memory-constrained environments or applications
requiring minimal memory usage.
Double Ended Queue
◦ A double-ended queue, often abbreviated as deque (pronounced "deck"), is a versatile data structure that
supports insertion and deletion operations at both ends. It combines the features of both stacks and
queues, allowing elements to be added or removed from either the front or the back of the deque.
[Link] Size: Unlike arrays with fixed sizes, deques can dynamically grow and shrink as elements are
added or removed. This dynamic resizing capability makes them suitable for scenarios where the number
of elements varies unpredictably.
[Link] Insertions and Deletions: Deques typically provide constant-time insertion and deletion
operations at both ends. This efficiency is crucial for applications requiring fast insertion and removal of
elements from either end of the deque.
3. Random Access: Some deque implementations may support random access to elements, allowing direct
access to elements at specific indices. This feature can be useful in scenarios where indexed access to
elements is required.
What is a Deque (or double-ended
queue)
◦ The deque stands for Double Ended Queue. Deque is a linear data structure where the insertion and
deletion operations are performed from both ends. We can say that deque is a generalized version of the
queue.
◦ Though the insertion and deletion in a deque can be performed on both ends, it does not follow the FIFO
rule. The representation of a deque is given as follows -
Types of Deque

• Input restricted queue

• Output restricted queue
Input restricted Queue
◦In input restricted queue, insertion operation can be performed at only one end,
while deletion can be performed from both ends.
Output restricted Queue
◦ In output restricted queue, deletion operation can be performed at only one end, while
insertion can be performed from both ends.
Application of Queue
1. Resource allocation: Queues are used to manage access to shared resources in systems where multiple
processes or threads need to access a resource but can't do so simultaneously. For example, printers often use
queues to manage print jobs from multiple users.
2. Job scheduling: Operating systems use queues to schedule processes for execution based on priority or other
criteria. Jobs are placed in a queue and executed in the order they were received or based on their priority
level.
3. Breadth-first search (BFS): Queues are an essential component of graph traversal algorithms like BFS. In
BFS, nodes are visited level by level, and a queue is used to keep track of the nodes that need to be explored
at each level.
4. Buffering: Queues are commonly used for buffering in computer networks and communication systems.
Incoming data packets are stored in a queue until they can be processed or transmitted further.
5. Task management: Queues are used in task management systems to handle tasks or requests in a first-come-
first-served manner. For example, customer service centers often use queues to manage customer inquiries or
support tickets.
6. Event handling: Queues are used in event-driven programming to manage events generated by user
interactions or system processes. Events are typically queued up and processed in the order they occurred.
Thank You