假设栈的输入序列为1 2 3 ... n，设计算法求出所有可能的出栈序列。比如输入1 2 3 4 5，可能出栈的序列为1 2 3 4 5，1 3 4 5 2等42个。
void StackPopLegal(vector<int> ans, linkedStack stk, linkedStack input, vector<vector<int>>& result, int n) {
if (ans.size() == n) {
result.push_back(ans);//在vector的末尾插入一个元素
return;
}
sNode* stk_tmp;
Init(stk_tmp);
vector<int> ans_tmp = ans;
sNode* p = stk->next;
int x = 0;
while (p != NULL) {
x = p->data;
PushStack(stk_tmp, x);
p = p->next;
}
delete p;
//输入直接出栈
if (!StackIsEmpty(stk)) {
int x = 0, temp = 0;
StackTop(stk, x);
ans.push_back(x);
PopStack(stk, temp);
StackPopLegal(ans, stk, input, result, n);//递归
}
//输入直接入栈
if (!StackIsEmpty(input)) {
int x = 0, temp = 0;
StackTop(input, x);
PushStack(stk_tmp, x);
PopStack(input, temp);
StackPopLegal(ans_tmp, stk_tmp, input, result, n);
}
delete stk_tmp;
}
帮忙看看算法思路，里面的函数没有问题，但是只能求出1 2 3 4 …… n这一个合法出栈序列，为什么？
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> getPermutations(int n) {
vector<vector<int>> res;
if (n == 0) { // 栈大小为0，返回空数组
return res;
}
if (n == 1) { // 栈大小为1，返回仅包含一个元素的数组
vector<int> v = {1};
res.push_back(v);
return res;
}
for (int i = 1; i <= n; ++i) { // 枚举每个元素作为第一个出栈的元素
vector<vector<int>> p = getPermutations(n - 1); // 递归求解剩余元素的出栈序列
for (int j = 0; j < p.size(); ++j) {
vector<int> v = p[j];
v.insert(v.begin(), i); // 将i插入到序列的开始，得到新的出栈序列
res.push_back(v);
}
}
return res;
}
int main() {
int n = 5;
vector<vector<int>> res = getPermutations(n);
for (int i = 0; i < res.size(); ++i) {
vector<int> v = res[i];
for (int j = 0; j < v.size(); ++j) {
cout << v[j] << " ";
}
cout << endl;
}
return 0;
}
先进后出（后进先出）