栈

栈的抽象数据类型

顺序栈的抽象类型

1
2
3
4
5
6
#define MAXSIZE 100
typedef struct{
   SElemType *base; #底边指针
   SElemType *top; #顶指针，指向栈中最后一个元素的下一位
   int stakesize; #栈的可用最大容量
}SqSack;

顺序栈的一些算法

  • 判断是否为空
    • S.top == S.base ? true : false;
  • 栈长度
    • return S.top-S.base;
  • 清空栈
    • if(S.base){S.top=S.base}
  • 删除栈
    • if(S.base){delete S.base; S.stacksize=0;S.base=S.top=Null}
  • 压栈
    • 判断是否满了->栈顶上移，写入e（*S.top=e;S.top++;）
  • 出栈
    • 判断是否为空->获取栈顶元素->栈顶下移

链栈的抽象数据类型

只能在链表头部进行操作的特殊链表

特点：

  • 不需要头节点
  • 头指针就是栈顶
  • 空栈就是头指针指向空
  • 插入和删除仅发生在栈顶

算法

  • 入栈
    • 新建一个节点，指针域指向上次的栈顶，修改栈指针
  • 出栈
    • 头指针指向下一位，返回上次的*S.top

栈与递归

递归

如果一个对象部分地指向自身，或用自己给自己定义，那么他就是递归的

如果一个过程直接的或者间接的调用自身，那这个过程是递归的过程

递归工作栈

在函数嵌套调用或者递归时，所有进行中的函数都被保存在栈内存中

递归的优缺点

  • 优点是程序简洁易读
  • 缺点是每次调用要生成记录，保存状态信息，稍后要取出状态信息，时间开销大。