Reverse a stack in place.
Input:
3 4 5 6 7
Output:
Original stack:
3 -> 4 -> 5 -> 6 -> 7 -> Null
Reversed stack:
7 -> 6 -> 5 -> 4 -> 3 -> Null
Input:
3 4 5 6 7
Output:
Original stack:
3 -> 4 -> 5 -> 6 -> 7 -> Null
Reversed stack:
7 -> 6 -> 5 -> 4 -> 3 -> Null
The complexity here goes to n(n + 1) / 2 which is n^2. Why don't just skip the recursion and make it easier by using just stacks (after all the recursion is just the same thing). Here is a O(n) time complexity and O(1) space (since filling one stack on one side, clears the other one on the other) Java code:
ReplyDeletepublic void reverseStack(Stack s) {
Stack reversed = new Stack();
Stack nonReversed = new Stack();
//reverse the stack
while(!s.isEmpty())
reversed.push(s.pop());
//move to the nonReversed order
while(!reversed.isEmpty())
nonReversed.push(reversed.pop());
// and reverse the result stack
while(!nonReversed.isEmpty())
s.push(nonReversed.pop());
}