给定一个字符串，设计一个算法完成对该字符串的一个全排列的输出。比如：字符串 “abc”，输出结果应该是“abc”、“acb”、“bac”、“bca”、“cab” 和 “cba”。 要求：①使用递归思想，编写一个函数 permutationByRecursion，该函数用来生成给定的字符 串的全排列结果。②使用栈数据结构，将①中编写的算法转换成非递归函数，函数名为： permutationByNoRecursion。（利用课堂上讲解的分解 Hanoi 塔的任务方式），该函数所使用的栈 数据结构只能使用自己定义的栈数据结构，不能使用任何语言提供的栈

permutationByRecursion函数的代码如下：

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

void permutationByRecursion(string str, int start, int end) {
    if (start == end) {
        cout << str << endl;
    } else {
        for (int i = start; i <= end; i++) {
            swap(str[start], str[i]);
            permutationByRecursion(str, start + 1, end);
            swap(str[start], str[i]);
        }
    }
}

int main() {
    string str = "abc";
    permutationByRecursion(str, 0, str.size() - 1);
    return 0;
}

permutationByNoRecursion函数的代码如下：

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

struct Stack {
    char data[100];
    int top;
};

void initStack(Stack &s) {
    s.top = -1;
}

bool isEmpty(Stack &s) {
    return s.top == -1;
}

bool isFull(Stack &s) {
    return s.top == 99;
}

void push(Stack &s, char c) {
    if (isFull(s)) {
        cout << "Stack is full!" << endl;
    } else {
        s.top++;
        s.data[s.top] = c;
    }
}

char pop(Stack &s) {
    if (isEmpty(s)) {
        cout << "Stack is empty!" << endl;
        return '\0';
    } else {
        char c = s.data[s.top];
        s.top--;
        return c;
    }
}

void permutationByNoRecursion(string str) {
    Stack s;
    initStack(s);
    int start = 0;
    int end = str.size() - 1;
    push(s, end);
    while (!isEmpty(s)) {
        end = pop(s);
        if (start == end) {
            cout << str << endl;
            start++;
            if (start <= end) {
                push(s, end);
            }
        } else {
            for (int i = end; i >= start; i--) {
                swap(str[end], str[i]);
                push(s, end - 1);
            }
        }
    }
}

int main() {
    string str = "abc";
    permutationByNoRecursion(str);
    return 0;
}