大话数据结构-4.2 栈的定义 89- 高飞网

4.2 栈的定义 89

2016-12-17 00:54:37.0

4.2 栈的定义

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

    我们把允许插入和删除的一端称为栈顶(top),另一端称为栈低(bottom),不含任何数据元素的栈称为空栈。栈又称为后进先出(Last In First Out)的线性表,简称LIFO结构。

    栈的插入操作,叫作进栈,也称压栈、入栈;栈的删除操作,叫作出栈,也叫弹栈。

    举例:现有3个整形数字元素1、2、3,依次进栈,会有哪些出栈次序呢?

  1. 1、2、3进,3、2、1出,即321
  2. 1进、1出,2进、2出,3进、3出,即123
  3. 1进、2进,2出,1出,3进,3出,即213
  4. 1进,1出,2进,3进,3出,2出,即132
  5. 1进,2进,2出,3进,3出,1出,即231

    但不可能为312,因为如果3出栈了,则3应先进栈,既然3进栈了,则1,2也应进栈,而1进2进的次序,出栈2应在1的前面,因此不会有312这个情况

4.3 栈的抽象数据类型

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