第三章：栈/队列 重点题

1. 栈（Stack）是一种操作受限（只允许在一边进行插入或者删除操作）的线性表，遵循先进后出（也称后进先出）原则 Last In First Out ;

(1) 若一个栈的输入序列是1，2，3…, n ， 输出序列的第一个元素是n ，则第i 个输出的元素是：n-i+1

分析：第一个输出的元素如果是n，证明1～n-1顺序入栈且还在栈中，此时按照栈的特性，后进先出，依次出栈的顺序是：
第二个：n-1
第三个：n-2
第四个：n-3
…
第n个：1
所以第i个输出的元素的按照规律就是：n-i+1

(2) 若一个栈的输入序列是1，2，3…, n ， 输出序列的第一个元素是i ，则第j 个输出的元素是：不确定

该题跟第一题类似，但是因为第一个输出的元素i不确定，自然没法推断第j个输出的元素

(3）若一个栈的输入序列是P1，P2，P3…Pn ，输出序列是1,2,3…n, 若P3 = 1；P1的值不可能是：2

假设P1进，P2进，P3进，P3出（输出1），
按照题目的输出序列，第二个输出的必须是2，此时P3和P1中间隔着P2，所以必须P2出完，P1才能出栈，所以，P1绝对不可能是2，但是从P4～Pn都有可能是2，设 i 属于4～n范围内且Pi=2，则Pi进，Pi出，马上可以得到1，2的输出序列

(4）已知一个栈的入栈序列是1，2，3，4，出栈序列P1，P2，P3，P4，则P2，P4 不可能是：C

A：2，4 B：2，1 C：4，3 D：3，4

A选项，1进1出（P1），2进2出（P2），3进3出（P3），4进4出（P4）即可得P2=2，P4=4
B选项，1进，2进，3进3出（P1），2出（P2），4进4出（P3），1出（P4），即可得P2=2，P4=1
C选项，1进1出（P1），2进，3进，4进4出（P2），