CODEWITHSUNDEEP
javaalgorithmdata-structurescollectionsstack
Bharat
Bharat

Reputation: 1082

Reversing stack in O(n) without extraspace is not happening

I'm trying to reverse a stack using recursion :

I'm able to print the elements of the stack in reverse order. But if I try to push the reverse elements it is not working.

Let the stack be [0,1,2,3,4]. 4 is top.

This is what I've tried:

private static void reverseStack(Stack<Integer> stack) {
        if (!stack.isEmpty()){
            int n=stack.pop();
            reverseStack(stack);
            System.out.println(n);
        }
    }

With this I'm getting the correct output.

Output is :

0
1
2
3
4

This is what I've expected.

If I try to push these elements back to stack I'm getting the same stack back without getting reversed :

This is the code used for reversing :

private static void reverseStack(Stack<Integer> stack) {
        if (!stack.isEmpty()){
            int n=stack.pop();
            reverseStack(stack);
            System.out.println(n);
            stack.push(n);
        }
    }

This is the step wise stack obtained from this code :

private static void reverseStack(Stack<Integer> stack) {
        if (!stack.isEmpty()){
            int n=stack.pop();
            System.out.println(stack);
            reverseStack(stack);
            System.out.println(n);
            stack.push(n);
        }
    }

Output

We can clearly see that the output stack is same as input stack but still elements are printed in reverse order. Where am I doing wrong ?

Upvotes: 5

Views: 2350

Answers (7)

jala
jala

Reputation: 1

This implementation is generic for Stack,List,Vector

For Stack :

private static void reverseStack(Stack<Integer> stack) {
    for (int i = 0, j = stack.size() - 1; i < j; i++) {
        stack.add(i, stack.pop());
    }
}

For List :

private static void reverseList(List<Integer> list) {
    for (int i = 0, j = list.size() - 1; i < j; i++) {
        list.add(i, list.remove(j));
    }
}

Upvotes: -1

aventurin
aventurin

Reputation: 2203

In Java normally one would not use recursion to reverse a list-like data structure that is designed to support a large number of elements.

Since Java does not use tail call optimizations such algorithms may produce large stacks, or even stack overflows. And they probably would not be considered "without extra space" either.

You could simply reverse the stack in a loop with O(n) time and constant space complexity by swapping elements pairwise, i.e. first with last, second with second last, and so on. The following code which is adopted from JDK classes shows this approach.

private static void reverseStack(Stack<Integer> stack) {
    for (int i = 0, mid = stack.size() >> 1, j = stack.size() - 1; i < mid; i++, j--)
        stack.set(i, stack.set(j, stack.get(i)));
}

Upvotes: 0

skY
skY

Reputation: 111

Here's a different approach. I"m trying to use fixed set of variables (5 - max,A,A1,B,B1) and re-utilizing these variables, re-populating stack in reverse order.

No-Recursion. Recursive Solutions for this means O(n) extra space.

Only works for Integers

Let's say Stack = [1,2,-3,4] with 4 on top.

max = 5

A = ((((((1*5)+2)*5)+3)*5)4)*5

A1 = (((((((0+5)*5)+5)*5)+6)*5)+5)*5

With the help of A and A1 you can re-populate the stack but in the same order so calculating B and B1 which are in reverse order.

A1 & B1 are to remember negative integers.

Here, + max is for positive and + (max + 1) to remember negative integers. 

import java.util.Stack;
//Not ideal solution. This is only because no other data structure can be used

/*
 * 1. Find Max. Any number > max can be used for max
 * 2. Find A and A1
 * 3. Find B and B1
 * 4. Fill the Stack using B and B'
 * O( 4n ) = O( n )
 */

class Stack_Reversal_Using_Recursion { 

static Stack<Integer> stack = new Stack<>(); 

public static void main(String[] args) {

    stack.push(1);
    stack.push(8);
    stack.push(-3);
    stack.push(0);
    stack.push(4);
    System.out.println(stack);  

    better_Solution();

    System.out.println("Using mathematical approch");
    System.out.println(stack);

}
private static void better_Solution() {

    int size = stack.size();

    //Finding Max
    int max = 0;
    for(int item : stack){
        if( max < Math.abs(item) )
            max = Math.abs(item);
    }
    max = max + 1;

    //Finding A and A1
    int A = 0;
    int A1 = 0;

    while( stack.size() > 0 )
    {
        int x = stack.pop();
        A += Math.abs(x);
        A *= max;

        if( x < 0 )
            A1 += (max+1);
        else
            A1 += max;
        A1 *= max;
    }
    //A and A' hold single sum total value from which using max we can find out entire stack but in same order so we find out B and B1

    int B = 0;
    int B1 = 0;

    for( int i = 0; i < size; i++)
    {
        A = A / max;
        A1 = A1/ max;

        int A_mdl = A % max;
        A -= A_mdl;

        int A1_mdl = A1 % max;
        if( A1_mdl == 0 )
            A1_mdl = max;
        else
            A1_mdl = max + 1;
        A1 -= A1_mdl;

        B += A_mdl;
        B *= max;

        B1 += A1_mdl;
        B1 *= max;

    }

    //Now that we have B and B1 in desired order let's re-populate the Stack
    for( int i = 0; i < size; i++)
    {
        B = B / max;
        B1 = B1/ max;

        int B_mdl = B % max;
        B -= B_mdl;

        int B1_mdl = B1 % max;
        if( B1_mdl != 0 )
            B_mdl = -B_mdl;
        if( B1_mdl ==0 )
            B1 -= max;
        else
            B1 -= (max+1);

        stack.push( B_mdl );

    }

}

}

As stated earlier, This approach is only for Integers and one can always debate what if numbers are vary large! In that case As and Bs can be Big Integers.

Upvotes: 1

nagendra547
nagendra547

Reputation: 6312

If you are doing recursive call to reverse the stack, then you are using extra space. (When you pop the element and store it to add it later).

However if you use 2nd stack approach mentioned by @Scott and @Berkley then it's not taking extra space. So this will be right answer to your question.

while(!stack.isEmpty()) {
 reversedStack.push(stack.pop());            
}

Upvotes: 3

Berkley Lamb
Berkley Lamb

Reputation: 293

When you hit the base case for the call, you are putting that element back onto the stack. That function is then completed, then goes back up to the element above it, and adds that back.

First call ([0,1,2,3,4])
int n = 4
Second call ([0,1,2,3])
int n = 3
Third call ([0,1,2])
int n = 2
Fourth call ([0,1])
int n = 1
Fifth call ([0])
int n = 0
Sixth call ([])
empty is reached, return
add 0 to stack then return ([0])
add 1 to stack then return ([0,1])
add 2 to stack then return ([0,1,2])
add 3 to stack then return ([0,1,2,3])
add 4 to stack then return ([0,1,2,3,4])

This problem could be resolved in a simpler fashion by using a loop and two different stacks.

while(!stack.isEmpty()) {
 int n = stack.pop();
 stack2.push(n);            
}

Upvotes: 2

TruckDriver
TruckDriver

Reputation: 1456

You have problem in visualizing the recursion, the sysout's (System.out.println) will not be executed till the exit criteria of recursion is fulfilled i.e . when stack is empty. At this point the recursion will wind up and all the elements will be printed in that order i.e. 0,1,2,3,4 And only then you are pushing the elements in that order , so that stack becomes [0,1,2,3,4] See attached pic, pardon my handwriting :) https://i.sstatic.net/Xc7jN.jpgenter image description here

Upvotes: 2

Scott Hunter
Scott Hunter

Reputation: 49813

You have to build a new stack, so that the first one popped from the old stack is the first one pushed onto the new one. There won't be "extra space", as every original item will be in one of the 2 stacks. I'd do it using a helper function that knows about the stack you are building.

Upvotes: 3

Related Questions