Need for Data Structures
Data Structures organize data = efficient programs.
The choice of data structure??
A data structure requires certain amount of:
“Time , Space, Programming efforts.”
Data Structures deals with the study of how data is organized in the
memory, how efficiently the data can be retrieved and manipulated,
and possibly the different data items are logically related.
This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
Classification of Data
Structures
This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
Classification of Data
Structures
Dynamic Data Structures: grow and shrink during execution
Linked Lists: insertions and removal made anywhere
Stacks: insertions and removal made only at top of the stack
Queues: insertion made at the back and removal made from the front
Binary Trees: high speed searching and sorting of data
Graphs: non-linear data structure consisting nodes and edges
This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
Asymptotic Notations
The efficiency of an algorithm is dependent on amount of time, storage and other resources.
The efficiency is measured with the help of asymptotic notations.
Asymptotic notations are mathematical notations used to describe the running time of an
algorithm.
Example: Bubble Sort:
1. If input array is already sorted: best case
2. If array is in reverse condition: worst case
3. Array is neither sorted nor in reverse condition: average case
This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
Asymptotic Notations
There are mainly three asymptotic notations:
•Big-O Notation (O-notation) -------------- represents upper bound of
running time of algo. (worst case complexity)
•Omega Notation (Ω-notation)------------- represents lower bound of the
running time of algo. (best case
complexity)
•Theta Notation (Θ-notation)--------------represents upper & lower bound
of the runningThistime of algo. (average case
video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
Divide and Conquer Algo.
A divide and conquer algorithm is a strategy of solving a large
problem by
1. breaking the problem into smaller sub-problems
2. solving the sub-problems, and
3. combining them to get the desired output.
How Divide and Conquer Algorithms Work?
Here are the steps involved:
1.Divide: Divide the given problem into sub-problems using
recursion.
2.Conquer: Solve the smaller sub-problems recursively. If the
subproblem is small enough, then solve it directly.
3.Combine: Combine the solutions of the sub-problems that are
part of the recursive
This video is sole property of process topenalsolve
Talent Battle Pvt. Ltd. Strict the
action will be taken actual
against unauthorized problem.
piracy of this video
Array
Instead of creating separate variables to store
data, it is an efficient organization to store
data in a single variable called array
Definition: An array is defined as a collection of
items stored at contiguous memory locations under
the same name
Ex: int (a,b,c,d,e )can be grouped in a single
variable as int a[5]: now five continuous memory
location are assigned with the same name ‘a’
This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
Array: Practice Examples
1. Java program to read array of size n and find the frequency of the given
element.
2. Java program to find the array type (even, odd or mixed)
Algorithm to find the array type (even, odd or mixed array)
•Input the number of elements of the array.
•Input the array elements.
•If all the elements of the array are odd, display "Odd".
•If all the elements of the array are even, display "Even".
•Else, display "Mixed".
This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
STACK Data Structure
• A stack is a useful data structure in programming.
• It is just like a pile of plates kept on top of each other.
Think about the things you can do with such a pile of plates
•Put a new plate on top
•Remove the top plate
If you want the plate at the bottom, you must first remove all the plates on top.
Such an arrangement is called Last In First Out - the last item that is the first
item to go out.
This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
LIFO Principle of Stack
In programming terms, putting an item on top of the stack is called push and
removing an item is called pop.
This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
Basic Operations of Stack
A stack is an object (an abstract data type - ADT) that allows the following
operations:
•Push: Add an element to the top of a stack
•Pop: Remove an element from the top of a stack
•IsEmpty: Check if the stack is empty
•IsFull: Check if the stack is full
•Peek: Get the value of the top element without removing it
This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
Working of Stack Data
Structure
The operations work as follows:
1. A pointer called TOP is used to keep track of the top element in
the stack.
2. When initializing the stack, we set its value to -1 so that we can
check if the stack is empty by comparing TOP == -1.
3. On pushing an element, we increase the value of TOP and place the
new element in the position pointed to by TOP.
4. On popping an element, we return the element pointed to by TOP and
reduce its value.
5. Before pushing, we check if the stack is already full
6. Before popping, we check if the stack is already empty
This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
Working of Stack Data
Structure
This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
Stack Applications
Applications of Stack Data Structure
Although stack is a simple data structure to implement, it is very powerful.
The most common uses of a stack are:
• To reverse a word - Put all the letters in a stack and pop them out.
Because of the LIFO order of stack, you will get the letters in reverse
order.
• In compilers - Compilers use the stack to calculate the value of
expressions like
2 + 4 / 5 * (7 - 9) by converting the expression to prefix or postfix form.
• In browsers - The back button in a browser saves all the URLs you have
visited previously in a stack. Each time you visit a new page, it is added on
top of the stack. When you press the back button, the current URL is removed
from the stack, and the previous URL is accessed.
This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
