CSP2021初賽真題講解

2014年，CCF推出CSP認證 （Certified Softwmare Professional， 軟件能力認證），以評價計算機專業人士或準專業人士計算機科學的基礎能力——算法和編程能力。CSP每年舉辦3次，現已成為一些企業及許多大學評價計算機專業大學生專業能力的重要工具。

這是CSP2021初賽的一道選擇題：

對于入棧順序為a， b， c， d， e的序列，下列（）不是合法的出棧序列。

A. a，b，c，d，e

B.e，d，c，b，a

C.b，a，c，d，e

D.c，d，a，e，b

棧（stack）又名堆棧，它是一種運算受限的線性表。其限制是僅允許在表的一端進行插入和刪除運算。這一端被稱為棧頂，相對的，把另一端稱為棧底。向一個棧插入新元素又稱作進棧、入棧或壓棧，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素;從一個棧刪除元素又稱作出棧或退棧，它是把棧頂元素刪除掉，使其相鄰的元素成為新的棧頂元素。

進棧出棧就像一個盒子，先一個個放入盒內，而拿出的時候只有先從上面拿，才能再拿下面。入棧的順序規律是排在前面的先進，排在后面的后進。出棧所遵循的原則是“先進后出”，基于這個原則可以引出一類問題，即出棧序列問題。

解析順序的問題，如果學過編譯原理，比較容易理解，解析格式的時候，是用堆棧的，遇到一個格式描述符，就壓棧，遇到一個變量，就出棧，就有了這樣的表現。

同線性表一樣，也有兩種方式來存儲棧，一是順序存儲，二是鏈式存儲。對于順序存儲，大家自然能想到的是利用數組。但數組的容量不易擴張，加上棧在使用過程中所需的最大空間大小很難估計，因此，合理的做法是：先為棧分配一個基本容量，然后在應用過程中，當棧的空間不夠時，再逐段擴大。因此需要為棧尋找一個地址標志來定位，即棧尾指針，同時用棧頂指針來表示棧元素的存取情況。

回到這個問題，依據“先進后出”的規則，需要出棧元素的要最后進棧。

選項A合法，a入棧a出棧;b入棧b出棧;c入棧c出棧的順序依次進行。

選項B合法，a，b，c，d，e依次入棧;e，d，c，b，a依次出棧。

選項C合法，a，b入棧，b，a出棧;c入棧c出棧;d入棧d出棧;e入棧e出棧。

選項D不合法，根據要求c要出棧，那么就需要a，b，c入棧，c出棧，此時棧中剩b，a;d入棧d出棧，此時棧中剩b，a;接下來需要a出棧，但是現在a上面還有b，所以D不合法。

選D。