Stacks Stack LIFO(Last In First Out) or FILO(First In Last Out) order. In the below program, Stack is reversed using recursion. This algorithm will not use any additional or extra space but will use auxiliary space for recursion calls.
package org.wesome.dsalgo;
import java.util.Stack;
public class ReverseStack {
// first remove all the integers from stack, then start inserting in reverse order.
// with every recursion, save the top in temp variable.
public static Stack<Integer> reverseStack(Stack<Integer> stack) {
if (stack.empty()) {
return stack;
}
int temp = stack.pop();
reverseStack(stack);
insertAtTheBottom(stack, temp);
return stack;
}
public static void insertAtTheBottom(Stack<Integer> stack, int push) {
if (stack.empty()) {
stack.push(push);
return;
}
// with each recursion, save top integer into temp, when stack become empty then first insert push, then all top back.
int top = stack.pop();
insertAtTheBottom(stack, push);
stack.push(top);
}
}
package org.wesome.dsalgo;
import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;
import java.util.Stack;
import java.util.stream.IntStream;
import static org.wesome.dsalgo.ReverseStack.reverseStack;
public class ReverseStackTest {
@Test
void reverseStackTest1() {
Stack<Integer> stack = new Stack<>();
IntStream.rangeClosed(1, 5).forEach(stack::push);
Stack<Integer> reverseStack = reverseStack(stack);
Stack<Integer> assertStack = new Stack<>();
for (int i = 5; i >= 1; i--) {
assertStack.push(i);
}
Assertions.assertEquals(assertStack, reverseStack);
}
@Test
void reverseStackTest2() {
Stack<Integer> stack = new Stack<>();
IntStream.rangeClosed(1, 10).filter(i -> i % 2 == 0).forEach(stack::push);
Stack<Integer> reverseStack = reverseStack(stack);
Stack<Integer> assertStack = new Stack<>();
for (int i = 10; i >= 1; i -= 2) {
assertStack.push(i);
}
Assertions.assertEquals(assertStack, reverseStack);
}
@Test
void reverseStackTest3() {
Stack<Integer> stack = new Stack<>();
IntStream.rangeClosed(1, 10).filter(i -> i % 2 != 0).forEach(stack::push);
Stack<Integer> reverseStack = reverseStack(stack);
Stack<Integer> assertStack = new Stack<>();
for (int i = 9; i >= 1; i -= 2) {
assertStack.push(i);
}
Assertions.assertEquals(assertStack, reverseStack);
}
}
plugins {
id 'java'
}
group = 'org.wesome'
version = '0.0.1-SNAPSHOT'
sourceCompatibility = JavaVersion.VERSION_1_8
configurations {
compileOnly {
extendsFrom annotationProcessor
}
}
repositories {
mavenCentral()
}
dependencies {
testImplementation 'org.junit.jupiter:junit-jupiter:5.6.2'
}
test {
useJUnitPlatform()
}