Page 105 - 高中 信息技术 选择性必修1 数据与数据结构

 4.2 用抽象数据类型表示队列和栈

因为队列属于线性表，队列元素的组织和存储可以使用数组，也可以使用链表，在第
三章中我们已经分别用数组和链表实现了队列的存储和操作。虽然两种实现方法具体细节
各有不同，但是都体现出了元素的线性关系，并且在相关操作中也遵循先进先出的原则，
这就是队列的特点。

4 . 2 . 2 用抽象数据类型表示栈

栈和队列一样，属于线性表的一种，其元素之间也具有线性关系。与队列不同的是，
栈元素的入栈、出栈都是从同一头进行的，所以栈具有后进先出（LIFO）的特点。从抽象
}ADT 栈 广东教育出版社
数据类型的角度来看，栈的数据部分包括线性关系的数据元素和栈顶、栈底。关于栈的操
作有：初始化栈、元素入栈、元素出栈、栈空判断、栈满判断、求栈的长度。类似的，我

们可以用下面的抽象数据类型表示栈：
ADT 栈
{
数据：
栈元素;

栈顶;
栈底;
操作：

初始化栈;
元素入栈;
元素出栈;
栈空判断;
栈满判断;

求栈的长度;

与队列类似，栈的数据元素可以使用数组存储，也可以使用链表存储，不同的存储方

式，其实现细节会有一些区别。但是不管实现方式有何不同，其基本的数据元素关系是相
同的，栈的基本操作也是相同的，具有后进先出的特点。有关栈的实现，可以参考第三章
的相关内容。

探究活动

分 析

对比队列和栈的抽象数据类型表示，结合前面关于队列和栈的定义与实现，总结队列
和栈的共同点和区别。

97 97

21X2204.indd 97 2019/9/26 13:53:26