c++

如何使用c++ stack类进行递归

小樊
82
2024-09-25 08:31:17
栏目: 编程语言

C++的stack类并不支持递归,因为它的主要作用是后进先出(LIFO)的数据结构,用于存储一系列的元素,并只能在其一端(称为栈顶)进行插入和删除操作。

如果你想在递归函数中使用类似栈的功能,你可以使用C++的STL库中的stack类,或者自己定义一个栈类。

以下是一个简单的自定义栈类的例子:

#include <iostream>
#include <vector>
using namespace std;

template <typename T>
class Stack {
private:
    vector<T> data;
public:
    void push(T val) {
        data.push_back(val);
    }
    T pop() {
        if (isEmpty()) {
            throw runtime_error("Stack is empty");
        }
        T val = data.back();
        data.pop_back();
        return val;
    }
    T top() {
        if (isEmpty()) {
            throw runtime_error("Stack is empty");
        }
        return data.back();
    }
    bool isEmpty() {
        return data.empty();
    }
};

int factorial(int n) {
    Stack<int> s;
    s.push(1);
    while (n > 1) {
        s.push(n);
        n = n - 1;
    }
    int result = 1;
    while (!s.isEmpty()) {
        result = result * s.pop();
    }
    return result;
}

int main() {
    cout << factorial(5) << endl;
    return 0;
}

在这个例子中,我们定义了一个模板类Stack,它有push、pop、top和isEmpty等方法。然后在factorial函数中,我们使用Stack来存储递归调用的结果,以实现递归计算阶乘的功能。

0
看了该问题的人还看了