Question

若让元素1，2，3，4，5依次进栈，则出栈的可能性有哪些?

列出所有可能

Answer 1

#include <stdio.h>
#include <stdlib.h>
#define ELEMENT_TYPE int

/* 打印所有可能的出栈顺序
参数：
queue 已知的入栈顺序
queue_size 栈 queue 的大小

递归使用参数：
poped_queue 出栈顺序。poped_queue[i]=j 表示元素 queue[j] 第 i 个出栈。可以初始为 NULL。
poped_queue_size poped_queue 栈的大小。必须初始为 0 。

total 统计出栈顺序总数。可以初始为 NULL。或者初始为一个变量的地址，该变量的值必须为 0。
*/
void printAllPopOrder(ELEMENT_TYPE queue[],int queue_size,
int poped_queue[],int poped_queue_size,int *total)
{
int i,j,max_index,top_index;

// 分配临时空间
if(poped_queue == NULL)
poped_queue = (int*)malloc(sizeof(int)*queue_size);

if(poped_queue_size == queue_size)
{
// 全部元素已经出栈，打印出栈顺序
for(i=0;i<poped_queue_size;i++)
printf("%d ",queue[poped_queue[i]]);
printf("\n");

if(total)
(*total)++;
}
else
{
// 枚举元素 queue[i] 是否能出栈
for(i=0;i<queue_size;i++)
{
// 根据当前的出栈顺序 poped_queue,判断出已经入栈元素的最大索引。
for(j=0,max_index=-1;j<poped_queue_size;j++)
if(max_index < poped_queue[j])
max_index = poped_queue[j];

// 根据当前的出栈顺序 poped_queue,找出当前入栈栈顶元素索引。
for(top_index=max_index-1;top_index>=0;top_index--)
{
for(j=0;j<poped_queue_size;j++)
if(top_index == poped_queue[j])
break;
if(j == poped_queue_size)
break;
}

// 判断元素 queue[i] 能否出栈
if( i>max_index || i==top_index)
{
poped_queue[poped_queue_size] = i;
printAllPopOrder(queue,queue_size,poped_queue,poped_queue_size+1,total);
}
}
}
}
/*
"所有可能出栈的顺序总数" ，其实是一个卡特兰数(CatalanNumber)。
设栈的元素数目为 n , 那么"所有可能出栈的顺序总数"为：
2n!/(n+1)/n!
也就是第 n 个卡特兰数。

参数：
n 卡特兰数的编号（从1开始）
返回：
第 n 个卡特兰数

*/
int getCatalanNumber (int n)
{
int total = 1,i;
for(i=2*n;i>=(n+2);i--)
total *= i;

for(i=1;i<=n;i++)
total /= i;

return total;
}

int main(int argc, char *argv[])
{
// 列出元素进栈顺序
ELEMENT_TYPE queue[]={1,2,3,4,5};
int queue_size = sizeof(queue)/sizeof(queue[0]);

int total_1=0,toatl_2=0;

// 输出所有可能的出栈顺序
printAllPopOrder(queue,queue_size,NULL,0,&total_1);
printf("total = %d\n",total_1);

// 调用 printAllPopOrder 其实已经通过变量 total_1 得到了出栈顺序的总数。
// 下面用公式(卡特兰数)计算所有可能出栈顺序的总数。
toatl_2 = getCatalanNumber(queue_size);

printf("total = %d\n",toatl_2);
return 0;
}
/*
1 2 3 4 5
1 2 3 5 4
1 2 4 3 5
1 2 4 5 3
1 2 5 4 3
1 3 2 4 5
1 3 2 5 4
1 3 4 2 5
1 3 4 5 2
1 3 5 4 2
1 4 3 2 5
1 4 3 5 2
1 4 5 3 2
1 5 4 3 2
2 1 3 4 5
2 1 3 5 4
2 1 4 3 5
2 1 4 5 3
2 1 5 4 3
2 3 1 4 5
2 3 1 5 4
2 3 4 1 5
2 3 4 5 1
2 3 5 4 1
2 4 3 1 5
2 4 3 5 1
2 4 5 3 1
2 5 4 3 1
3 2 1 4 5
3 2 1 5 4
3 2 4 1 5
3 2 4 5 1
3 2 5 4 1
3 4 2 1 5
3 4 2 5 1
3 4 5 2 1
3 5 4 2 1
4 3 2 1 5
4 3 2 5 1
4 3 5 2 1
4 5 3 2 1
5 4 3 2 1
total = 42
total = 42

ps;
"@找个名字真难呐" 列出了34个，少了8个，它们是：
12453
13425
13452
13542
14352
14532
21354
21453
*/

Answer 2

不一定要一次性全部都进栈，也不一定一次性都出栈！
可以push(1) pop(1) push(2) push(3) pop(3) push(4) pop(4) pop(2) push(5) pop(5)
也可以有其他N多种 push 跟 pop 的顺序 答案也就有N种了 。一楼的答案蛮准的 （全不全我就不知道了）
至于有多少种答案也就是把5次 push 跟 5次pop 进行排序 ，而且 pop时要保证栈不是空的！

Answer 3

进栈从栈底起，出栈从栈顶起，没有其他可能。12345依次进栈，出栈则是54321的顺序，这是最基本的堆栈法则怎么可能有其他方式呢

Answer 4

“栈”的特点是LIFO(后进先出)，所以正常操作的话，出栈情况只有一种，就是: 5，4，3，2，1。

Answer 5

如果依次进栈，相当于把东西放到口袋里，先放1，再放2，再放3,4,5，那么取出来的时候即出栈，就是先拿出5，再拿出4，再拿出3,2,1，