CareerCup

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

//from stackoverflow, but there is temp storage is involved in appendStack

public static void revertStack(Stack<Integer> s) {
    if (s.isEmpty()) {
        return;
    } else {
        Integer a = s.pop();
        revertStack(s);
        appendStack(s, a);
    }
}

public static void appendStack(Stack<Integer> s, Integer a) {
    if (s.isEmpty()) {
        s.push(a);
        return;
    } else {
        Integer o = s.pop();
        appendStack(s, a);
        s.push(o);
    }
}

Using recursion involves using extra space.

With O(n) extra space it is trivial.

Without extra space, you need recursion to hold values. You can ask the interviewer that if I have source code of given stack, if I have the information on how the stack is implemented, then reverse that internal data structure of stack for example, array and linked lists can be reversed using constant extra space.

First, think about how to add a data to the bottom of the a stack, which requirement a recursive function. If you can sort out the 1st question, then it is straight forward to use another recursive function to revert a stack.

Using pointers

pt1 = First;
pt2 = Last;

pt1 = pt1+pt2;
pt2= pt1- pt2;
pt1= pt1- pt2;

I think this would be implementation depended...
if it is normal array then putting two pointer one from end and one from start and swapping them would reverse the stack...
for link list reverse would be fine I guess....

int size = stack.size() - 1;
		
		for (int i = 0 ; i < stack.size() / 2 ; i++) {
			String temp = (String) stack.get(i);
			stack.set(i, stack.get(size));
			stack.set(size, temp);
			size--;
		}

we use recursion ; i.e. System Stack called SS
and our stack being S;
Algo: 1> first pop all the element of stack S and push it into SS s.t. data is the top of the data of SS
2> now We Pop element of SS ( done by automatically when recursion back up) and push element in S s.t. if it being first push then done it otherwise again pop Element of S until empty and push into SS then insert that element and again push element of SS to S
void ReverseStack ( struct Stack *S ) { int data ;
if ( ! ISEmpty(S) ) return ;
data = POP(S) ; // collecting top most data of SS
ReverseStack(S) ; // popping from S and pushing in SS
InsertInStack(S,data); // this will insert into stack
}
void InsertInStack(struct Stack *S, int data)
{ if ( ! ISEmpyt(S) ) { PUSH(S,data); return ; } // if it being first element
int temp;
temp = POP(S) ; InsertInStack(S,data) ; // pop all element of the Stack and push into SS and then again push PUSH(S,temp) ; //in S

Hi,
I am commenting on a very old thread. Not sure if iam missing something in the question, but using a stack in a single recursive loop can reverse the stack elements. Stack ADT itself can be considered as first level recursion and the second recursion that we do in code together can be treated or assumed as double recursion.
Here is my sample code that worked in unit test.

@Test
    public void reverseStack() {
        Stack<String> stack = new Stack<String>();
        stack.push("a");
        stack.push("b");
        stack.push("c");
        reverseStackFunc(stack);
        for (String s : stack) {
            System.out.println(s);
        }
    }

    private void reverseStackFunc(Stack<String> stack) {
        if (stack.empty()) {
            return;
        }
        else {
            String s = stack.pop();
            reverseStackFunc(stack);
            stack.push(s);
        }
    }

Thanks
sri

public class ReversingStack<T>
where T:IComparable<T>
{
public Stack<T> Reverse(Stack<T> stack)
{
if(stack.Count>0)
{
/* Hold all items in Function Call Stack until we reach end of
the stack */
T temp = stack.Pop();
stack= Reverse(stack);

/* Insert all the items (held in Function Call Stack) one by one
from the bottom to top. Every item is inserted at the bottom */
stack = InsertAtBottom(stack, temp);
}
return stack;
}

private Stack<T> InsertAtBottom(Stack<T> stack, T item)
{
if (stack.Count == 0)
{
stack.Push(item);
}
else
{
/* Hold all items in Function Call Stack until we reach end of
the stack. When the stack becomes empty, the isEmpty(*top_ref)
becomes true, the above if part is executed and the item is
inserted at the bottom */
T temp = stack.Pop();
stack = InsertAtBottom(stack, item);

/* Once the item is inserted at the bottom, push all the
items held in Function Call Stack */
stack.Push(temp);
}

return stack;
}
}

import java.util.Stack;

class GFG {
	public static void main (String[] args) {
		  Stack<Integer> s = new Stack();
        s.push(4);
        s.push(3);
        s.push(2);
        s.push(1);
         System.out.println("Original stack");
        System.out.println(s);
        reverse(s);
         System.out.println("Reversed stack");
        System.out.println(s);
	}
	
	public static void reverse(Stack<Integer> s) {
        if (s.isEmpty()) {
            return;
        }
        int pop = s.pop();
        reverse(s);

        insert(s, pop);
    }

    public static void insert(Stack<Integer> s, int popped) {
        if (s.isEmpty()) {
            s.push(popped);
        } else {
            int element = s.pop();
            insert(s, popped);
            s.push(element);
        }
    }
}