This content originally appeared on DEV Community and was authored by Garvit Khamesra
Question:
Given a stack, sort it using recursion. Use of any loop constructs like while, for..etc is not allowed.
Solution:
This question follows the same algorithm as Sort an Array using recursion. So I would suggest you go through the post and try it once.
I have added the code and the call order because once go through it you’ll see the code is similar.
package stack.queue;
import java.util.Stack;
public class SortStackWithRecursion {
static Stack stack;
public static void sort() {
if (!stack.isEmpty()) {
int temp = stack.pop();
sort();
insert(temp);
}
}
private static void insert(int value) {
if (stack.isEmpty() || stack.peek() < value) {
stack.push(value);
} else {
int temp = stack.pop();
insert(value);
stack.push(temp);
}
}
public static void main(String[] args) {
stack = new Stack<>();
stack.add(12112);
stack.add(21);
stack.add(300);
stack.add(41);
stack.add(52);
for (int i : stack) {
System.out.print(i + " ,");
}
System.out.println("\n>>>");
sort();
System.out.println("<<<");
for (int i : stack) {
System.out.print(i + " ,");
}
}
}
Sort [12112, 21, 300, 41, 52] Stack Size: 5 Sort [12112, 21, 300, 41] Stack Size: 4 Sort [12112, 21, 300] Stack Size: 3 Sort [12112, 21] Stack Size: 2 Sort [12112] Stack Size: 1 Insert [] Stack Size: 0 Inserting Value: 12112 Insert [12112] Stack Size: 1 Insert [] Stack Size: 0 Inserting Value: 21 Inserting Value: 12112 Insert [21, 12112] Stack Size: 2 Insert [21] Stack Size: 1 Inserting Value: 300 Inserting Value: 12112 Insert [21, 300, 12112] Stack Size: 3 Insert [21, 300] Stack Size: 2 Insert [21] Stack Size: 1 Inserting Value: 41 Inserting Value: 300 Inserting Value: 12112 Insert [21, 41, 300, 12112] Stack Size: 4 Insert [21, 41, 300] Stack Size: 3 Insert [21, 41] Stack Size: 2 Inserting Value: 52 Inserting Value: 300 Inserting Value: 12112
#HappyCoding
This content originally appeared on DEV Community and was authored by Garvit Khamesra