Is there way to reverse the last half of the elements from the bottom of the stack (using recursion)?

Question

The code which helps reverse the entire stack is however not able to get it to reverse half the elements -

static void reverseSecondHalf(Stack<Integer> stack) {
    // Write your code here
    
    if(stack.size() > 0)
    {
    
        int x = stack.peek();
        stack.pop();

        reverseSecondHalf(stack);
        insert_at_bottom(x,stack);}
    System.out.print(stack);
}
static void insert_at_bottom(int x, Stack<Integer> stack) {

    if(stack.isEmpty()) {
        stack.push(x);
    }
    else {
        int y = stack.peek();
        stack.pop();
        insert_at_bottom(x,stack);
        stack.push(y);
    }

}

Answer 1

1. Move the first half of the stack into a temporary stack with push(pop()).
2. Push(pop()) the second half of the stack into a result stack.
3. Move the temporary stack into the result stack with push(pop()).

For example:

public static Stack<Integer> reverseLastHalf(Stack<Integer> source){
    Stack<Integer> temp = new Stack<>();
    Stack<Integer> result = new Stack<>();
    int size = source.size();

    for(int i = 0; i < size; i++){
        if(i < size / 2)
            temp.push(source.pop());
        else
            result.push(source.pop());
    }
    while(!temp.isEmpty()) result.push(temp.pop());
    return result;
}

Maybe this is a useful solution for you.

Answer 2

this should be the shortest recursive solution

public static void reverseLastHalf(int half, Stack<Integer> stack) {
  int tos = stack.pop();
  if(stack.size() > 0)
    reverseLastHalf(half, stack);
  if(stack.size() < half)
    insert_at_bottom(tos, stack);
  else
    stack.add(tos);
}

call it like this

reverseLastHalf(stack.size() / 2, stack);

(Typically, stack-oriented languages like 7th have a function of rolling an element up from the bottom of the stack. The opposite way is unusual.)

Answer 3

static void reverseSecondHalf(Stack<Integer> stack) {
    Stack<Integer> temp = new Stack<>();
    Stack<Integer> result = new Stack<>();
    int size = stack.size();
    for (int i = 0; i < size; i++) {
        if (i < size / 2)
            temp.push(stack.pop());
        else
            result.push(stack.get(size-(i+1)));
    }
    while (!temp.isEmpty())
        result.push(temp.pop());
    for(int i=0; i<size/2;i++) {
        stack.push(result.pop());
    }
    System.out.println(stack);
}

Answer 4

You can try this in Java-

    static void reverseSecondHalf(Stack<Integer> stack, int n) {
        // Write your code here
        if (stack.size()>(n/2+1) ){
            int top= stack.pop();
            reverseSecondHalf(stack,n);
            stack.add(n/2+1,top);
        }


    }

call in main like:

reverseSecondHalf(stack, stack.size());