数据结构——栈

    1.栈是什么？

    现在城市的车越来越多，比方说，你晚上开车九点钟回家，如果没有车位的话，把车堵在外面，挡在明天不走的车前面。

    示意图就是这样：

        很显然，假设车头在右边，c1是最先进的，但是，c1要等到c5、c4、c3、c2先全部出来以后，才能出来，所以，栈这个线性结构具有一个非常实用的特性——先进后出，这让stack成为做题的非常实用的工具。

        你可以把这个stack想象成一个“死胡同”，只要你前面的元素不出来，或不被“pop”掉的话，你就不会被读取，就像你在一个箱子里拿小包袱一样。

      栈的定义如下：

        首先 系统或者数据结构栈中数据push和pop 是两回事！

        插入是增加数据 弹出 是删除数据 ，这些操作只能从栈顶即最低地址作为约束的接口界面入手操作 ，但读取栈中  的数据 是随便的 没有接口约束之说。很多人都误解这个理念从而对栈产生困惑。而系统栈在计算机体系结构中 又起到一个跨部件交互的媒介区域的作用 即 cpu 与内存的交流通道 ，cpu只从系统给我们自己编写的应用程序所规定的栈入口线性地读取执行指令， 用一个形象的词来形容它就是pipeline。

        cpu内部交互具体参见 EU与BIU的概念介绍。（转自360）
        栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶。

        需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针

        栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；

        栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。

        插入一般称为进栈（PUSH），删除则称为退栈（POP）。栈也称为后进先出表。

 第二天：

2.栈的操作函数

      栈的操作函数？系统提供吗？还是要自己写一个stack（栈）的模板类？

        STL是一个功能特别强大的东西，但你肯定不能偷偷摸摸去调用它的public函数，当然首先要#include<数据结构名>，本章中，是#include<stack>，其中包括了stack需要使用的绝大部分的函数。

       定义：

                定义方法如下：

                                         stack<int/char/bool....>  s/*（stack名称，当然了，不一定是s）*/;

                还可以这样定义：

                                         char/int/bool.....  s[10000];//模拟一个栈

        主要函数：

                  1.    s.push（int/char...... n）:

                         功能正如push一样，就是把一个元素推入栈中，也就是推入现在深度最深且有位置的那个位置

                    注意事项及运行过程：

                   ①若TOP≥n时，则给出溢出信息，作出错处理（进栈前首先检查栈是否已满，满则溢出；不满则②）；
                   ②置TOP=TOP+1（栈指针加1，指向进栈地址）；
                   ③S(TOP)=n，结束（n为新进栈的元素）；

                  2.     s.pop（）:

                            pop：弹出，顾名思义就是弹出栈顶的元素，为动作函数，随即top减一。

                  注意事项及运行过程：

                 ①若TOP≤0，则给出下溢信息，作出错处理(退栈前先检查是否已为空栈， 空则下溢；不空则作②)；
                 ②X=S(TOP)，（退栈后的元素赋给X）：
                 ③TOP=TOP-1，结束（栈指针减1，指向栈顶）。

                  3.    s.size（）

                             这个当然是返回栈的大小了。

                  4.    s.top（）

                             这个函数正好跟pop函数相反，它用top指针访问栈顶元素，但不弹出。

                  5.    empty()

                             判断栈是否为空，真则返回1，反之返回0

                  操作实例：

                  stack<int> s;

                       操作        |                          栈                                        | 输出

                  empty()     |                                                                      |  true

                  push（7） |   7                                                                 |    无

                  push（2） |   7   2                                                            |    无

                  top （）     |   7   2                                                            |     2

                  pop（）     |   7                                                                  |     2

                  empty（）|   7                                                                  |  false

                  size（）     |   7                                                                  |      1