DATA STRUCTURE USING JAVA
LECTURE NOTES FOR UNIT - 2
UNIT -2
STACK - I
PREPARED BY:
MR. VISMAY SHAH
DATA STRUCTURES (017013292)
Semester – II
Chapter Name: STACK-1
Contents
2.1 Stack 2
a. Some key points related to stack 3
b. Working of Stack 3
2.2 Stack Operations 4
a. PUSH OPERATION 5
b. POP OPERATION 7
c. PEEP OPERATION 9
d. CHANGE OPERATION 10
2.3 JAVA Programs for Stack Operations 11
2.4 Application of Stack 19
a. Balancing of Symbols 19
b. String Reversal 19
c. Undo/ Redo 20
d. Recursion 20
e. DFS 20
f. Backtracking 20
g. Expression Conversion 20
h. Memory Management 21
2.5 Recursion 21
a. Difference Between Recursion and Iteration: - 22
2.6 Recursive Method 23
a. Memory allocation of Recursive method 24
2.7 Advantages and Disadvantages of Recursion 25
2.8 Tower of Hanoi Problem Using Recursion 26
a. JAVA PROGRAM FOR TOWER HANOI 27
2.9 String Reversal Using Stack 29
b. JAVA PROGRAM FOR STRING REVERSAL 29
2.10 Find Binary of The Given Decimal Number Using Stack 30
c. JAVA PROGRAM TO FIND BINARY FROM DECIMAL 30
P a g e 1 | 30
Prepared By: Mr. Vismay Shah
DATA STRUCTURES (017013292)
Semester – II
Chapter Name: STACK-1
2.1 Stack
P a g e 2 | 30
Prepared By: Mr. Vismay Shah
DATA STRUCTURES (017013292)
Semester – II
Chapter Name: STACK-1
a. Some key points related to stack
b. Working of Stack
P a g e 3 | 30
Prepared By: Mr. Vismay Shah
DATA STRUCTURES (017013292)
Semester – II
Chapter Name: STACK-1
2.2 Stack Operations
The following are some common operations implemented on the stack:
P a g e 4 | 30
Prepared By: Mr. Vismay Shah
DATA STRUCTURES (017013292)
Semester – II
Chapter Name: STACK-1
a. PUSH OPERATION
The steps involved in the PUSH operation is given below:
P a g e 5 | 30
Prepared By: Mr. Vismay Shah
DATA STRUCTURES (017013292)
Semester – II
Chapter Name: STACK-1
P a g e 6 | 30
Prepared By: Mr. Vismay Shah
DATA STRUCTURES (017013292)
Semester – II
Chapter Name: STACK-1
b. POP OPERATION
The steps involved in the POP operation is given below:
P a g e 7 | 30
Prepared By: Mr. Vismay Shah
DATA STRUCTURES (017013292)
Semester – II
Chapter Name: STACK-1
P a g e 8 | 30
Prepared By: Mr. Vismay Shah
DATA STRUCTURES (017013292)
Semester – II
Chapter Name: STACK-1
c. PEEP OPERATION
P a g e 9 | 30
Prepared By: Mr. Vismay Shah
DATA STRUCTURES (017013292)
Semester – II
Chapter Name: STACK-1
d. CHANGE OPERATION
P a g e 10 | 30
Prepared By: Mr. Vismay Shah
DATA STRUCTURES (017013292)
Semester – II
Chapter Name: STACK-1
2.3 JAVA Programs for Stack Operations
P a g e 11 | 30
Prepared By: Mr. Vismay Shah
DATA STRUCTURES (017013292)
Semester – II
Chapter Name: STACK-1
P a g e 12 | 30
Prepared By: Mr. Vismay Shah
DATA STRUCTURES (017013292)
Semester – II
Chapter Name: STACK-1
P a g e 13 | 30
Prepared By: Mr. Vismay Shah
DATA STRUCTURES (017013292)
Semester – II
Chapter Name: STACK-1
P a g e 14 | 30
Prepared By: Mr. Vismay Shah
DATA STRUCTURES (017013292)
Semester – II
Chapter Name: STACK-1
P a g e 15 | 30
Prepared By: Mr. Vismay Shah
DATA STRUCTURES (017013292)
Semester – II
Chapter Name: STACK-1
P a g e 16 | 30
Prepared By: Mr. Vismay Shah
DATA STRUCTURES (017013292)
Semester – II
Chapter Name: STACK-1
P a g e 17 | 30
Prepared By: Mr. Vismay Shah
DATA STRUCTURES (017013292)
Semester – II
Chapter Name: STACK-1
P a g e 18 | 30
Prepared By: Mr. Vismay Shah
DATA STRUCTURES (017013292)
Semester – II
Chapter Name: STACK-1
2.4 Application of Stack
The following are the applications of the stack:
[Link] of Symbols
b. String Reversal
P a g e 19 | 30
Prepared By: Mr. Vismay Shah
DATA STRUCTURES (017013292)
Semester – II
Chapter Name: STACK-1
c. Undo/ Redo
d. Recursion
e. DFS
f. Backtracking
g. Expression Conversion
P a g e 20 | 30
Prepared By: Mr. Vismay Shah
DATA STRUCTURES (017013292)
Semester – II
Chapter Name: STACK-1
h. Memory Management
2.5 Recursion
P a g e 21 | 30
Prepared By: Mr. Vismay Shah
DATA STRUCTURES (017013292)
Semester – II
Chapter Name: STACK-1
a. Difference Between Recursion and Iteration: -
Property Recursion Iteration
Definition Method calls itself. A set of instructions repeatedly
executed.
Application For methods. For loops.
Termination Through base case, where there When the termination condition for
will be no method call. the iterator ceases to be satisfied.
Usage Used when code size needs to Used when time complexity needs to
be small, and time complexity be balanced against an expanded code
is not an issue. size.
Code Size Smaller code size Larger Code Size.
Time Very high (generally Relatively lower time complexity
Complexity exponential) time complexity. (generally polynomial-
logarithmic).
In the following example, recursion is used to calculate the factorial of a number.
P a g e 22 | 30
Prepared By: Mr. Vismay Shah
DATA STRUCTURES (017013292)
Semester – II
Chapter Name: STACK-1
2.6 Recursive Method
Pseudocode for writing any recursive method is given below.
P a g e 23 | 30
Prepared By: Mr. Vismay Shah
DATA STRUCTURES (017013292)
Semester – II
Chapter Name: STACK-1
a. Memory allocation of Recursive method
Explanation:
Let us examine this recursive method for n = 4. First, all the stacks are maintained which prints the
corresponding value of n until n becomes 0, Once the termination condition is reached, the stacks get destroyed
one by one by returning 0 to its calling stack. Consider the following image for more information regarding
the stack trace for the recursive methods.
P a g e 24 | 30
Prepared By: Mr. Vismay Shah
DATA STRUCTURES (017013292)
Semester – II
Chapter Name: STACK-1
2.7 Advantages and Disadvantages of Recursion
P a g e 25 | 30
Prepared By: Mr. Vismay Shah
DATA STRUCTURES (017013292)
Semester – II
Chapter Name: STACK-1
2.8 Tower of Hanoi Problem Using Recursion
Tower of Hanoi is a mathematical puzzle where we have three rods and n disks. The objective
of the puzzle is to move the entire stack to another rod, obeying the following simple rules:
1. Only one disk can be moved at a time.
2. 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.
3. No disk may be placed on top of a smaller disk.
P a g e 26 | 30
Prepared By: Mr. Vismay Shah
DATA STRUCTURES (017013292)
Semester – II
Chapter Name: STACK-1
a. JAVA PROGRAM FOR TOWER HANOI
P a g e 27 | 30
Prepared By: Mr. Vismay Shah
DATA STRUCTURES (017013292)
Semester – II
Chapter Name: STACK-1
Output:
Move disk 1 from rod A to rod B
Move disk 2 from rod A to rod C
Move disk 1 from rod B to rod C
Move disk 3 from rod A to rod B
Move disk 1 from rod C to rod A
Move disk 2 from rod C to rod B
Move disk 1 from rod A to rod B
Move disk 4 from rod A to rod C
Move disk 1 from rod B to rod C
Move disk 2 from rod B to rod A
Move disk 1 from rod C to rod A
Move disk 3 from rod B to rod C
Move disk 1 from rod A to rod B
Move disk 2 from rod A to rod C
Move disk 1 from rod B to rod C
P a g e 28 | 30
Prepared By: Mr. Vismay Shah
DATA STRUCTURES (017013292)
Semester – II
Chapter Name: STACK-1
2.9 String Reversal Using Stack
b. JAVA PROGRAM FOR STRING REVERSAL
P a g e 29 | 30
Prepared By: Mr. Vismay Shah
DATA STRUCTURES (017013292)
Semester – II
Chapter Name: STACK-1
2.10 Find Binary of The Given Decimal Number Using Stack
c. JAVA PROGRAM TO FIND BINARY FROM DECIMAL
P a g e 30 | 30
Prepared By: Mr. Vismay Shah