數(shù)據(jù)結(jié)構(gòu)中n個數(shù)據(jù)依次入棧，出棧順序有多少種？誰能幫忙證明下？n個數(shù)據(jù)依次入棧，出棧順序種數(shù)的遞推公式如下：F(n)=∑(F(n-1-k)*Fk)其中k從0到n-1已知F0=1，F(xiàn)1=F0*F0=1F

數(shù)據(jù)結(jié)構(gòu)中n個數(shù)據(jù)依次入棧，出棧順序有多少種？誰能幫忙證明下？

n個數(shù)據(jù)依次入棧，出棧順序種數(shù)的遞推公式如下：F(n)=∑(F(n-1-k)*Fk)其中k從0到n-1已知F0=1，F(xiàn)1=F0*F0=1F2=F1*F0 F0*F1=2F3=F2*F0 F1*F1 F0*F2=5……證明的話，對于n個數(shù)據(jù)，我只看第一個數(shù)據(jù)的出入棧順序：第一個數(shù)據(jù)入棧到出棧之間可以包含0，1，2…n-1個數(shù)據(jù)的出入棧，相應(yīng)的，第一個數(shù)據(jù)出棧之后，還有n-1，n-2…2，1，0個數(shù)據(jù)需要出入棧根據(jù)組合數(shù)學(xué)里面的乘法原理，需要把第一個數(shù)據(jù)出棧前后的種數(shù)相乘根據(jù)加法原理，需要把第一個數(shù)據(jù)出入棧的n種方式全加起來于是就得到了那個遞推公式，不過，要找出一個直接計算Fn的公式似乎不太好辦。

定義棧的順序存儲結(jié)構(gòu)，實現(xiàn)入棧操作，出棧操作，判斷棧為空的基本操作，設(shè)計算法？

對于單向鏈表來說最好從頭入棧，從頭出棧，這樣就可以不用移動，時間復(fù)雜度O(1)，不然每次入棧出棧都要走到最后一個節(jié)點，時間復(fù)雜度O(n)。

如果是雙向鏈表，則有頭尾節(jié)點，在頭出入棧和在尾出入棧都是一樣的。