5

How can I Reverse stack without using any (extra) data structure ? Any suggestions or Pseudo code could be helpful . I trying and couldn't find any viable solution . Problem here is I don-no the size of stack also . If i know that I could at-least proceed on creating something , Thanks in advance .

5
  • Since the stack itself is a data structure, are you allowed to use that?
    – corsiKa
    Nov 21, 2013 at 16:01
  • 3
    What can you do is pop all element of the current stack and push them to another. I'm not if that would suit you though.
    – sve
    Nov 21, 2013 at 16:02
  • 1
    How's the stack implemented? If it's your own implementation with a linked list, just reverse direction of pointers.
    – chill
    Nov 21, 2013 at 16:16
  • 1
    @chill, better yet - use a double ended queue
    – Leeor
    Nov 21, 2013 at 16:25
  • @Leeor nice one. Recursion does use a stack which is inbuilt. Is this a stupid interview question (Sometimes they ask such, why would anyone do with recursion,it is so expensive) Nov 21, 2013 at 16:43

3 Answers 3

6

This can be done with double recursion , as follows: .

void insert_at_bottom(node **stack, int data)
{
     if( isempty(*stack) ){
          push(stack,data);
          return;
     }
     int temp=pop(stack);
     insert_at_bottom(stack,data);
     push(stack,temp);
}  


void rev_stack(node **stack)
{
     if( isempty(*stack) ) return;
     int temp = pop(stack);
     rev_stack(stack);
     insert_at_bottom(stack,temp);
}
3

You can easily do this using recursion. Then your maximum allowed stack size would be bound by maximum recursion depth. Some code:

public void reverse(Stack st) { 
    int m = (int)st.Pop(); 
    if (st.Count != 1) {
        reverse(st); 
    }
    Push(st , m); 
  } 

public void Push(Stack st , int a) { 
   int m = (int)st.Pop(); 
   if (st.Count != 0) {
       Push(st , a); 
   }
   else {
       st.Push(a); 
       st.Push(m); 
   }
}
0

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.

Only works for Integers

Let's say Stack = [1,2,-3,4] with 1 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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.