SY([Link].

) Program in Information
Technology Semester – II
Course Name: Data Structures and Analysis
(Course Code: ITC302)

Module – 1
Introduction to Stacks, Queues and Linked Lists

Dr. Harsh Namdev Bhor

PhD (CSE), ME (IT), BE (Computer)
PCP – Coordinator
[Link]/in/drhbhor-3a721039

Dr. Harsh Namdev Bhor

KJSIT, Sion – Data Structure and Analysis – ITC302 Dr. Harsh Namdev Bhor
KJSIT, Sion – Data Structure and Analysis – ITC302 Dr. Harsh Namdev Bhor
KJSIT, Sion – Data Structure and Analysis – ITC302 Dr. Harsh Namdev Bhor
KJSIT, Sion – Data Structure and Analysis – ITC302 Dr. Harsh Namdev Bhor
KJSIT, Sion – Data Structure and Analysis – ITC302 Dr. Harsh Namdev Bhor
KJSIT, Sion – Data Structure and Analysis – ITC302 Dr. Harsh Namdev Bhor
 Definition

Data Structures are a way of

organizing and storing data in a computer such that

it can be retrieved and used effectively

(DS considers not only the elements stored but also their

relationship to each other)

E.g. Array

KJSIT, Sion – Data Structure and Analysis – ITC302 Dr. Harsh Namdev Bhor
 DS

Why We Need Data Structures

• Organized data

• Efficient data management

• Optimal performance

• Scalability

• Reusability and maintenance

KJSIT, Sion – Data Structure and Analysis – ITC302 Dr. Harsh Namdev Bhor
 DS

KJSIT, Sion – Data Structure and Analysis – ITC302 Dr. Harsh Namdev Bhor
 DS

[Link] Data Structure

[Link]-Linear Data Structure

KJSIT, Sion – Data Structure and Analysis – ITC302 Dr. Harsh Namdev Bhor
 DS

A linear data structure is

one in which the components are stored in a sequential order and are
linked to the elements before and after them.
items are kept in a sequential order, they can be accessed or traversed in a
single operation.
elements are progressively ordered in memory, linear data structures are
easy to build.
An array's data items are traversed one by one, and you can only
access one element at a time.
Array, Stack, Queue, Linked list, and other linear data
structures are examples.
KJSIT, Sion – Data Structure and Analysis – ITC302 Dr. Harsh Namdev Bhor
 DS

Characteristics - linear data structure :

•Elements are stored in a sequential order.

•Each element has a unique predecessor and successor (except

the first and last elements).

•Traversal is typically straightforward and in a single direction.

KJSIT, Sion – Data Structure and Analysis – ITC302 Dr. Harsh Namdev Bhor
 DS

•Linear Data Structures: Elements are arranged in a sequential

order (e.g., Arrays, Linked Lists, Stacks, Queues).

•Non-Linear Data Structures: Elements are arranged in a

hierarchical or interconnected manner (e.g., Trees, Graphs).

KJSIT, Sion – Data Structure and Analysis – ITC302 Dr. Harsh Namdev Bhor
 DS

Non-Linear Data Structure,

the elements are not arranged sequentially.
they can be connected to multiple elements, forming a hierarchical
or interconnected structure.
This allows for more complex relationships among data elements.
Characteristics:
 Elements are stored in a hierarchical or interconnected manner.
 Each element may be connected to multiple elements.
 Traversal can be complex, often requiring algorithms like Depth-
First Search (DFS) or Breadth-First Search (BFS).
KJSIT, Sion – Data Structure and Analysis – ITC302 Dr. Harsh Namdev Bhor
 Rank

KJSIT, Sion – Data Structure and Analysis – ITC302 Dr. Harsh Namdev Bhor
 Rank

Rank in postfix expressions measures

how "complete" the expression is

at any given point in terms of operands and operators.

track whether there are enough operands for each operator and

ensures the overall structure of the expression is correct.

KJSIT, Sion – Data Structure and Analysis – ITC302 Dr. Harsh Namdev Bhor
 Rank

Rank Calculation Process:

1. Start with a rank of 0.

2. Traverse the expression from left to right (for a postfix

expression).

3. For each operand, add 1 to the rank.

4. For each operator, subtract 1 from the rank.

KJSIT, Sion – Data Structure and Analysis – ITC302 Dr. Harsh Namdev Bhor
 Rank

Postfix Expression: 3 4 + 5 *

•Initial Rank: 0

Step 1 - 3: Operand, rank increases by 1 (Rank = 1)

Step 2 - 4: Operand, rank increases by 1 (Rank = 2)
Step 3 - +: Operator, rank decreases by 1 (Rank = 1)
Step 4 - 5: Operand, rank increases by 1 (Rank = 2)
Step 5 - *: Operator, rank decreases by 1 (Rank = 1)

Final Rank: 1

KJSIT, Sion – Data Structure and Analysis – ITC302 Dr. Harsh Namdev Bhor
 Rank

Validity of the Expression

A postfix expression is valid if, after processing all the symbols in
the expression, the rank equals 1.

This final rank of 1 indicates that exactly one value (the result of
the entire expression) remains, which is what we expect for a
well-formed expression.

KJSIT, Sion – Data Structure and Analysis – ITC302 Dr. Harsh Namdev Bhor
 DS

Asymptotic Notations:
•Asymptotic Notations are mathematical tools used to analyze the performance of algorithms by
understanding how their efficiency changes as the input size grows.
•These notations provide a concise way to express the behavior of an algorithm’s time or space complexity
as the input size approaches infinity.
•Rather than comparing algorithms directly, asymptotic analysis focuses on understanding the relative
growth rates of algorithms’ complexities.
•It enables comparisons of algorithms’ efficiency by abstracting away machine-specific constants and
implementation details, focusing instead on fundamental trends.
•Asymptotic analysis allows for the comparison of algorithms’ space and time complexities by examining
their performance characteristics as the input size varies.
•By using asymptotic notations, such as Big O, Big Omega, and Big Theta, we can categorize algorithms
based on their worst-case, best-case, or average-case time or space complexities, providing valuable insights
into their efficiency.

KJSIT, Sion – Data Structure and Analysis – ITC302 Dr. Harsh Namdev Bhor
 DS

Theta Notation (Θ-Notation)

Theta notation encloses the function from above and below. Since it
represents the upper and the lower bound of the running time of an algorithm,
it is used for analyzing the average-case complexity of an algorithm.

Theta (Average Case) You add the running times for each possible input
combination and take the average in the average case.

KJSIT, Sion – Data Structure and Analysis – ITC302 Dr. Harsh Namdev Bhor
 DS

•Big O (O): Upper bound (worst-case).

•Omega (Ω): Lower bound (best-case).
•Theta (θ): Tight bound (average-case or overall growth rate).

Theta bounds the function within constants factors

For a function g(n), Θ(g(n)) is given by the relation:
Θ(g(n)) = { f(n): there exist positive constants c1, c2 and n0 such that 0 ≤ c1g(n) ≤ f(n)
≤ c2g(n) for all n ≥ n0 }

KJSIT, Sion – Data Structure and Analysis – ITC302 Dr. Harsh Namdev Bhor
 DS

Big-O Notation (O-notation):

Big-O notation represents the upper bound of the running time of an algorithm.
Therefore, it gives the worst-case complexity of an algorithm.

.It is the most widely used notation for Asymptotic analysis.

.It specifies the upper bound of a function.
.The maximum time required by an algorithm or the worst-case time complexity.
.It returns the highest possible output value(big-O) for a given input.
.Big-O(Worst Case) It is defined as the condition that allows an algorithm to
complete statement execution in the longest amount of time possible.

KJSIT, Sion – Data Structure and Analysis – ITC302 Dr. Harsh Namdev Bhor
 DS

•Big O (O): Upper bound (worst-case).

•Omega (Ω): Lower bound (best-case).
•Theta (θ): Tight bound (average-case or overall growth rate).

Big-O gives the upper bound of a function

O(g(n)) = { f(n): there exist positive constants c and n0 such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0 }

KJSIT, Sion – Data Structure and Analysis – ITC302 Dr. Harsh Namdev Bhor
 DS

Omega Notation (Ω-Notation):

Omega notation represents the lower bound of the running time of an
algorithm. Thus, it provides the best case complexity of an algorithm.

The execution time serves as a lower bound on the algorithm’s time

complexity.

It is defined as the condition that allows an algorithm to complete

statement execution in the shortest amount of time.

KJSIT, Sion – Data Structure and Analysis – ITC302 Dr. Harsh Namdev Bhor
 DS

•Big O (O): Upper bound (worst-case).

•Omega (Ω): Lower bound (best-case).
•Theta (θ): Tight bound (average-case or overall growth rate).

Omega gives the lower bound of a function

Ω(g(n)) = { f(n): there exist positive constants c and n0
such that 0 ≤ cg(n) ≤ f(n) for all n ≥ n0 }

KJSIT, Sion – Data Structure and Analysis – ITC302 Dr. Harsh Namdev Bhor
 DS

The word Algorithm means ” A set of finite rules or instructions to

be followed in calculations or other problem-solving operations ”
Or
A procedure for solving a mathematical problem in a finite number
of steps that frequently involves recursive operations”.

KJSIT, Sion – Data Structure and Analysis – ITC302 Dr. Harsh Namdev Bhor
 DS

Characteristics of algorithms:
• Well-described steps
• Input and output
• Finiteness
• Determinism
• Efficiency
• Generality
• Correctness
• Modularity and reusability
• Understandability
KJSIT, Sion – Data Structure and Analysis – ITC302 Dr. Harsh Namdev Bhor
 DS

Push Operation in Stack:

Adds an item to the stack.
If the stack is full,
then it is said to be an Overflow condition.

Algorithm for Push Operation:

Before pushing the element to the stack, we check if the stack is full .
If the stack is full (top == capacity-1) ,
then Stack Overflows and we cannot insert the element to the stack.

Otherwise, we increment the value of top by 1

(top = top + 1) and the new value is inserted at top position .
The elements can be pushed into the stack till we reach the capacity of the stack.

KJSIT, Sion – Data Structure and Analysis – ITC302 Dr. Harsh Namdev Bhor
 DS

Pop Operation in Stack:

Removes an item from the stack.
The items are popped in the reversed order in which they are pushed.
If the stack is empty,
then it is said to be an Underflow condition.

Algorithm for Pop Operation:

1. Before popping the element from the stack, we check if the stack is empty.
2. If the stack is empty (top == -1),
then Stack Underflows and we cannot remove any element from the stack.
1. Otherwise, we store the value at top,
decrement the value of top by 1 (top = top – 1) and return the stored top value.

KJSIT, Sion – Data Structure and Analysis – ITC302 Dr. Harsh Namdev Bhor