Data Structuresand Algorithms Good OldJava AdvancedInterview Topics Cloud andDatabases Web Designand Development Must-knowTools Good ToKnow

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: