Page 90 - 高中 信息技术 选择性必修1 数据与数据结构
P. 90
第三章 线性数据的组织和存储
实 践
1. 根据所选择的项目，列出其中具备栈特征的事物或现象，并用画图的方式描述出这
种事物或现象的工作过程（画出栈，标识栈顶、栈底）。
2. 尝试为以上事物或现象建立栈模型。
根据栈的概念，在程序中我们可以这样定义栈：
typedef struct //数据描述
{
datatype items[maxsize];
//datatype为栈元素的类型，maxsize为栈的最大高度
广东教育出版社
int top; //栈顶标志
int bottom; //栈底标志
}Stack;
operations; //操作声明
与队列一样，在定义栈时，栈元素的类型datatype可以根据现实数据的情况而确定；
另外，若采用数组来作为栈元素的存储结构，数组容量的大小maxsize也需根据现实情况进
行估计。
3.4.2 栈的基本操作
栈的常用基本操作有以下几种：
（1）初始化栈：构造一个空栈，初始化栈顶标志。
（2）元素入栈：若栈非满，栈顶标志上移一位，插入一个元素到栈顶标志指向的位
置，该元素成为新的栈顶元素。
（3）元素出栈：删除栈顶标志指向的栈顶元素，栈顶标志下移一位，若此时栈非
空，则栈顶标志指向的元素成为新的栈顶元素。
（4）栈空判断：判断栈是否为空。
（5）栈满判断：判断栈是否为满。
（6）栈的长度：求栈的元素个数。
3.4.3 顺序栈的实现
栈的存储也可采用顺序存储结构的方法来实现，采用顺序存储结构的栈称为顺序栈，
是指利用一组连续的存储单元依次存放自栈底到栈顶的数据元素，同时设置指针top来动态
地指示栈顶元素的当前位置。
82 82
21X2204.indd 82 2019/9/26 13:53:19
