Reverse stack without using any data structure

Question

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 .

Answer 1

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);
}

Answer 2

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); 
   }
}