第_3_章_栈与队列.pptVIP

栈的形式化定义 栈简称为S，是一个二元组 S=（D,R) 其中：D 是数据元素的有限集合 D＝{ ai | ai ∈ElemSet, i = 1, 2, ..., n, n≥0 } R 是数据元素之间关系的有限集合 数据关系：R1＝{ ai-1, ai | ai-1, ai∈D, i = 2, ..., n }  约定an 端为栈顶，a1 端为栈底。 队列的形式化定义 队列简称为Q，是一个二元组 Q=（D,R) 其中：D 是数据元素的有限集合 D＝{ ai | ai ∈ElemSet, i = 1, 2, ..., n, n≥0 } R 是数据元素之间关系的有限集合 数据关系：R1＝{ ai-1, ai | ai-1, ai∈D, i = 2, ..., n }  约定an 端为队尾，a1 端为队头。 数据结构 第三章 栈和队列 1、栈和队列的定义及特点； 2、栈的顺序存储表示； 3、队列的顺序存储表示；队列的链接存储表示； 4、栈和队列的应用举例。 教学内容 限定仅在表尾进行插入或删除操作。 3.1 栈 3.1.1 抽象数据类型栈的定义 栈的定义 a1 a2 an-1 an … 栈顶 (top) 栈底 (bottom) 出栈 进栈 栈底元素 栈顶元素 栈(stack)：线性表 后进先出 (LIFO结构)。 栈顶 (top) 数据对象 （ a1 ， a2 ， a3 ，…….， ai-1 ， ai ， ai +1，……， an） 栈的接口的定义 Public interface IStackT { int GetLength( ); // 求栈的长度 bool IsEmpty( ); // 判断栈是否为空 void Clear ( ); // 清空操作 void Push (T item ); //入栈操作 T Pop ( ); // 出栈操作 T GetTop（）；//取栈顶元素 } 3.1.2 栈的存储和运算实现 顺序栈 利用一组地址连续的 存储单元 依次存放自栈底到栈顶的 数据元素，同时附设指针 top 指示栈顶元素在顺序栈中的位置。 top A top B top C top D top E top 空栈 若再进行元 素“出栈”操 作，将产生 “下溢”。 top 栈满 若再进行元 素“入栈”操 作，将产生 “上溢”。 top -1 顺序栈类SeqStackT的实现说明： public class SeqStackT: IStackT { private int maxsize ; // 顺序栈的容量 private T[] data ; // 数组，用于存储顺序栈中的数据元素 private int top; //指示顺序栈的栈顶 基本操作： } 顺序栈的基本操作： int GetLength( ); // 求栈的长度 bool IsEmpty( ); // 判断栈是否为空 void Clear ( ); // 清空操作 void Push (T item ); //入栈操作 T Pop ( ); // 出栈操作 T GetTop（）；//取栈顶元素 3.2 栈的应用举例 3.2.1 数制转换 十进制数 N 和其他 d 进制数 M 的转换是计算机实现计算 的基本问题，其解决方法很多，其中一个简单算法是逐次除以 基数 d 取余法，它基于下列原理： N = (N div d )*d + N mod d 具体作法为：首先用 N 除以 d，得到的余数是 d 进制数 M 的