文章目錄

• • 1 引例
  • 2 做題方法
  • 3 原因
  • • 3.1 選項(xiàng)D（4 3 1 2）的模擬

1 引例

（例）設(shè)棧的入棧序列是 1 2 3 4，則下列不可能是其出棧序列的是（ ）。
A. 1 2 4 3
B. 2 1 3 4
C. 1 4 3 2
D. 4 3 1 2
E. 3 2 1 4

一般人看到此類題目，都會(huì)拿起草稿紙，將各個(gè)選項(xiàng)都模擬一遍選出正確答案
這當(dāng)然可以得出正確的答案 （D ）
但當(dāng)元素個(gè)數(shù)過(guò)多的時(shí)候，這個(gè)方法不可取，而且，這種人工模擬過(guò)程浪費(fèi)時(shí)間且容易出錯(cuò)，下面將介紹一種簡(jiǎn)單的做題方法。

2 做題方法

按順序入棧的序列，任意元素 e ，比 e 先入棧的元素，并且比 e 后出棧的元素，一定是逆序的。

讀起來(lái)有點(diǎn)繞口，那么先記下 “ 后出先入逆序 ”

1、以最上面的例題為例，若要寫出所有以 1 2 3 4 為入棧順序的出棧序列
暴力求解：4個(gè)元素一共有 $A_4^4$ 共24種排列（下表加粗斜體的排列為合法排列）

1234	1243	1324	1342	1423	1432
2134	2143	2314	2341	2413	2431
3124	3142	3214	3241	3412	3421
4123	4132	4213	4231	4312	4321

表格中加粗斜體的排列為合法排列一共有 14 個(gè)
現(xiàn)在可以隨意選一個(gè)序列來(lái)理解一下什么是 “ 后出先入逆序 ”
比如序列：3 1 2 4

選擇任意元素 e ，這里選擇 3

比 3 后出棧的有三個(gè)元素 1 2 4

其中比 3 先入棧的有兩個(gè)元素 1 2

但是 1 2 是正序的，而不是逆序的

所以這個(gè)序列不是合法出棧序列

（注：可以利用遞歸設(shè)計(jì)出相應(yīng)的算法來(lái)判斷所有合法序列）

2、若只要求出一共有多少個(gè)合法出棧序列

將元素個(gè)數(shù)替換 n 計(jì)算即可，計(jì)算得 14
該公式稱為卡塔蘭數(shù)（Catalan number）公式，了解更多 點(diǎn)這里

注：上式中的括號(hào)上下兩個(gè)數(shù)（2n和n）代表數(shù)學(xué)中排列組合公式中的C上下兩個(gè)數(shù)，即用組合公式來(lái)求即可。

3 原因

3.1 選項(xiàng)D（4 3 1 2）的模擬

1、將 1 2 3 4 順序依次入棧：

2、彈出棧頂元素 4：

3、彈出棧頂元素 3：

接下來(lái)?xiàng)?nèi)只剩下元素 1 和 2 ，并且 2 在棧頂
所以說(shuō) D （4 3 1 2） 選項(xiàng)的出棧順序最后的 1 和 2 是無(wú)法完成的

可以發(fā)現(xiàn)：
如果把最后兩個(gè)元素的順序逆置一下，就可以完成了

總結(jié)

以上是生活随笔為你收集整理的栈 - 关于出栈序列，判断合法的出栈序列的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。