数据结构——栈知识总结_数据结构栈总结

  一、栈

1、栈的逻辑结构

栈：限定仅在表尾进行插入和删除操作的线性表。

空栈：不含任何数据元素的栈。

允许插入和删除的一端称为栈顶，另一端称为栈底。

栈的操作特性：后进先出。

ADT Stack

Data

   栈中元素具有相同类型及后进先出特性，

   相邻元素具有前驱和后继关系

Operation

   InitStack

      前置条件：栈不存在

      输入：无

      功能：栈的初始化

      输出：无

      后置条件：构造一个空栈

DestroyStack

     前置条件：栈已存在

     输入：无

     功能：销毁栈

     输出：无

     后置条件：释放栈所占用的存储空间

Push

     前置条件：栈已存在

     输入：元素值x

     功能：在栈顶插入一个元素x

     输出：如果插入不成功，抛出异常

     后置条件：如果插入成功，栈顶增加了一个元素

Pop

    前置条件：栈已存在

    输入：无

    功能：删除栈顶元素

    输出：如果删除成功，返回被删元素值，否则，抛出异常

    后置条件：如果删除成功，栈减少了一个元素

GetTop

    前置条件：栈已存在

    输入：无

    功能：读取当前的栈顶元素

    输出：若栈