Блог

Код работает хорошо. Просто я этого не понимаю. Возникли трудности в рекурсивной части. В этой части: char a = st.peek();st.pop(); insert_at_bottom(x); st.push(a); моя идея заключается в том, что сначала он будет выполняться char a = st.peek();st.pop() все время до достижения порогового значения. затем он будет выполнен st.push(a); один раз. Таким a образом, значение будет присвоено только один раз. Очевидно, что это неправда.

Трудная часть для меня заключается в insert_at_bottom методе insert_at_bottom(x) , что делает? в reverse методе, что делает reverse() , insert_at_bottom(x) делает?

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

Для начала мы будем использовать [] обозначения для стеков. Будет обозначена пустая стопка [] . Когда мы нажимаем или открываем элемент, мы делаем это с левой стороны. Например, если мы начнем с [1, 2, 3] и хлопнем, нас оставят, [2, 3] и поп вернется 1 . И если мы начнем с [1, 2, 3] этого и будем настаивать 0 , то останемся ни с [0, 1, 2, 3] чем .

insert_at_bottom единственная цель состоит в том, чтобы позволить нам добавить элемент в правую часть стека, а не в левую часть стека.

Итак, как мы вставляем что-то (скажем, мы хотим вставить x ) в правую часть стека, а не в левую? Мы рассматриваем два разных случая:

1. Стопка пуста: то есть st = [] .

В этом случае толчок вправо и толчок влево-это одно и то же, поэтому мы просто позвонили st.push(x) и сейчас сделали st = [x] .

2. Стек непустой: например, стек является [‘1’, ‘2’, ‘3’].

Сначала мы '1' снимаем стопку. Теперь у нас есть st = ['2', '3'] .
Затем мы нажимаем x на правую сторону st , делая рекурсивный вызов. Это дает нам st = ['2', '3', x] .
Наконец, мы '1' возвращаемся в стопку. Это дает нам st = ['1', '2', '3', x] . Как вы можете видеть, мы успешно вставили x в крайнее правое положение st .

Вот как insert_at_bottom это работает.

Теперь, как это reverse работает? Мы снова рассмотрим два разных случая.

1. Стопка пуста, то есть st = [] .

В этом случае нам не нужно ничего делать, чтобы повернуть вспять st .

2. Стопка не пуста; мы возьмем st = ['1', '2', '3'] в качестве примера.

Сначала мы выскакиваем '1' из стека, оставляя нас с st = ['2', '3'] .
Затем мы разворачиваемся st , оставляя нас с st = ['3', '2'] .
Наконец, мы вставляем '1' с правой стороны st по вызову insert_bottom('1') , оставляя нас с st = ['3', '2', '1'] .

Как вы можете видеть, мы успешно изменили st направление .

Чтобы понять, что делают ваши методы, вы должны понять, что такое Stack а. A Stack похоже на стопку тарелок: вы можете положить тарелки только на верхнюю часть стопки или извлечь тарелки сверху. В противном случае стек рухнет.

Если вы хотите добавить тарелку в нижней части тарелки, вам придется удалить все тарелки до этого. Самый простой способ состоит в том, чтобы сделать следующее: пока в стопке есть тарелка, вы снимаете ее и откладываете в сторону. Если стопка пуста, то вы можете положить свою новую тарелку в нижней части стопки. Затем вы должны положить все пластины обратно на новую нижнюю пластину.

Что та же самая операция здесь, insert_at_bottom но с рекурсивным методом: пока у вас char в стеке есть a, то есть он не пуст, вы откладываете верхнюю char часть, которая помечена как a , в сторону, и снова пытаетесь положить x ее на дно. Если стек не пуст, вы повторяете операцию. Как только вы достигнете нижней части своего стека, вы можете положить x туда и начать толкать все остальные char s в том же порядке, в каком они были раньше.

reverse Метод использует почти тот же процесс с небольшим поворотом: вы берете верхнюю char часть , откладываете ее в сторону, берете вторую верхнюю char часть , откладываете ее в сторону … Когда вы будете на последнем char , вы можете положить его в самый низ стопки. Затем вы кладете ранее-второе-дно char в нижней части стопки… И вы возвращаетесь к предыдущему началу char , которое вы положили на последнее дно. Затем весь ваш стек был перевернут.