数据结构和算法研究-栈

栈ADT

栈模型

_栈（stack）_是一种仅允许在某一端执行插入和删除操作的数据结构，在计算机科学中具有重要地位。这一特定位置被称为栈顶（top）。关于栈的基本操作主要有两种：Push操作用于将元素放入栈中以及Pop操作用于从栈中取出最新插入的数据。为了方便获取最新存入的数据还可以预先调用Top函数在其前执行一次Pop操作。对于空栈而言若进行Pop或Top的操作通常被视为违反了该数据结构抽象定义。另一方面当一个Push操作导致内存溢出的情况则属于实现层面的问题并不涉及数据结构本身的抽象定义范畴

栈也被称为 LIFO（Last In First Out） 表。
通常情况下，在一个栈模型中会存在处于栈顶端位置的一个元素；其特点是该位置上的唯一一个元素为整个结构中唯一可见的。

栈的实现

栈的链表实现

首先，给出一些定义。实现栈要用到一个表头。

    #ifndef _Stack_h
    #define _Stack_h
    
    typedef int ElementType;
    struct Node;
    typedef struct Node *PtrToNode;
    typedef PtrToNode Stack;
    
    int IsEmpty( Stack S