DS and Algorithms in Java

In this article, we will write a simple program to reverse a Stack using recursion. we are not using loop constructs like a while, for etc, and we only use the following ADT functions on Stack:
• isEmpty(S)
• push(S)
• pop(S)
Let's write generic methods so that we can reverse any data type like String, Integer, Double etc.
In this program, we will demonstrate how to reverse Integer Stack and String Stack.
Please refer the comments in below program are self-descriptive.
import java.util.Iterator;
import java.util.Stack;

/**
* Generic methods to reverse stack
* @author Ramesh Fadatare
*
*/
public class StackReversal {

public static <T> void reverseStack(Stack<T> stack) {
if (stack.isEmpty()) {
return;
}
// Remove bottom element from stack
T bottom = popBottom(stack);

// Reverse everything else in stack
reverseStack(stack);

// Add original bottom element to top of stack
stack.push(bottom);
}
private static <T> T popBottom(Stack<T> stack) {
T top = stack.pop();
if (stack.isEmpty()) {
// If we removed the last element, return it
} else {
// We didn't remove the last element, so remove the last element from what remains
T bottom = popBottom(stack);
// Since the element we removed in this function call isn't the bottom element,
// add it back onto the top of the stack where it came from
stack.push(top);
return bottom;
}
}

private static <T> void printStack(Stack<T> stack){
Iterator<T> iterator = stack.iterator();
while (iterator.hasNext()) {
T t = (T) iterator.next();
System.out.println(t);
}
}
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>();
stack.push(10);
stack.push(20);
stack.push(30);
stack.push(40);

System.out.println("Stack elements before reverse");
printStack(stack);
StackReversal reversal = new StackReversal();
reversal.reverseStack(stack);

System.out.println("Stack after before reverse");
printStack(stack);

Stack<String> stack1 = new Stack<>();
stack1.push("a");
stack1.push("b");
stack1.push("c");
stack1.push("d");

System.out.println("Stack elements before reverse");
printStack(stack1);
reversal.reverseStack(stack1);

System.out.println("Stack after before reverse");
printStack(stack1);
}
}
Output:
Stack elements before reverse
10
20
30
40
Stack after before reverse
40
30
20
10
Stack elements before reverse
a
b
c
d
Stack after before reverse
d
c
b
a