大家好。
今天我们学习数据结构与算法第三章，
栈与队列的内容，今天我们首先介绍栈。
栈它是一种受限制的数据结构，它的操作
是限制在同一端进行，那么还有一种受限的数据结构，也就是队列。
它的操作呢，是插入在一端，删除在另一端。我们在后面一讲会
介绍到。那栈的定义呢，
那它实际上是一种后进先出，或者叫先进后出的一种数据结构。
那，也可以简称为LIFO。它的主要操作呢，就是进栈出栈。
那栈的应用非常的广泛, 例如在表达式
求值，还有，在我们编译里面对函数的
这些运算，那我们还有是对递归的处理我们都可以用到栈。
在我们后续的一些复杂数据结构，也就是树和
图里面，我们也可以用到栈来进行深搜的操作。
栈的抽象数据类型，除了上面介绍到的
它的逻辑结构以外，然后我们的主要的运算来说，我们就是
压栈和出栈这样的操作，另外还有一个，读栈顶的操作。
我们来看一个火车进栈的例子。
那如果是说有一些火车，1，2到n，它是顺序入栈，那么我们经过这个栈的调度，
它的合法出栈序列是什么？显然1-2-3-4-5，然后5-4-3-2-1都是合法的序列。
那我们来判断一下，这个序列它是不是合法的呢？3-4-1-2。
那我们来判断它是否合法，首先我们用构造的方法 。
如果是3需要出栈的话呢，那
它是要在1、2、3都进栈的情况下它第一个出来。
然后我们要求4是第二个出来，所以4
也进栈，然后再出栈。接着我们要求1
要是出栈的序列，但是它被2给压住，这样一个后进先出的结构下，
它是不能够读出来的，因此它是个非法序列。那我们思考一下，
如果进栈序列是1-2-3-4，那么它的可能的出栈序列是哪一些呢？
实际上，我们还可以看一下这个思考题。
实际上通过这个思考题呢，我们能够更透彻地理解这个出栈的，
它的一个顺序，有哪些要素。那我们如果是1，2到n
这几个数字它顺序入栈，那如果是它的出栈序列呢，实际上是
一个排列了，就是p1到pn，那么这个排列里面，刚才我们也看到，有些是可能是非法的。
那么，我们问，如果是说，有那么下标i，j，k，
那就是i小于j小于k，那他能不能得到这么一个出栈的序列，
也就是pj，pk，pi，那么就是分别是这样的pj小于pk小于pi。
举个例子，也就是说，我们对于这样的，比如说1，2，3
这样的入栈的顺序，我们能不能够得到3，1，2这个序列呢？
好，那我们看栈的实现，它显然也是顺序栈
和链栈这两种，其中顺序栈特别要注意上溢和下溢的这个问题。
我们看一下顺序栈的内定义。那顺序栈
里面呢，我们实际上是需要用一个数组来表示这个栈的元素。
另外呢，就是栈顶指针，还有因为它是顺序栈，我们需要有一个预存的一个
比较大的空间来给它，因此，有一个这个栈的空间的最大的数值。
那我们看一下演示这个顺序栈，那我们这个栈顶
它是随着我们元素的变化而发生变化的，例如我们往上增长的话，这栈顶是
往上去变化。那么，这个栈底呢，它是不变的。
顺序栈的上溢和下溢问题，我们刚才已经介绍过。
那我们在后面呢，它的一些相应运算，也就是
push和pop的时候，就特别要注意上溢下溢的问题。
那例如我们这个push操作，那我们首先要判断它是不是栈
已经满了。如果满了的话，就是一个上溢出，那否则的话呢，我们就把这个元素存进去，而且修改栈顶元素。
我们出栈的话呢，就是判断下溢的问题。如果没有
下溢的话呢，那我们就是把这个栈顶的这个数值呢，
读出来，然后呢就是要修改这个栈顶指针。
链式栈呢，我们往往就采用单链的形式来存储。
单链的话，我们直接从栈顶往下去链接。大家注意这个链接的形式。
它非常好处理，那我们加入一个新元素，就在栈顶
把这个新元素连上，然后删除的话，把这个栈顶给删掉，然后再修改这个栈顶的指针。
我们看一下这个
链式栈它的一个类的定义，实际上是就说， 它这个创建的过程。
那我们在开始的时候，就是链式栈的话，它的栈顶就是空，然后整个栈的
大小是0。因为这个大小的话呢，我们要，我们有些应用
我们可能需要知道栈它里面有多少个元素。另外呢就是跟我们刚才的顺序栈也对应，
我们大概能够了解这是栈里面有效的元素值。
我们看一下这个，对于链式栈，它的压栈操作。
那么因为我们这边是调用了一个new link，也就是new是这个节点，
这样一个运算。在new这个节点时候，我们这边item是
存的这个值。然后top呢就是，原来的那个栈顶元素。我们可以看，
这个link本身呢，它，它是把这个新生成的这个节点，
它的next域呢，就指向了我们传进来的这个top。
这是参数，因此呢它就已经链好了，然后呢，就是，栈的大小呢是加1的。
我们top当然要修改为新的，这样的一个栈顶。
从链式栈里面弹出一个元素的话呢，我们就是
直接地把这个栈顶的元素给读出来，放到一个临时的变量里面。
然后呢，同时把这个栈顶指针呢，指向
原来的这个第二个元素，也就是栈顶已经弹出去了。
顺序栈和链式栈，它们在
时间效率上都是非常好的。都是常数时间，也就是大于1的时间。
因为它们是在底层的运算，要支持上层的很多操作，必须是快速的完成的。
空间效率来说呢，因为就是链栈它长度
可变，但是它会，因为指针的原因，它会增加一些结构性的开销。
而顺序栈呢，如果是说它的最大的规模我们
可以预计的情况，因为它是用数组来实现的。 非常好操作，所以在实际的应用中，
我们其实是更多的用到顺序栈。
特别要注意呢，在一般的情况下，栈它
只能够是受限的操作，这个操作主要是插入删除。
但是有时候你要读元素，我们也只能读栈顶元素。大家注意，
不要到栈里面去读它的内部的元素的内容，这就是信息的封装性。
思考一下， 关于STL里面栈的函数，我们看到，
STL里面有那个top和pop两个这个函数。
那为什么它要把这个两个操作呢，是分开的？因为我们有的时候，我们经常是
读出栈顶元素，同时呢，我要把这个元素弹出去。
那么我们为什么不设一个ptop，这样一个就是同时读完又把它弹出来呢？
栈的应用，
是因为它的后出先进，那也是
这样的一个原因，那我们经常是用来
给它处理具有递归结构的这样的数据。在深搜里面有很广泛的应用。
还有就是我们说道的，在编译里面，对于子程序，函数它的求解。 那我们会在这一讲讲一下表达式求值，特别是后缀表达式
的这样一个问题。另外呢，就是下一讲我们会讲一下利用栈来消除递归。
计算表达式的值，那这样一个中缀表达式是我们常见的
四则运算。那后缀表达式呢，它主要的就是，把运算符放在后面。
而操作呢，是碰到了这个运算符则拿出前面的
相应的两个操作数来进行计算。然后算出来的结果又
占住这个原来的这几个相应的操作符和操作数的位置，然后继续进行这个扫描和计算。
中缀表达式我们可以看，其实就是我们在
小学的这个数学里面的，或者是算数里面的四则运算。
那它通过这个括号呢，能够改变优先级它的这个运算符号是在中间的。
我们在后面学到二叉树， 大家可以再回顾到这儿来看，就是说，实际上是对这样的一个表达式
二叉树它的一个中序遍历。当然需要注意这个运算优先级的时候呢，
就是要考虑加上括号，那我们这里就不展开了。
中缀表达式的语法公式，我们可以用这个
巴克斯范式来定义的话，它其实是一个递归的过程，大家可以看到。
也可以通过这个图示的方法来看，它其实是递归的展开的，
就是，表达式呢，它是由项和因子来组合成的。
后缀表达式，它的运算的符号呢，它是
在这个数值的后面，就是操作数的后面，
那实际上通过单遍的扫描，而且不需要
括号，我们就可以求出这个表达式的值。
所以它是非常方便的。在我们这个，
相应的它在表达式二叉树里面，后缀表达式
实际上是对表达式二叉树的一个后序遍历，
而且是完全不需要考虑括号的问题。表达式二叉树，
它的一个语法图，还有就是他的
语法的公式集，就是我们刚才所见的这样的一个表。
那表达式的计算呢，我们对于后缀表达式，我们来看一下。
它的计算特点会是什么样的？ 然后呢他们的异同是什么？那他们的运算数的出现顺序是一样的。
主要不同就是他们的符号这个出现的顺序是不一样了。
那我们看待处理的这么一个表达式。那
我们遇到的操作数呢，都直接进栈。
遇到符号，我就拿出栈里面的两个数来进行操作。
那么我们一直重复这样的一个过程。最后呢，一直到这个表达式，
整体的值都求出来了为止。
后缀表达式的求值过程，
我们可以总结一下，实际上，它就是这个算法思想就是这样的，我们刚才已经都介绍过了。
就是遇到操作数，则压入栈；遇到一个运算符，从栈中取出两个元素
进行操作，而且把结果放到栈里面，这样一直继续，一直到这个表达式处理完为止。
我们来看一下，
我们这个后缀表达式，我如果是给它设计一个计算器，
那我们主要的操作，就是我刚才说，首先是读这个数据。如果他是个合法表达式的话。
我们从栈里面读数据的话，我应该是一次就是取出两个，
然后呢，就是计算。遇到符号的话呢，我就是去读这个数据的计算，然后结果再放回到栈里面。
我们看它的计算过程。
那读数的这个操作很简单，但是我们要注意，就是
我们哪一个是左操作数，哪一个是右操作数，就后面那个是左操作数，
前面那个是右操作数。然后，我们这个计算的过程呢，就是
如果是要，要算这个值，就是我们碰到了一个
运算符，我们要算这个值，那我取出两个元素，然后根据这个
运算符加减乘除我们分别来进行计算。
然后计算的时候呢，要注意 就是对于被0除的情况要做一个异常处理。
整个处理表达式的这个过程，它实际上就是，对于这个
标准输入里面的这些数值，然后我就是逐个去读。
我们统一的，就是先来把它读到一个
这个字符型的变量里面。我们如果遇到了等号呢，就是表示运算结束。
否则呢，我们来看这个符号，它是不是
操作符。如果是操作符呢，我们就是
从栈里面拿出两个数据，然后进行计算。计算完了以后把这个数呢，
结果呢乘回去。如果是，
不是这种符号的情况，那就是数值。
那么，如果是数值的情况，因为它前头已经被读了一个了，因此呢这个时候要注意，
把这个提前读出来的这个数呢，要放回去。然后下次读，就可以读到完整的，
这个数。否则的话呢，就被吃掉了这个第一个数，而读出来是错误的值。
最后我们留一些思考题。
也就是，栈我们往往是用单链实现的。
那我们是不是能够用双链来实现呢？那哪一个更好呢？
还有一个，就是我们刚才举的例子是，
后缀表达式，那我们相应的也可以有一个
前缀表达式，那我们对前缀表达式我们研究一下，看看它有哪些性质， 以及它的求值过程是怎么样的。
谢谢大家。