Friday, 15 November 2013

Program to reverse a stack "in place" using recursion?

Code :


import java.util.Stack;
/**
 * Created with IntelliJ IDEA.
 * User: aniket
 * Date: 11/15/13
 * Time: 3:30 PM
 */

public class InPlaceStackReversal {
    public static void reverse(Stack<String> stack){
        String element = stack.pop();
        if(stack.size() != 1) {
            reverse(stack);
        }
        pushToBottomOfStack(element,stack);
    }


    private static void pushToBottomOfStack(String data, Stack<String> stack){
        String element = stack.pop();
        if(stack.size() != 0){
            pushToBottomOfStack(data, stack);
        }
        else {
            stack.push(data);
        }
        stack.push(element);
    }

    public static void main(String args[]) {
        Stack<String> myStack = new Stack<String>();
        myStack.push("A");
        myStack.push("B");
        myStack.push("C");
        myStack.push("D");
        System.out.println("Original Stack : " + myStack);
        InPlaceStackReversal.reverse(myStack);
        System.out.println("Revered Stack : " + myStack);

    }
}

Output :


Original Stack : [A, B, C, D]
Revered Stack : [D, C, B, A]

1 comment:

  1. Your code won't work for some inputs.
    ex : try reversing a stack having one element, you will get an exception.

    ReplyDelete

t> UA-39527780-1 back to top