栈是数据结构中比较重要的知识点，也是程序设计常用的一种数据结构，在历届的信息学竞赛中，栈的操作和存储方式一直作为重点考核内容。由于栈采用“先进后出”的特殊存储方式，给定入栈序列（操作），求出栈序列（操作），在历届的信息学初赛试题中几乎每年都出现，我们将依次进行分析。
一、给定入栈序列和首个出栈记录，求某个出栈记录
    例1(第7届 选择20) 若已知一个栈的入栈顺序是1，2，3，…，n，其输出序列为P1，P2，P3，…，Pn，若P1是n，则Pi是(   )
　A.i 　B.n-1 　C.n-i+1 　D.不确定
    分析：由于栈采用先进后出的存储方式，由题意“若P1是n”可知，出栈操作是在所有元素进栈后进行的，因此存在P1=n，P2=n-1，……，Pn-1=2，Pn=1。
    设Pi=m，通过以上等式，不难发现其中规律i+m=1+n=n-1+2=……，因此m=n+1-I，故答案为C。
    与该题类似的还有第9届选择17题，以队列为存储结构。
    例2(第9届 选择17) 已知队列(13，2，11，34，41，77，5，7，18，26，15)，第一个进入队列的元素是13，则第五个出队列的元素是(   )。
    A.5   B.41    C.77    D.13      E.18
    分析：因此由题意第一个进入队列的元素是13，记为P1=1，表示入队的第一个元素，和栈结构不同的，队列采用“先进先出”的存储特点， 因此分析Pi=i，表示是第i个入队元素，故本题答案为41，选B。
    由上两题可见，若求其中一个指定的出栈记录，给出条件必须是出栈的首个元素是最后一个入栈的记录，否则求其第i个出栈元素将不确定，但可以求出该在状态下，出栈序列的多种情况，结合排列组合知识，题目难度有所增加。此类型题目在第8届试题中出现，具体见下。
    例3(第8届 问题求解1) 如下图，有一个无穷大的的栈S，在栈的右边排列着1，2，3，4，5共五个车厢。其中每个车厢可以向左行走，也可以进入栈S让后面的车厢通过。现已知第一个到达出口的是3号车厢，请写出所有可能的到达出口的车厢排列总数(不必给出每种排列)。
出口← ←  1    2    3    4    5
 ↓ S 
    分析：该题将栈的应用结合排列组合知识考察考生。
    由题意“已知第一个到达出口的是3号车厢”可知第1个出栈的是3，即该状态下1、2还在栈内，因此到达出口的所有排列中，2必须在1之前，运用排列组合的知识，确定2、1的排列顺序共有P（4，4）/P（2，2）=12，但其中还应除去当5在第2个到达时，即4在栈中的状态下的不符合的排列顺序，共有两种状态：其一是421的状态，除去不合法的排列：241，214，其二是41的状态，除去14的状态。因此综合以上，该问题求解的答案为：P（4，4）/P（2，2）-C（1，2）-C（1，1）=9。具体排列为：
32145，32154，32415，32451，32541；34215，34251，34521；35421。
二、给定入栈操作，求出栈顺序
    例4(第10届 选择14) 某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。已知某时刻该车站状态为空，从这一时刻开始的出入记录为：“进，出，进，进，出，进，进，进，出，出，进，出”。假设车辆入站的顺序为1，2，3，……，则车辆出站的顺序为(   )。
    A. 1, 2, 3, 4, 5   B. 1, 2, 4, 5, 7   C. 1, 3, 5, 4, 6   D. 1, 3, 5, 6, 7   E. 1, 3, 6, 5, 7
    分析：根据题意，用下表表示记录出栈入栈操作，出栈操作选择入栈集合中最近的一个记录（即后进先出），写在出栈序列中，并把该记录从入栈集合中删除。
    操作 进 出 进 进 出 进 进 进 出 出 进 出
    入栈 1  2 3  4 5 6   7 
    出栈  1   3    6 5  7
    因此根据出栈序列，依次分别为1，3，6，5，7，答案为E。
    与该题类似的还有第12届选择13题。
    例5(第12届 选择13) 某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。已知某时刻该车站状态为空，从这一时刻开始的出入记录为："进，出，进，进，进，出，出，进，进，进，出，出"。假设车辆入站的顺序为1，2，3，……，则车辆出站的顺序为(   )。
A. 1, 2, 3, 4, 5   B. 1, 2, 4, 5, 7   C. 1, 4, 3, 7, 6   D. 1, 4, 3, 7, 2 与上题分析类似，解得该题答案为C。
三、给定入栈序列，求不可能（或可能）的出栈序列
    例6(第11届 选择20) 设栈S的初始状态为空，元素a,b,c,d,e,f,g依次入栈，以下出栈序列不可能出现的是(   )。
   A.a,b,c,e,d,f,g   B.b,c,a,f,e,g,d   C.a,e,d,c,b,f,g   D.d,c,f,e,b,a,g   E.g,e,f,d,c,b,a
分析：该类题目主要考察入栈操作和出栈操作对出栈序列的影响，若单个元素入栈后，又出栈，不影响出栈序列，快速地选择该题的主要方法就是检查间隔不连续元素必须以逆序方式输出全部元素，如出栈序列的前三个为a,b,f,则可知c,d,e入栈，在后续的输出序列中必须保持e,……,d,……,c的顺序，即e必在d前，d必在c前，否则为不可能的序列。
    运用该方法，依次检查选项中跳过的多个字符，如C选项中，a后输出的字符为e，中间跳过了d,c,b,在出栈序列中必须保持d……c……b的序列，查看其后出栈序列，符合要求。在E选项中，首个出栈的字符为g，表示a,b,……,e,f,都在栈内，则其出栈的正确序列应该为f,e,……,b,a，在该选项中的e,f顺序错误，即不可能出现的出栈序列。因此答案为E。
    例7(第12届 选择19) 设栈S的初始状态为空，元素a, b, c, d, e 依次入栈，以下出栈序列不可能出现的有(   )。
A. a, b, c, e, d   B. b, c, a, e, d   C. a, e, c, b, d    D. d, c, e, b, a
    与上题分析类似，本题答案C。
    栈作为一个特殊的存储结构，在很多实际问题中的求解过程中就利用了其“先进后出”的特点，这首先要求考生平时注重基础知识的积累，愿以上分析可以给考生带来一些启示。