本文共 567 字,大约阅读时间需要 1 分钟。
学过数据结构的程序猿应该都清楚,栈是一种先入后出,后入先出(LIFO)的表。即插入和删除都只能在一个位置上进行,即栈顶位置。对栈的基本操作有Push(入栈)和Pop(出栈)。在一般软件研发的笔试中,就会经常遇到关于入栈次序一定时,出栈次序有哪些?共有几种?
其实,此处只要了解一下卡特兰数的算法结构,参见:
由卡特兰数的思想可知。若有n个元素顺序入栈,则对应的出栈次序共有f(n)=f(0)f(n-1)+f(1)f(n-2)+……+f(n-1)f(0)
(其中f(0)=1;f(1)=1);
举个例子:
如果说入栈元素次序是abc,则由递推公式可得出栈次序共有5种。出栈顺序分别如下:
abc push pop push pop push pop a入栈→a出栈→b入栈→b出栈→c入栈→c出栈
acb push pop push push pop pop a入栈→a出栈→b入栈→c入栈→c出栈→b出栈
bac push push pop pop push pop a入栈→b入栈→b出栈→a出栈→c入栈→c出栈
bca push push pop push pop pop a入栈→b入栈→b出栈→c入栈→c出栈→a出栈
cba push push push pop pop pop a入栈→b入栈→c入栈→c出栈→b出栈→a出栈
转载地址:http://hjrzi.baihongyu.com/