package org.wesome.dsalgo;
import java.util.Stack;
public class SortStack {
public static Stack<Integer> sortStack(Stack<Integer> unsortedStack) {
System.out.println("unsorted stack is = " + unsortedStack);
Stack<Integer> sortedStack = new Stack<>();
// we will return sortedStack so loop while unsortedStack is not empty.
while (!unsortedStack.isEmpty()) {
// pop out the first element from main stack
int unsortedStackTop = unsortedStack.pop();
System.out.println("removing unsortedStackTop is = " + unsortedStackTop + " unsortedStackTop is = " + unsortedStack);
// if temporary stack has data and unsortedStack top is greater than sortedStack top
while (!sortedStack.isEmpty() && sortedStack.peek() > unsortedStackTop) {
// pop from temporary stack and push it to the unsortedStack stack
System.out.println("sortedStackTop = " + sortedStack.peek() + " greater then unsortedStackTop = " + unsortedStackTop);
System.out.println("so take all the elements of sortedStack which are greater then " + unsortedStackTop + " and put in unSortedStack, then put " + unsortedStackTop + " at the top of sortedStack");
System.out.println("removing sortedStack top = " + sortedStack.peek() + " and putting back into unsortedStack");
unsortedStack.push(sortedStack.pop());
System.out.println("now unsortedStack is = " + unsortedStack);
}
System.out.println("pushing unsortedStackTop top = " + unsortedStackTop + " into sortedStack");
sortedStack.push(unsortedStackTop);
System.out.println("now sortedStack is = " + sortedStack);
System.out.println("now unsortedStack is = " + unsortedStack + "\n");
}
System.out.print("sortedStack is = " + sortedStack);
return sortedStack;
}
}
package org.wesome.dsalgo;
import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;
import java.util.Stack;
import static org.wesome.dsalgo.SortStack.sortStack;
public class SortStackTest {
@Test
void SortStack() {
Stack<Integer> stack = new Stack<>();
stack.add(5);
stack.add(3);
stack.add(4);
stack.add(2);
stack.add(0);
stack.add(1);
Stack<Integer> sortedStack = sortStack(stack);
Stack<Integer> assertStack = new Stack<>();
assertStack.add(0);
assertStack.add(1);
assertStack.add(2);
assertStack.add(3);
assertStack.add(4);
assertStack.add(5);
Assertions.assertEquals(assertStack, sortedStack);
}
}
plugins {
id 'org.springframework.boot' version '2.5.4'
id 'io.spring.dependency-management' version '1.0.11.RELEASE'
id 'java'
}
group = 'org.wesome'
version = '0.0.1-SNAPSHOT'
sourceCompatibility = JavaVersion.VERSION_1_8
configurations {
compileOnly {
extendsFrom annotationProcessor
}
}
repositories {
mavenCentral()
}
dependencies {
compileOnly 'org.projectlombok:lombok'
annotationProcessor 'org.projectlombok:lombok'
testImplementation 'org.springframework.boot:spring-boot-starter-test'
}
test {
useJUnitPlatform()
}