Data Structures
Module-2
Syllabus
• INTRODUCTION TO ADT:
Stack: Definition, Array Representation of Stack, Operations on Stacks.
Applications of Stack: Expression evaluation, Conversion of Infix to Postfix, Infix
to Prefix, Recursion, Tower of Hanoi
Queue: Definition, Representation of Queues, Operations of Queues, Circular
Queue.
Applications of Queue: Job Scheduling, A Maze Problem
Slides prepared by: Dr. Santhosh Kumar G , Department of CSE(Data Science), Dayananda Sagar University, Harohalli, Karnataka. 2
Introduction To ADT
• Abstract Data type (ADT) is a type (or class) for objects whose behavior is
defined by a set of values and a set of operations.
• The definition of ADT only mentions what operations are to be performed but not
how these operations will be implemented.
• It does not specify how data will be organized in memory and what algorithms
will be used for implementing the operations.
• It is called “abstract” because it gives an implementation-independent view.
• The three ADTs namely List ADT, Stack ADT, Queue ADT.
Slides prepared by: Dr. Santhosh Kumar G , Department of CSE(Data Science), Dayananda Sagar University, Harohalli, Karnataka. 3
Stacks
• Stack is a linear data structure that follows a particular order in which the operations are
performed.
• The order may be LIFO `(Last In First Out) or FILO (First In Last Out).
• LIFO implies that the element that is inserted last, comes out first and FILO implies that the
element that is inserted first, comes out last.
Slides prepared by: Dr. Santhosh Kumar G , Department of CSE(Data Science), Dayananda Sagar University, Harohalli, Karnataka. 4
Stack of Blueberry Pancakes
Slides prepared by: Dr. Santhosh Kumar G , Department of CSE(Data Science), Dayananda Sagar University, Harohalli, Karnataka. 5
Stack
• To implement the stack, it is required to maintain the pointer to the top of the
stack, which is the last element to be inserted because we can access the elements
only on the top of the stack.
Slides prepared by: Dr. Santhosh Kumar G , Department of CSE(Data Science), Dayananda Sagar University, Harohalli, Karnataka. 6
Array Representation of Stack
• In the computer’s memory, stacks can be represented as a linear array.
• Every stack has a variable called TOP associated with it, which is used to store the
address of the topmost element of the stack.
• It is this position where the element will be added to or deleted from.
• There is another variable called MAX, which is used to store the maximum number of
elements that the stack can hold.
• If TOP = NULL, then it indicates that the stack is empty and if TOP = MAX–1, then the
stack is full.
Slides prepared by: Dr. Santhosh Kumar G , Department of CSE(Data Science), Dayananda Sagar University, Harohalli, Karnataka. 7
Basic Operations on Stack
• In order to make manipulations in a stack, there are certain operations provided to us.
• push() to insert an element into the stack
• pop() to remove an element from the stack
• top() Returns the top element of the stack.
• isEmpty() returns true if stack is empty else false.
• size() returns the size of stack.
Slides prepared by: Dr. Santhosh Kumar G , Department of CSE(Data Science), Dayananda Sagar University, Harohalli, Karnataka. 8
Basic Operations of Stack
• Push:
• Adds an item to the stack. If the stack is full, then it is said to be an Overflow
condition.
• Algorithm for push:
begin
if stack is full
return
endif
else
increment top
stack[top] assign value
end else Slides prepared by: Dr. Santhosh Kumar G , Department of CSE(Data Science), Dayananda Sagar University, Harohalli, Karnataka. 9
Basic Operation of stack
• Pop:
• 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:
begin
if stack is empty
return
endif
else
store value of stack[top]
decrement top
return value
end else
end procedure
Slides prepared by: Dr. Santhosh Kumar G , Department of CSE(Data Science), Dayananda Sagar University, Harohalli, Karnataka. 10
Basic Operation of stack
• Top: • isEmpty:
• Returns the top element of the stack. • Returns true if the stack is empty, else false.
• Algorithm for Top: • Algorithm for isEmpty:
begin begin
return stack[top] if top < 1
end procedure return true
else
return false
end procedure
Slides prepared by: Dr. Santhosh Kumar G , Department of CSE(Data Science), Dayananda Sagar University, Harohalli, Karnataka. 11
Applications of Stack –Expression
Evaluation
• Evaluate an expression represented by a String.
• The expression can contain parentheses, you can assume parentheses are well-matched. You can assume only
binary operations allowed are +, -, *, and /.
• Arithmetic Expressions can be written in one of three forms:
Infix Notation: Operators are written between the operands they operate on, e.g. 3 + 4.
Prefix Notation: Operators are written before the operands, e.g + 3 4
Postfix Notation: Operators are written after operands. e.g 3 4 +
Slides prepared by: Dr. Santhosh Kumar G , Department of CSE(Data Science), Dayananda Sagar University, Harohalli, Karnataka. 12
Conversion of Infix to Postfix
• Although it is easy for us to write expressions using infix notation,
computers find it difficult to parse as the computer needs a lot of information
to evaluate the expression.
• Information is needed about operator precedence and associativity rules,
and brackets which override these rules.
• The order of evaluation of a postfix expression is always from left to right.
• Even brackets cannot alter the order of evaluation.
• A postfix operation does not even follow the rules of operator precedence.
• The operator which occurs first in the expression is operated first on the
operands.
• The expression (A + B) * C can be written as:
[AB+]*C or AB+C* in the postfix notation
Slides prepared by: Dr. Santhosh Kumar G , Department of CSE(Data Science), Dayananda Sagar University, Harohalli, Karnataka. 13
Example
• Convert the following infix expressions into postfix expressions.
• Solution
(a) (A–B) * (C+D)
[AB–] * [CD+]
AB–CD+*
(b) (A + B) / (C + D) – (D * E)
[AB+] / [CD+] – [DE*]
[AB+CD+/] – [DE*]
AB+CD+/DE*–
• The precedence of these operators can be given as follows:
Higher priority *, /, %
Lower priority +, –
Slides prepared by: Dr. Santhosh Kumar G , Department of CSE(Data Science), Dayananda Sagar University, Harohalli, Karnataka. 14
Algorithm for Infix to Postfix Conversion
Let, X is an arithmetic expression written in infix notation. This algorithm finds the equivalent postfix expression Y.
1. Push “(“onto Stack, and add “)” to the end of X.
2. Scan X from left to right and repeat Step 3 to 6 for each element of X until the Stack is empty.
3. If an operand is encountered, add it to Y.
4. If a left parenthesis is encountered, push it onto Stack.
5. If an operator is encountered ,then:
1. Repeatedly pop from Stack and add to Y each operator (on the top of Stack) which has the same precedence
as or higher precedence than operator encountered.
2. Add operator to Stack.
[End of If]
6. If a right parenthesis is encountered ,then:
1. Repeatedly pop from Stack and add to Y each operator (on the top of Stack) until a left parenthesis is
encountered.
2. Remove the left Parenthesis.
[End of If]
[End of If]
7. END.
Slides prepared by: Dr. Santhosh Kumar G , Department of CSE(Data Science), Dayananda Sagar University, Harohalli, Karnataka. 15
Example using Algorithm
Slides prepared by: Dr. Santhosh Kumar G , Department of CSE(Data Science), Dayananda Sagar University, Harohalli, Karnataka. 16
Examples:
Slides prepared by: Dr. Santhosh Kumar G , Department of CSE(Data Science), Dayananda Sagar University, Harohalli, Karnataka. 17
Examples:
1. A*B+C
2. (A+B)*(C/D)
3. A*(B*C+D*E)+F
4. (A+B)*C+(D-E)/F-G
5. a + b * (c + d) / f + d * e
Bonus: P*Q/S+T/R*U+V-W*X
Slides prepared by: Dr. Santhosh Kumar G , Department of CSE(Data Science), Dayananda Sagar University, Harohalli, Karnataka. 18
Examples:
A1: AB*C+
A2: AB+CD/*
A3: ABC*DE*+*F+
A4: AB+C*DE-F/+G-
A5: a b c d + * f / + d e * +
PQ*S/TR/U*+V+WX*-
Slides prepared by: Dr. Santhosh Kumar G , Department of CSE(Data Science), Dayananda Sagar University, Harohalli, Karnataka. 19
Conversion of Infix to Prefix
• Prefix notation is also evaluated from left to right, the only
difference between a postfix notation and a prefix notation is that
in a prefix notation, the operator is placed before the operands.
• While evaluating a prefix expression, the operators are applied to
the operands that are present immediately on the right of the
operator
• Prefix expressions also do not follow the rules of operator
precedence and associativity, and even brackets cannot alter the
order of evaluation.
• If A+B is an expression in infix notation, then the
corresponding expression in prefix notation is given
by +AB.
Slides prepared by: Dr. Santhosh Kumar G , Department of CSE(Data Science), Dayananda Sagar University, Harohalli, Karnataka. 20
Example
• Convert the following infix expressions into postfix expressions.
• Solution
(a) (A–B) * (C+D)
[AB–] * [CD+]
AB–CD+*
(b) (A + B) / (C + D) – (D * E)
[AB+] / [CD+] – [DE*]
[AB+CD+/] – [DE*]
AB+CD+/DE*–
Slides prepared by: Dr. Santhosh Kumar G , Department of CSE(Data Science), Dayananda Sagar University, Harohalli, Karnataka. 21
Algorithm for Infix to Prefix Conversion
1. First, reverse the given infix expression.
2. Scan the characters one by one.
3. If the character is an operand, copy it to the prefix notation output.
4. If the character is a closing parenthesis, then push it to the stack.
5. If the character is an opening parenthesis, pop the elements in the stack until we find the
corresponding closing parenthesis.
6. If the character scanned is an operator
● If the operator has precedence greater than or equal to the top of the stack, push the
operator to the stack. op >= s[top] push to stack
● If the operator has precedence lesser than the top of the stack, pop (from the stack) and output it
to the prefix notation output and then check the above condition again with the new top of the
stack.
● op < S[top] then you pop it to Y
7. After all the characters are scanned, reverse the notation output.
Slides prepared by: Dr. Santhosh Kumar G , Department of CSE(Data Science), Dayananda Sagar University, Harohalli, Karnataka. 22
Example Using Algorithm
• Convert the infix expression A+B-C to prefix expression
Slides prepared by: Dr. Santhosh Kumar G , Department of CSE(Data Science), Dayananda Sagar University, Harohalli, Karnataka. 23
Examples:
1. a/b-(c+d)-e
2. a+b*(c+d)/f+d*e
3. a+(b*c-(d/e^f)*g)*h
Slides prepared by: Dr. Santhosh Kumar G , Department of CSE(Data Science), Dayananda Sagar University, Harohalli, Karnataka. 24
Examples:
-/ab-+cde
+a+*b/+cdf*de
+a*-*bc*/d^efgh
Slides prepared by: Dr. Santhosh Kumar G , Department of CSE(Data Science), Dayananda Sagar University, Harohalli, Karnataka. 25
Recursion
The process in which a function calls itself
directly or indirectly is called recursion and
the corresponding function is called a
recursive function.
Slides prepared by: Dr. Santhosh Kumar G , Department of CSE(Data Science), Dayananda Sagar University, Harohalli, Karnataka. 26
Recursion
Using a recursive algorithm, certain problems can be solved quite easily.
Examples of such problems are Towers of Hanoi
(TOH), Inorder/Preorder/Postorder Tree Traversals, DFS of Graph, etc
A recursive function solves a particular problem by calling a copy of itself
and solving smaller subproblems of the original problems.
Recursion is an amazing technique with the help of which we can reduce
the length of our code and make it easier to read and write.
Slides prepared by: Dr. Santhosh Kumar G , Department of CSE(Data Science), Dayananda Sagar University, Harohalli, Karnataka. 27
Recursion
Slides prepared by: Dr. Santhosh Kumar G , Department of CSE(Data Science), Dayananda Sagar University, Harohalli, Karnataka. 28
Advantages of Recursion
The advantages of using recursive methods over other methods are:
• Recursion can effectively reduce the length of the code.
• Some problems are easily solved by using recursion like the tower of Hanoi and tree traversals.
• Data structures like linked lists, trees, etc. are recursive by nature so recursive methods are easier to implement
for these data structures.
Disadvantages of Recursion
As with almost anything in the world, recursion also comes with certain limitations some of which are:
• Recursive functions make our program a bit slower due to function call overhead.
• Recursion functions always take extra space in the function call stack due to separate stack frames.
• Recursion methods are difficult to understand and implement.
Slides prepared by: Dr. Santhosh Kumar G , Department of CSE(Data Science), Dayananda Sagar University, Harohalli, Karnataka. 29
Tower of Hanoi
• 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 (From A to 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.
Slides prepared by: Dr. Santhosh Kumar G , Department of CSE(Data Science), Dayananda Sagar University, Harohalli, Karnataka. 30
Tower of Hanoi
Slides prepared by: Dr. Santhosh Kumar G , Department of CSE(Data Science), Dayananda Sagar University, Harohalli, Karnataka. 31
Tower of Hanoi
Slides prepared by: Dr. Santhosh Kumar G , Department of CSE(Data Science), Dayananda Sagar University, Harohalli, Karnataka. 32
Tower of Hanoi
Rules of Tower of Hanoi Puzzle
The Tower of Hanoi problem is solved using the set of rules given below:
Only one disc can be moved at a time.
Only the top disc of one stack can be transferred to the top of another stack or an empty rod.
Larger discs cannot be stacked over smaller ones.
The complexity of this problem can be mapped by evaluating the number of possible moves.
The least movements needed to solve the Tower of Hanoi problem with n discs
are 2^n - 1.
Slides prepared by: Dr. Santhosh Kumar G , Department of CSE(Data Science), Dayananda Sagar University, Harohalli, Karnataka. 33
Tower of Hanoi
Follow the steps below to solve the problem:
Create a function towerOfHanoi where pass the N (current number of disk), from_rod, to_rod,
aux_rod i.e towerOfHanoi(N, A, C,B)
Make a function call for N – 1 th disk.
Then print the current the disk along with from_rod and to_rod
Again make a function call for N – 1 th disk.
Input N: 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
Slides prepared by: Dr. Santhosh Kumar G , Department of CSE(Data Science), Dayananda Sagar University, Harohalli, Karnataka. 34
Tower of Hanoi
void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod) Toh(3,A,B,C)
{ Toh(2, A, C,B)
if (n == 1) Toh(1,A, B, C)
{ Disk 1 from A to B
printf("\n Move disk 1 from rod %c to rod %c", from_rod, to_rod);
Disk 2 from A to C
return;
} Toh(1, B, C, A)
towerOfHanoi(n-1, from_rod, aux_rod, to_rod); disk 1 from B to C
printf("\n Move disk %d from rod %c to rod %c", n, from_rod, to_rod);
towerOfHanoi(n-1, aux_rod, to_rod, from_rod);
}
Slides prepared by: Dr. Santhosh Kumar G , Department of CSE(Data Science), Dayananda Sagar University, Harohalli, Karnataka. 35
Queue
• A Queue is defined as a linear data structure that is open at both ends and the operations are performed in First
In First Out (FIFO) order.
• We define a queue to be a list in which all additions to the list are made at one end, and all deletions from the
list are made at the other end.
• The element which is first pushed into the order, the operation is first performed on that.
Slides prepared by: Dr. Santhosh Kumar G , Department of CSE(Data Science), Dayananda Sagar University, Harohalli, Karnataka. 36
Characteristics of Queue
Queue can handle multiple data.
We can access both ends.
They are fast and flexible.
Slides prepared by: Dr. Santhosh Kumar G , Department of CSE(Data Science), Dayananda Sagar University, Harohalli, Karnataka. 37
Queue Representation
• Like stacks, Queues can also be represented in an array: In this representation, the Queue is
implemented using the array. Variables used in this case are
Queue: the name of the array storing queue elements.
Front: the index where the first element is stored in the array representing the queue.
Rear: the index where the last element is stored in an array representing the queue.
Slides prepared by: Dr. Santhosh Kumar G , Department of CSE(Data Science), Dayananda Sagar University, Harohalli, Karnataka. 38
Basic Operations on Queue
• Some of the basic operations for Queue in Data Structure are:
enqueue() – Insertion of elements to the queue.
dequeue() – Removal of elements from the queue.
peek() or front()- Acquires the data element available at the front node of the queue without deleting it.
rear() – This operation returns the element at the rear end without removing it.
isFull() – Validates if the queue is full.
isEmpty() – Checks if the queue is empty.
size(): This operation returns the size of the queue i.e. the total number of elements it contains.
Slides prepared by: Dr. Santhosh Kumar G , Department of CSE(Data Science), Dayananda Sagar University, Harohalli, Karnataka. 39
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.
Slides prepared by: Dr. Santhosh Kumar G , Department of CSE(Data Science), Dayananda Sagar University, Harohalli, Karnataka. 40
Enqueue
Slides prepared by: Dr. Santhosh Kumar G , Department of CSE(Data Science), Dayananda Sagar University, Harohalli, Karnataka. 41
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.
Slides prepared by: Dr. Santhosh Kumar G , Department of CSE(Data Science), Dayananda Sagar University, Harohalli, Karnataka. 42
Dequeue
Slides prepared by: Dr. Santhosh Kumar G , Department of CSE(Data Science), Dayananda Sagar University, Harohalli, Karnataka. 43
Circular Queue
• A Circular Queue is an extended version of a normal queue where the last element of the queue is
connected to the first element of the queue forming a circle.
• The operations are performed based on FIFO (First In First Out) principle. It is also called ‘Ring Buffer’.
In a normal Queue, we can insert elements until queue becomes full. But once queue becomes
full, we cannot insert the next element even if there is a space in front of queue.
Slides prepared by: Dr. Santhosh Kumar G , Department of CSE(Data Science), Dayananda Sagar University, Harohalli, Karnataka. 44
Operations on Circular Queue
Front: Get the front item from the queue.
Rear: Get the last item from the queue.
enQueue(value) This function is used to insert an element into the circular queue. In a circular
queue, the new element is always inserted at the rear position.
Check whether the queue is full – [i.e., the rear end is in just before the front end in a circular
manner].
If it is full then display Queue is full.
If the queue is not full then, insert an element at the end of the queue.
deQueue() This function is used to delete an element from the circular queue. In a circular queue,
the element is always deleted from the front position.
Check whether the queue is Empty.
If it is empty then display Queue is empty.
Slides prepared by: Dr. Santhosh Kumar G , Department of CSE(Data Science), Dayananda Sagar University, Harohalli, Karnataka. 45
If the queue is not empty, then get the last element and remove it from the queue
Implement Circular Queue using Array
• Initialize an array queue of size n, where n is the maximum number of elements that the queue can hold.
• Initialize two variables front and rear to -1.
• Enqueue: To enqueue an element x into the queue, do the following:
Increment rear by 1.
If rear is equal to n, set rear to 0.
If front is -1, set front to 0.
Set queue[rear] to x.
• Dequeue: To dequeue an element from the queue, do the following:
Check if the queue is empty by checking if front is -1.
If it is, return an error message indicating that the queue is empty.
Set x to queue[front].
If front is equal to rear, set front and rear to -1.
Otherwise, increment front by 1 and if front is equal to n, set front to 0.
Return x. Slides prepared by: Dr. Santhosh Kumar G , Department of CSE(Data Science), Dayananda Sagar University, Harohalli, Karnataka. 46
Applications of circular queue
• Job Scheduling
• The jobs that are to be executed by the computer is scheduled to be executed one by one. There are many jobs
like keyboard press, mouse click etc. in the system. These jobs are brought in the main memory. These jobs
are assigned to the processor one by one which is organized using a queue.e.g. First In First Out and Round
Robin processor scheduling in queues.
Slides prepared by: Dr. Santhosh Kumar G , Department of CSE(Data Science), Dayananda Sagar University, Harohalli, Karnataka. 47
Maze Problem
• A Maze is given as N*N binary matrix of blocks where source block is the
upper left most block i.e., maze[0][0] and destination block is lower rightmost
block i.e., maze[N-1][N-1].
• A rat starts from source and has to reach the destination. The rat can move only
in two directions: forward and down.
• In the maze matrix, 0 means the block is a dead end and 1 means the block can
be used in the path from source to destination.
• Note that this is a simple version of the typical Maze problem.
• For example, a more complex version can be that the rat can move in 4
directions and a more complex version can be with a limited number of moves.
Slides prepared by: Dr. Santhosh Kumar G , Department of CSE(Data Science), Dayananda Sagar University, Harohalli, Karnataka. 48
Example Maze
• Gray blocks are dead ends (value = 0).
Following is a binary matrix representation of the above maze.
{1, 0, 0, 0}
{1, 1, 0, 1}
{0, 1, 0, 0}
{1, 1, 1, 1}
Following is a maze with highlighted solution path.
Slides prepared by: Dr. Santhosh Kumar G , Department of CSE(Data Science), Dayananda Sagar University, Harohalli, Karnataka. 49
Example Maze
Following is the solution matrix (output of program) for the above input matrix.
{1, 0, 0, 0}
{1, 1, 0, 0}
{0, 1, 0, 0}
{0, 1, 1, 1}
All entries in solution path are marked as 1.
Slides prepared by: Dr. Santhosh Kumar G , Department of CSE(Data Science), Dayananda Sagar University, Harohalli, Karnataka. 50