CODEWITHSUNDEEP
javarecursion
jian
jian

Reputation: 4824

Understand stack recursive in java

The code works well. It's just i don't get it. Having difficult in the recursive part. In this part: char a = st.peek();st.pop(); insert_at_bottom(x); st.push(a); my idea is that first it will execute char a = st.peek();st.pop() all the time until a threshold. then it will execute st.push(a); one time. So the a will only be assigned value once. Obviously that is not true.

The difficult part for me is in the insert_at_bottom method what does insert_at_bottom(x) do? in reverse method what does reverse(), insert_at_bottom(x)do?

import java.util.Stack;
class Test {
    static Stack<Character> st = new Stack<>();
    static void insert_at_bottom(char x)
    {
        if(st.isEmpty()) st.push(x);
        else
        {char a = st.peek();
            st.pop();
            insert_at_bottom(x);
            st.push(a);
        }
    }
    
    static void reverse()
    {
        if(st.size() > 0)
        {           
            char x = st.peek();
            st.pop();
            reverse();
            insert_at_bottom(x);
        }
    }
    public static void main(String[] args)
    {   st.push('1'); st.push('2'); st.push('3'); st.push('4');     
        System.out.println("Original Stack");
        System.out.println(st);
        reverse();
        System.out.println("Reversed Stack");
        System.out.println(st); }}

Upvotes: 0

Views: 224

Answers (2)

Mark Saving
Mark Saving

Reputation: 1787

To begin with, we will use [] notation for stacks. An empty stack will be denoted []. When we push or pop an element, we will do so on the left side. For example, if we start with [1, 2, 3] and pop, we will be left with [2, 3] and the pop will return 1. And if we start with [1, 2, 3] and push 0, we will be left with [0, 1, 2, 3].

insert_at_bottom's sole purpose is enabling us to push append an element to the right side of the stack, rather than the left side of the stack.

So how do we insert something (let's say we want to insert x) on the right side of the stack rather than the left side? We consider two different cases:

  1. The stack is empty: that is, st = [].

In this case, pushing to the right and pushing to the left are the same thing, so we just call st.push(x) and now have st = [x].

  1. The stack is non-empty: for example, the stack is ['1', '2', '3'].

First, we pop '1' off the stack. Now we have st = ['2', '3'].
Then, we push x onto the right side of st by making a recursive call. This gives us st = ['2', '3', x].
Finally, we push '1' back onto the stack. This gives us st = ['1', '2', '3', x]. As you can see, we have successfully inserted x at the rightmost position of st.

This is how insert_at_bottom works.

Now how does reverse work? We again consider two distinct cases.

  1. The stack is empty; that is, st = [].

In this case, we don't need to do anything to reverse st.

  1. The stack is non-empty; we will take st = ['1', '2', '3'] as our example.

First, we pop '1' from the stack, leaving us with st = ['2', '3'].
Then, we reverse st, leaving us with st = ['3', '2'].
Finally, we insert '1' at the right side of st by calling insert_bottom('1'), leaving us with st = ['3', '2', '1'].

As you can see, we have successfully reversed st.

Upvotes: 1

Abrikot
Abrikot

Reputation: 995

To understand what your methods do, you have to understand what a Stack is. A Stack is like a stack of plates: you can only put plates on the top of the stack, or retrieve plates from the top. Otherwise, the stack will collapse.

If you want to add a plate at the bottom of the plate, you have to remove all the plates before. The easy way is to do as following: while there is a plate on the stack, you remove it and put it aside. If the stack is empty, then you can put your new plate at the bottom of the stack. Then you have to put back all the plates on the newly-bottom plate.

That the exact same operation here in insert_at_bottom but with a recursive method: while you have a char in your stack - i.e. it is not empty -, you put the top char - which is labelled as a - aside and you try again to put x to the bottom. If the stack is not empty, you re-do the operation. Once you have hit the bottom of your stack, you can put x there and start pushing all the other chars in the same order they were before.

The reverse method uses almost the same process with a little twist: you take the top char, put is aside, take the second-top char, put it aside, ... When you're on the last char, you can put it at the bottom of the stack. Then you put the previously-second-bottom char at the bottom of the stack... And you go back to the previously-top char that you put to the final bottom. All your stack has then been reversed.

Upvotes: 0

Related Questions