這是工作中遇到的小問題。

數(shù)據(jù)結(jié)構(gòu)中有一種數(shù)據(jù)類型——堆棧，該結(jié)構(gòu)中的數(shù)據(jù)項有如下特點：

除了最前面和最后面的數(shù)據(jù)，每個數(shù)據(jù)項都有一個前驅(qū)結(jié)點和一個后繼結(jié)點；

堆棧兩端分別稱為棧頂和棧底，數(shù)據(jù)項只能在棧頂加入或者彈出。

很明顯，堆棧的數(shù)據(jù)遵循先入后出原則。假設(shè)我們有 3 個不同的數(shù)據(jù)項，編號 1，2，3，只要保證入棧順序是大編號在后小編號在前，且每次進棧的數(shù)量不限，則所有可能的出棧順序有：1-》2-》3，1-》3-》2，2-》1-》3，2-》3-》1，3-》2-》1 一共 5 種，注意 3-》1-》2 不是可能的出棧順序，因為如果 3 最先出棧，那么 1 和 2 必在棧中（如果還未入棧，則說明 3 先入棧，與假設(shè)矛盾），只能 2 在上 1 在下，所以出棧順序必然是 2-》1。那么，

問題一：編號\（1\sim n\）的連續(xù)數(shù)據(jù)項以編號的先后順序入棧然后出棧，所有可能的出棧順序有多少種？

上面的問題比較難于回答，引申之后得到另一個比較弱的問題

問題二：給定一個長度為\（n\） 的整數(shù)序列，且各個元素均不相同，它是否是一個出棧序列？

為了回答以上的兩個問題，我們首先來看下一個正常的出棧序列有什么特點。假設(shè)長度為 \（n\）的出棧序列是\（a_1，a_2，…，a_n\），取其中第\（k\） 個數(shù) \（a_k\），則有如下結(jié)論：

\（a_k\）之前的所有數(shù)據(jù)項都已經(jīng)出棧，即\（a_1，a_2，…，a_{k-1}\）都已經(jīng)出棧；

\（a_k\） 之后的所有數(shù)據(jù)項中，小于 \（a_k\）的都在棧內(nèi)，大于\（a_k\）的尚未入棧；

\（a_k\）之后緊跟的出棧數(shù)據(jù)項 \（a_{k+1}\） 要么大于\（a_k\），要么是所有未出棧的比\（a_k\）小的數(shù)據(jù)項中最大的一個

結(jié)論 1 很明顯，因為本身就是出棧序列，因此之前的數(shù)據(jù)肯定已經(jīng)出棧；結(jié)論 2 中，之后的數(shù)據(jù)只有兩種存在的可能：在棧內(nèi)，或者未進棧。比\（a_k\）小的如果未進棧，那么 akak 根本不可能出棧（因為就沒進棧），比\（a_k\）大的如果在棧內(nèi)，那\（a_k\）也無法出棧，因為\（a_k\）在它的下面，因此得證；結(jié)論 3，\（a_{k+1}\）就是\（a_k\） 出棧后棧頂?shù)臄?shù)據(jù)，因此必然是在棧內(nèi)的數(shù)據(jù)的最上面的一個，或者是棧外的某一個數(shù)據(jù)（進棧再出棧）。

于是由結(jié)論 3 找到判斷序列的方法：逐個檢查序列的每一項\（a_k\），將該項之后的數(shù)據(jù)分為大于該數(shù)據(jù)的大數(shù)集合\（S_g\）和小于該數(shù)的小數(shù)集合\（S_l\），查看是否后續(xù)的數(shù)據(jù)項是小數(shù)集合的最大值或者是大數(shù)集合的任意值，如果不是則不是出棧序列，即若 \（a_{k+1}\in S_g\） 或 \（a_{k+1}=max_l{S_l}\），即是出棧序列。

問題一的解答，就是窮舉長度為 nn 的序列，逐個進行判斷，得到最后的結(jié)果，附上 python 程序。

import math

import itertools

% 輸入序列的長度

n = raw_input（“Input n： ”）

% 判斷是否是出棧序列

def IsNotStackSeq（n_ls， n）：

for k in range（0，n-2）：

% 逐個檢查序列中的每一個元素

ak = n_ls［k］

set_in = n_ls［k+1：］

a_max = ak

% 將ak之后的元素分為大于和小于兩組集合

min_list = ［item for item in set_in if item 》 ak］

max_list = ［item for item in set_in if item 《 ak］

if len（max_list） 》 0：

a_max = max（max_list）

% 后續(xù)的元素是否是小于集合的最大值或者屬于大于集合

if n_ls［k+1］ ！= a_max and （n_ls［k+1］ not in min_list）：

return 1

return -1

def StackSeqList（n）：

n_permation = list（itertools.permutations（range（1，int（n）+1）， int（n）））

n_list = ［item for item in n_permation if IsNotStackSeq（list（item），int（n）） 《 0］

return （len（n_list），n_list）
編輯：hfy