用栈求所有的输出队列

Question

/*3)假设栈的输入序列为1、2、3、...、n，设计算法求出所有可能的出栈序列。
比如输入1、2、3、4、5，可能出栈的序列为12345、13452等42个。
*/
#include"Queue.h"
 typedef struct sStack {
    element data[max];
    int top;
}seqStack;
void initialStack(seqStack& S) {
    S.top = -1;
}
bool stackEmpty(seqStack& S) {
    if (S.top == -1)
        return true;
    else
        return false;
}
bool stackFull(seqStack& S) {
    if (S.top == max - 1)
        return true;
    else
        return false;
}
bool pushStack(seqStack& S, element x) {//入栈
    if (stackFull(S))
        return false;
    else
    {
        S.top++;
        S.data[S.top] = x;
        return true;
    }
}
bool popStack(seqStack& S, element& x) {//出栈
    if (stackEmpty(S))
        return true;
    else {
        x = S.data[S.top];
        S.top--;
        return true;
    }
}
bool stackTop(seqStack& S, element& x) {//取栈顶元素
    if (stackEmpty(S))
        return false;
    else {
        x = S.data[S.top];
        return true;
    }
}
int fun(seQueue inQ, int n, seqStack& S, seQueue outQ) {
    if (n <= 0 || queueEmpty(inQ) && queueEmpty(outQ) && stackEmpty(S)) {
        return 0;
    }
    if (sizeQueue(inQ) == n) {
        element x=0;//存放出队队列队头元素
          while (!queueEmpty(outQ)) {
            queueFront(outQ, x);
            cout << x << " ";
            outQueue(outQ);
         }
        cout << endl;
        return 0;
    }
    //seqStack SCopy = S;
    //seQueue QCopy = outQ;
    element y;//存放栈顶元素
    if (!stackFull(S)) {
        stackTop(S, y);
        enQueue(outQ, y);
        popStack(S, y);
        fun(inQ, n, S, outQ);
    }
    element z=0;//存放入队队列队头元素
    if (!queueEmpty(inQ)) {
        queueFront(inQ, z);
        pushStack(S, z);
        outQueue(inQ);
        fun(inQ, n, S, outQ);
    }
    return 0;
}
int main() {
    seQueue inQ, outQ;
    seqStack S;
    initialStack(S);
    initQueue(inQ);
    initQueue(outQ);
    int n,a[100];
    cout << "输入元素个数：";
    cin >> n;
    cout << "输入元素：" << endl;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        enQueue(inQ, a[i]);
    }
    fun(inQ, n, S, outQ);
    return 0;
}
头文件队列的相关运算如下
#include<iostream>
#include<stdlib.h>
using namespace std;
#define max 100
typedef int element;
typedef struct sQueue {
    element data[max];
    int front;
    int rear;
}seQueue;
void initQueue(seQueue& Q) {
    Q.front = 0;
    Q.rear = 0;
}
bool queueEmpty(seQueue& Q) {
    if (Q.front == Q.rear)
        return true;
    else
        return false;
}
void queueFront(seQueue& Q, element x) {//取队头元素
    if (queueEmpty(Q))
        cout << "队空，不可取队头元素！";
    else
        x=Q.data[(Q.front + 1) % max] ;
}
void enQueue(seQueue& Q, element x) {//入队
    Q.rear = ((Q.rear) + 1) % max;
    Q.data[Q.rear] = x;
}
void outQueue(seQueue& Q) {//出队
    Q.front = (Q.front + 1) % max;
}
int sizeQueue(seQueue& Q) {//求队列中元素个数
    return (Q.rear - Q.front+max) % max;
}

编译没有问题，运行时输完数后，按回车什么都输不出来，这个我感觉有点难对我来说，这种写法也只是看到一个人的博客尝试一下，但我真的希望能搞出来，麻烦帮我看看哪里不合适，哪怕只是很小的一个地方，我也会认真改正

Answer 1

这样写，死算：

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100 // 栈的最大长度

int stack[MAX_SIZE]; // 栈
int top = -1; // 栈顶指针

void push(int value) { // 入栈
    stack[++top] = value;
}

int pop() { // 出栈
    if (top < 0) {
        printf("Stack underflow!\n");
        exit(1);
    }
    return stack[top--];
}

int is_empty() { // 判断栈是否为空
    return top < 0;
}

void print_stack(int* output, int len) { // 输出栈
    for (int i = 0; i < len; ++i) {
        printf("%d ", output[i]);
    }
    printf("\n");
}

void backtrack(int* input, int n, int* output, int len, int* count) { // 回溯法
    if (len == n) { // 找到一组出栈序列
        print_stack(output, len);
        (*count)++;
        return;
    }
    for (int i = 0; i < n; ++i) {
        int value = input[i];
        if (top < 0 || value > stack[top]) { // 如果当前元素比栈顶元素大，就入栈
            push(value);
            backtrack(input, n, output, len, count);
            pop(); // 回溯，弹出栈顶元素
        }
    }
}

int main() {
    int n;
    printf("Enter n: ");
    scanf("%d", &n);

    int* input = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; ++i) {
        input[i] = i + 1;
    }

    int* output = (int*)malloc(n * sizeof(int));
    int count = 0;
    backtrack(input, n, output, 0, &count);
    printf("Total: %d\n", count);
    free(input);
    free(output);
    return 0;
}