4.3　栈的抽象数据类型

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

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

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