关于数据结构的学习笔记——栈的基础知识
程序员文章站
2022-06-16 19:53:04
三、栈 3.1 栈 3.1.1抽象数据类型栈的定义 栈:限定仅在表尾进行插入或删除操作的线性表;表尾端称为栈顶,表头端称为栈底。不含元素的空表称为空栈。 特点:进栈操作:栈底元素先进栈,栈顶元素后进栈; 出栈操作:栈顶元素先出栈,栈底元素后出栈; 总结:栈的修改是按照后进先出的原则进行的。 3.1. ......
3.1 栈
3.1.1抽象数据类型栈的定义
栈:限定仅在表尾进行插入或删除操作的线性表;表尾端称为栈顶,表头端称为栈底。不含元素的空表称为空栈。
特点:进栈操作:栈底元素先进栈,栈顶元素后进栈;
出栈操作:栈顶元素先出栈,栈底元素后出栈;
总结:栈的修改是按照后进先出的原则进行的。
3.1.2 栈的表示和实现
顺序栈和链栈
顺序栈:利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,同时,附设指针top指示栈顶元素在顺序栈中的位置。
通常栈空表示为:top=0;
但是,一方面,如果以c语言作为描述语言时,c语言中的数组下标约定从0开始,这样设定(top=0)会带来很大不便;
另一方面,由于栈在使用过程中需要最大空间的大小很难确定,所以,在初始化栈空时,不应该限定栈的最大容量。
比较合理的做法为:
-
先为栈分配一个基本容量
-
在应用过程中不断扩大栈的容量空间(栈的空间不够时)
做法:设两个常量stack_init_size(存储空间初始分配量)、stackincrement(存储空间分配增量)
typedef struct{ selemtype *base; selemtype *top; int stacksize; }sqstack;
若base的值为null,则栈结构不存在;
栈空标记:top=base;
链栈:……