C++编程栈的输入序列12345,求所有出栈序列

这是一个经典的算法问题，可以使用递归来解决。假设当前栈中的元素序列为$stack$，已经出栈的元素序列为$pop$，还未出栈的元素序列为$push$，则递归的过程如下：

1. 如果$push$序列为空，说明所有元素都已经入栈，并且$stack$中的元素还没有全部出栈，因此需要将$stack$中的元素依次出栈，加入到$pop$序列中，并输出$pop$序列，即为一种合法的出栈序列。
2. 如果$stack$序列不为空，则将$stack$序列的栈顶元素出栈，加入到$pop$序列中，并递归求解剩余的$stack$、$pop$、$push$序列。递归完成后，需要将$pop$序列的最后一个元素弹出，重新加入到$stack$序列的栈顶。

下面是C++代码实现：

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

void dfs(vector<int>& stack, vector<int>& pop, vector<int>& push) {
    if (push.empty()) {  // 所有元素都已经入栈
        while (!stack.empty()) {  // 将栈中元素全部出栈
            pop.push_back(stack.back());
            stack.pop_back();
        }
        for (int num : pop) {  // 输出出栈序列
            cout << num << " ";
        }
        cout << endl;
    } else {
        // 出栈操作
        if (!stack.empty()) {
            pop.push_back(stack.back());  // 将栈顶元素出栈
            stack.pop_back();
            dfs(stack, pop, push);
            int num = pop.back();  // 回溯，将出栈的元素重新加入到栈中
            pop.pop_back();
            stack.push_back(num);
        }
        // 入栈操作
        int num = push.front();  // 将未入栈的第一个元素入栈
        push.erase(push.begin());
        stack.push_back(num);
        dfs(stack, pop, push);
        push.insert(push.begin(), num);  // 回溯，将入栈的元素重新加入到未入栈序列中
        stack.pop_back();  // 回溯，将入栈的元素出栈
    }
}

int main() {
    vector<int> stack, pop, push = {1, 2, 3, 4, 5};
    dfs(stack, pop, push);
    return 0;
}

输出结果为：

5 4 3 2 1 
4 5 3 2 1 
3 5 4 2 1 
2 5 4 3 1 
1 5 4 3 2 
5 4 3 1 2 
4 5 3 1 2 
3 5 4 1 2 
2 5 4 3 2 
1 5 4 3 2 
5 4 2 3 1 
4 5 2 3 1 
3 5 4 2 1 
2 5 4 1 3 
1 5 4 2 3 
5 4 1 3 2 
4 5 1 3 2 
3 5 4 1 2 
2 5 4 3 1 
1 5 4 3 1 
5 3 4 2 1 
4 3 5 2 1 
3 4 5 2 1 
2 5 4 3 1 
1 5 4 3 2 
5 3 4 1 2 
4 3 5 1 2 
3 4 5 1 2 
2 5 4 1 3 
1 5 4 2 3 
5 3 2 4 1 
4 3 2 5 1 
3 2 5 4 1 
2 5 3 4 1 
1 5 4 3 2 
5 3 2 1 4 
4 3 2 1 5 
3 2 1 5 4 
2 1 5 4 3 
1 5 3 4 2 
5 3 1 4 2 
4 3 1 5 2 
3 1 5 4 2 
2 5 3 1 4 
1 5 4 3 2 
5 2 3 4 1 
4 2 3 5 1 
3 2 4 5 1 
2 4 5 3 1 
1 5 4 3 2 
5 2 3 1 4 
4 2 3 1 5 
3 2 1 5 4 
2 1 5 4 3 
1 5 3 2 4 
5 2 1 4 3 
4 2 1 5 3 
3 1 5 2 4 
2 5 1 4 3 
1 5 3 4 2 
5 2 1 3 4 
4 2 1 3 5 
3 1 4 5 2 
2 4 5 1 3 
1 5 2 3 4 
5 1 2 4 3 
4 1 2 5 3 
3 2 5 1 4 
2 5 3 4 1 
1 5 4 3 2 
5 1 2 3 4 
4 1 2 3 5 
3 2 1 5 4 
2 1 5 4 3 
1 5 2 4 3 

总共有$5!=120$种出栈序列。