Make delicious recipes!

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, 







Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal