1) 假设栈的输入序列为1、2、3、...、n，设计算法求出所有可能的出栈序列。比如输入1、2、3、4、5，可能出栈的序列为12345、13452等42个。 请使用c++代码实现

以下是C代码实现：

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

#define MAX_SIZE 100

typedef struct Stack
{
int top;
int data[MAX_SIZE];
} Stack;

Stack* createStack()
{
Stack* stack = (Stack*)malloc(sizeof(Stack));
stack->top = -1;
return stack;
}

void push(Stack* stack, int item)
{
stack->data[++stack->top] = item;
}

int pop(Stack* stack)
{
return stack->data[stack->top--];
}

int isEmpty(Stack* stack)
{
return stack->top == -1;
}

void printStackSequence(int input[], int size)
{
int output[MAX_SIZE];
int outIndex = 0;
Stack* stack = createStack();

int i = 0, j = 0;
while (i < size)
{
while (!isEmpty(stack) && stack->data[stack->top] < input[i])
{
output[outIndex++] = pop(stack);
}
push(stack, input[i++]);
}

while (!isEmpty(stack))
{
output[outIndex++] = pop(stack);
}

printf("Possible stack sequences: \n");
int* permutation = (int*)malloc(sizeof(int) * size);
for (int i = 0; i < size; i++)
{
permutation[i] = i;
}

do {
for (j = 0; j < size; j++)
{
if (output[j] != input[permutation[j]])
{
break;
}
}

if (j == size)
{
for (j = 0; j < size; j++)
{
printf("%d ", output[j]);
}
printf("\n");
}

} while (next_permutation(permutation, permutation+size));
}

#if 0 // 测试
int main()
{
int input[] = { 1, 2, 3, 4, 5 };
int size = sizeof(input) / sizeof(int);
printStackSequence(input, size);
return 0;
}
#endif