Reverse a stack in place using only push,pop,size operators
Problem: Reverse a stack in place using only push, pop and size operators.
Auxiliary storage is not allowed. Recursion is allowed.
Code:
import java.util.Stack;
public class InPlaceStackReverse
{
static void reverseStack(Stack s)
{
printStack(s, "reverse1");
Object curr = s.pop();
if (s.size() != 1)
reverseStack (s);
placeCurrAtBottomOfStack (s, curr);
printStack(s, "place " + curr + " AtBottom");
}
static void placeCurrAtBottomOfStack(Stack s, Object curr)
{
Object top = s.pop();
if (s.size() == 0)
s.push(curr);
else
placeCurrAtBottomOfStack(s, curr);
s.push(top);
}
// main function to test the above
public static void main (String args[])
{
Stack s = new Stack ();
s.push(1); s.push(2); s.push(3);
s.push(4); s.push(5); s.push(6);
reverseStack (s);
}
// function to print a stack with some message.
static void printStack(Stack s, String msg)
{
System.out.print("\n" + msg + " = ");
for (int i=s.size()-1; i>=0; i--)
System.out.print(s.get(i)+", ");
}
}
Sample Execution:
reverse1 = 6, 5, 4, 3, 2, 1,
reverse1 = 5, 4, 3, 2, 1,
reverse1 = 4, 3, 2, 1,
reverse1 = 3, 2, 1,
reverse1 = 2, 1,
place 2 AtBottom = 1, 2,
place 3 AtBottom = 1, 2, 3,
place 4 AtBottom = 1, 2, 3, 4,
place 5 AtBottom = 1, 2, 3, 4, 5,
place 6 AtBottom = 1, 2, 3, 4, 5, 6,
|