Понимание механизма рекурсивного вызова для реализации очереди с использованием стека - PullRequest
Новая
       50

Понимание механизма рекурсивного вызова для реализации очереди с использованием стека

0 голосов
/ 13 января 2020

Я пытаюсь реализовать очередь, используя стек и рекурсивный вызов, это класс Stack и несколько методов: 

#include <iostream>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */

class Node{
    public:
        int data;
        Node* next;
};

Node* top = NULL;

void push(int data){
    Node* node = new Node();
    node->data = data;
    node->next = top;
    top = node;
    cout << "pushato: " << node->data << "\n";
};

bool isempty(){
    if(top==NULL){
        return true;
    }else{
        return false;
    }
};

void pop(){
    if(isempty()){
        cout << "lo stack e vuoto.\n";
    }else{
        Node* ptr = top;
        top = top->next;
        cout << "eliminato: " << ptr->data << "\n";
        delete(ptr);
    }
};

Node* showtop(){
    if(!isempty()){
        cout << "l'elemento del top e: " << top->data << "\n";
        return top;
    }else{
        cout << "lo stack e vuoto.\n";
    }
};

И это структура для очереди: 

struct Queue{
    void enQueue(int x) 
    { 
        push(x); 
    } 

    int deQueue() 
    { 
        if (isempty()) { 
            cout << "Q is empty"; 
            exit(0); 
        } 

        // pop an item from the stack 
        int x = showtop()->data; 
        pop(); 

        // if stack becomes empty, return 
        // the popped item 
        if (isempty()){
            return x; 
        }


        // recursive call 
        int item = deQueue(); 

        // push popped item back to the stack 
        push(x);

        // return the result of deQueue() call 
        return item; 
    } 
};

Это главное: 

int main(int argc, char** argv) {
     Queue q; 
    q.enQueue(1); 
    q.enQueue(2); 
    q.enQueue(3); 

    cout << q.deQueue() << '\n'; 
    cout << q.deQueue() << '\n'; 
    cout << q.deQueue() << '\n'; 
    return 0;
}

И это вывод: 

pushed:1
pushed:2
pushed:3
popped 3
popped 2
popped 1
pushed 2
pushed 3
1
popped 3
popped 2
pushed 3
2
popped 3
3

Код работает нормально, и вывод полностью правильный, но я не действительно понятно, почему после того, как рекурсивный вызов заканчивается, и я возвращаю x в if, все предыдущие элементы помещаются в стек? Как push(x) снова добавляет предметы в стек без элемента внизу?

Ответы [ 3 ]

1 голос
/ 13 января 2020

Чтобы понять, как код помещает элементы в стек с помощью push(x), рассмотрим следующее Q / As относительно очереди с N элементами внутри, с 1 в качестве нижнего элемента и N в качестве верхнего:

Q: Сколько раз вызывается функция deQueue()? Ответ: N раз. Первый раз из main() и N-1 раз рекурсивно.

Q: В методе deQueue() есть оператор if, который возвращает x. Сколько раз выполняется условие этого оператора if? Ответ: Только один раз.

Q. Итак, сколько раз выполняется код после упомянутого оператора if (включая оператор push(x))? Ответ: N-1 раз.

Q: В первый раз выполняется строка push(x)? Ответ: Он выполняется впервые, когда его предыдущий оператор, т. Е. int item = deQueue();, вернулся нормально без каких-либо рекурсий.

Q: В таком случае (первый вызов push(x)), каково будет значение x? Ответ: Если deQueue() возвращается нормально и не повторяется, значение x будет равно 1. Но для последней рекурсии до этого значение x равно 2.

Q: И какое значение будет равно x для следующего вызова pu sh(x)? Ответ: 3

Q: А для остальных? Ответ: 4, 5, ... N.

0 голосов
/ 13 января 2020

Он «выталкивает» нижний элемент стека, временно сохраняя элемент до тех пор, пока он не достигнет дна, а затем возвращает их обратно при возврате рекурсивных вызовов.

Удалите один элемент и сохраните его для дальнейшего использования: 

int x = showtop()->data; 
pop();

Если это был нижний элемент, верните его: 

if (isempty()){
    return x; 
}

В противном случае, пусть рекурсивный вызов удалит нижний элемент и передаст нам: 

 int item = deQueue();

Теперь в стеке находятся все элементы, кроме нижнего (item) и того, который мы удалили (x), поэтому мы помещаем тот, который мы удалили, сверху: 

push(x);

и передать нижний элемент, который мы получили из рекурсии: 

return item;

Я подозреваю, что вас сбивает с толку то, что deQueue может вернуть значение для предыдущего вызова на deQueue, а не на main.
(Возвращение из рекурсии не похоже на выход из al oop.)

Более конкретно, если ваша очередь 

1 2 3

Первый вызов сначала сохранит 1 в x, затем recurse (теперь стек 2 3).
Второй вызов s tores 2 в его x и рекурсах (3).
Третий вызов удаляет 3, оставляя пустой стек, и возвращает 3 вызывающей стороне.
Второй вызов затем возвращает назад 2, который он принял, и возвращает 3 (2).
Затем первый вызов возвращает 1 и также возвращает 3 (1 2).

0 голосов
/ 13 января 2020

В вашей функции deQueue() есть фрагмент кода, который (если true) выходит из программы: 

if (isempty()) { 
    cout << "Q is empty"; 
    exit(0); 
}

Через несколько строк вы получите: 

if (isempty()){
    return x; 
}

Это никогда не может быть выполнен, потому что вы уже звонили exit(0).

...