经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » C 语言 » 查看文章
关于数据结构的学习笔记——栈的基础知识
来源:cnblogs  作者:洛阳勿恋  时间:2021/5/6 18:01:54  对本文有异议

三、栈

3.1 栈

3.1.1抽象数据类型栈的定义

:限定仅在表尾进行插入或删除操作的线性表;表尾端称为栈顶,表头端称为栈底。不含元素的空表称为空栈

特点:进栈操作:栈底元素先进栈,栈顶元素后进栈;

出栈操作:栈顶元素先出栈,栈底元素后出栈;

总结:栈的修改是按照后进先出的原则进行的。

3.1.2 栈的表示和实现

顺序栈链栈

顺序栈:利用一组地址连续的存储单元依次存放自栈底栈顶的数据元素,同时,附设指针top指示栈顶元素在顺序栈中的位置。

通常栈空表示为:top=0;

但是,一方面,如果以C语言作为描述语言时,C语言中的数组下标约定从0开始,这样设定(top=0)会带来很大不便;

另一方面,由于栈在使用过程中需要最大空间的大小很难确定,所以,在初始化栈空时,不应该限定栈的最大容量。

比较合理的做法为:

  1. 先为栈分配一个基本容量

  2. 在应用过程中不断扩大栈的容量空间(栈的空间不够时)

做法:设两个常量STACK_INIT_SIZE(存储空间初始分配量)、STACKINCREMENT(存储空间分配增量)

 

typedef struct{
    SElemType *base;
    SElemType *top;
    int stacksize;
}SqStack;

 

若base的值为null,则栈结构不存在;

栈空标记:top=base;

链栈:……

原文链接:http://www.cnblogs.com/zw-521/p/14687783.html

 友情链接: NPS