栈与队列-之出栈和入栈_入栈和出栈

·栈的概念：
-运算只在表的一端进行，一般线性表而言，插入删除都可以在任意一个位置进行的
·队列：入栈和出栈只能分别在两端中的一边，就是说它在一端入队列，在另外一端当中去出队列。从某种意义上讲栈和队列也是一种线性表，但是操作是受限的

栈的逻辑结构：
·后进先出或者说先进后出的一种限制访问端口的线性表
·主要操作
-进栈、出栈
·应用
-表达式求值
-消除递归
-深度优先搜索

栈的抽象就像一个玻璃瓶，后来进入的元素会把压入瓶底。
给出抽象定义，在抽象定义当中它的基本操作包括push pop top ,
pop就是说如果要返回栈顶，并且把栈顶的元素弹出，把这个球弹出来；

top是说它只访问栈顶的这个球是什么东西，是哪个球。但是并不把最上面的那个球给弹出来，后面有两个判定性的这个函数

以火车进站为例：
例如像以前这种比较传统的火车站的例子，这个车站中有一个车轨，有很多车要到这里面来进行进栈。
只有这一个车轨，所以它先进来的车要等后面进来的车出去以后，第一辆车进来是1，假设鱼贯进入了12345五辆车，那么它要出站的时候就是54321，54321去出栈。

实际的举例方式：
给个例子，假设1入栈发现第一个出栈的是3，所以1这时候并不出栈，所以2入栈.
因为第一个出栈的是3，所以2也不出栈.3入栈，3入栈以后马上就出栈。为什么，因为第一个出栈是3，所以说3出栈。
4入栈，4入栈以后4出栈，我们发现有1它要求的出来的顺序是1和2，我们发现这是不可能的，因为2这个小球把1的小球压在底下，所以2要先出栈，1要后出栈。
对这个例子而言，可以这样理解，如果入栈的顺序是1234的话，不可能出现一个3412的出栈顺序。有可能出现3421的顺序是可以的，这地方讲入栈顺序是1234，并不意味着1234都是鱼贯地进入这个栈里面来，可能1进来以后，2进来以后，3进栈以后马上出栈。不是说3入栈以后4一定要入栈。

给定一个1234的入栈顺序，哪些出栈顺序是合法的，那些是不合法的？

解这个题给出一个引理：给定一个入栈顺序，假如1234这样入栈顺序，设k最后一个出栈的，那么k把入栈序列一分为二，在k之前入栈的元素一定在k之后入站元素要提前出栈。

什么含义，假设我有个入栈序列，出栈序列k是最后一个入栈的，那么k就会把原来就可以去扫描这个入栈序列，k就可以把入栈序列分成左边和右边。
两部分也就是在k之前入栈的，和在k之后入栈的。
结论是说在k之前入栈的元素，一定要在比k之后入栈的元素要提前出栈，所以3的序列是错的。
3是最后一个出栈的，3就会把它分成1 2和4，也就是1 2的出栈一定要在4之前。我们发现1 2的出栈在这例子当中1 2的出栈并不是在4之前，例如这2的出栈，就不在4之前了，所以这是不对的。
按照这个定理的话判断一下只有这一个是错，其他都是对的。注意到这个地方只是判定的最后一个元素，其实可以迭代地去判断子序列出栈是不是正确的

如何迭代的区分析一个入栈序列的出栈序列：
假如把这一个元素判断完以后，看另外一个例子叫1 3 4 2，2是最后一个出栈的，所以2九八序列分成1和3 4两部分，显然1是在3 4之前的，就是1和3 4之间的这个整体顺序是对的，那么3 4的出栈顺序对不对？就相当于对这个子序列就是3 4和3 4这个子序列再掉用这个定理去判定一下，给定这样一个3 4入栈顺序，是有可能得到3 4这样一个出栈顺序。所以我们利用这个引理写一个递归的这样一个程序来判定这个出栈顺序是否合法。

给定一个入栈顺序，入栈顺序的长度是N，出栈序列有多少种？

(1)假设有N，整个长度是n，对应于任何一个元素，x是其中的任何一个元素，这个x假设是第x的元素，系列是从第0个开始，到前面x减1个，显然前面是x个元素，这个元素是第x加1个，按下标的话是x，但是排在第x+1个因为是从0到x-1。剩下的N-1-x的元素

(2)我们设它有f（N）个出产序列，写出一个递归式子，N个元素它的出栈顺序有N种，按照刚才的定理如果这个出栈，这个x是最后一个出栈的，在它之前的这些元素一定是在它之后的这些元素之前提前出栈。也就是说左边的和右边的出栈顺序的整体出栈顺序它们之间的逻辑关系是确定的，左边的出栈序列有多少种，有f(x)种。
右边f(N-1-x)个，因为它两个之间的整体出栈顺序是确定的，内部的出栈顺序是不定的，所以它们俩是一个乘法原则。
（3）同时这个x是可以从第0个元素一直到n-1个元素，这个公式就是上面的公式，是一个比较典型的离散数学里面讲的叫Catalan数。