4.3 栈的抽象数据类型

对于栈来讲，理论上线性表的操作特性它都具备，可由于它的特殊性，所以针对它在操作上会有些变化。特别是插入和删除操作，我们改名为push和pop，英文直译的话是压和弹，更容易理解。你就把它当成是弹夹的子弹压入和弹出就好记忆了，我们一般叫进栈和出栈。

ADT 栈(stack)
Data
    同线性表。元素具有相同的类型，相邻元素具有前驱和后继关系。
Operation
    InitStack(*S): 初始化操作，建立一个空栈S。
    DestroyStack(*S): 若栈存在，则销毁它。
    ClearStack(*S):将栈清空。
    StackEmpty(S):若栈为空，返回true，否则返回false。
    GetTop(S, *e):若栈存在且非空，用e返回S的栈顶元素。
    Push(*S, e):若栈S存在，插入新元素e到栈S中并成为栈顶元素。
    Pop(*S, *e):删除栈S中栈顶元素，并用e返回其值。
    StackLength(S):返回栈S的元素个数。
endADT

由于栈本身就是一个线性表，那么上一章我们讨论了线性表的顺序存储和链式存储，对于栈来说，也是同样适用的。