数据结构详细教案——栈和队列.doc

数据结构教案 第三章 栈和队列  目 录 3.1 栈的基本概念 0 3.1.1 栈的抽象数据类型定义 0 3.1.2 顺序栈 0 3.1.3 链栈 2 3.2 栈的应用 2 3.2.1 数制转换：将十进制数N转换成其他d进制数 2 3.2.2 括号匹配的检验 2 3.2.3 行输入处理程序 2 3.2.4 迷宫求解 3 3.2.5 表达式求值 3 3.3 栈与递归的实现 4 3.4 队列的基本概念 4 3.4.1 队列的抽象数据类型定义 4 3.4.2 链队列 5 3.4.3 循环队列 6 3.5 队列与栈的应用 6 3.5.1 离散事件模拟 6  栈和队列 栈的基本概念 栈的抽象数据类型定义 栈的逻辑特征 限定在表尾进行插入或删除操作的线性表； 栈顶——表尾端；栈底——表头端 后进先出的线性表 抽象数据类型的定义 ADT Stack{ 数据对象：D={ai |ai∈ElemSet, i=1,2,…,n, n≥0} 数据关系：R={R1},R1={ai-1,ai|ai-1,ai∈D, i=2,3,…,n } 基本操作： InitStack( S ) 操作结果：构造一个空的栈S DestroyStack( S ) 初始条件：栈S已存在 操作结果：销毁栈S ClearStack( S ) 初始条件：栈S已存在 操作结果：将栈S重置为空栈 StackEmpty( S ) 初始条件：栈S已存在 操作结果：若S为空栈，则返回TRUE，否则返回FALSE StackLength( S ) 初始条件：栈S已存在 操作结果：返回栈S中数据元素的个数 GetTop( S, e ) 初始条件：栈S已存在且非空 操作结果：用e返回S中栈顶元素 Push( S, e ) 初始条件：栈S已存在 操作结果：插入元素e为新的栈顶元素 Pop( S, e ) 初始条件：栈S已存在且非空 操作结果：删除S的栈顶元素，并用e返回其值 StackTraverse( S, visit( ) ) 初始条件：栈S已存在且非空 操作结果：从栈底到栈顶依次对S的每个数据元素调用函数visit( )。一旦visit( )失败，则操作失败 }ADT Stack 思考：栈的取元素、插入、删除操作与线性表的相应操作有何区别，为什么？ 顺序栈 增量式顺序栈的定义 #define STACK_INIT_SIZE 100 /* 存储空间的初始分配量 */ #define STACKINCREMENT 10 /* 存储空间的分配增量 */ typedef struct{ ElemType *base; /* 栈底指针 */ ElemType *top; /* 栈顶指针(栈顶元素的下一个位置) */ int stacksize; /* 当前分配的存储容量 */ }SqStack; 和顺序表一样采用增量式的空间分配； 操作和栈顶相关：插入操作（入栈）：将待插元素插入到栈顶元素的下一个位置；删除操作（出栈）：删除栈顶元素；取元素操作：取栈顶元素的值。各操作的操作位置与栈顶元素的位置或其下一个位置相关，希望在O(1)时间内能获取操作位置，故可设置专门的栈顶指针top。 约定：top指向栈顶元素的下一个位置（便于表示空栈）。 栈顶的初始化：S.top = S.base(在上述3)约定下的空栈形式)， 栈空：S.base == S.top，栈满：S.top - S.base = S.stacksize 入栈：*S.top ++ = e，出栈：e = *--S.top 注意：4), 5), 6)步受3)制约。约定不同，相应的判定和处理也不一样。 如假设top就指向栈顶元素，此时4),5),6)如何？ 取栈顶元素GetTop_Sq 算法设计 参数：顺序栈S、取得的栈顶元素e 分析：由于top指向栈顶元素的下一个位置，因此实际的栈顶元素的位置应是top -1；栈非空时，此操作有效。 算法1 Status GetTop_Sq(SqStack S, ElemType e){ /* 判断栈是否为空 */ if ( S.base == S.top) return ERROR; e = *( S.top -1); return OK; } 入栈操作Push_Sq 算法设计 参数：顺序栈S、插入元素e 分析：插入位置为栈顶元素的下一个，无须判断位置的合法性；上溢即栈满的条件需要判断，由于是增量式分配，故栈满时需要重新申请空间; 算法2 Status Push_Sq( SqStack S, ElemType e ){ /* 判断栈是否为满 */ if ( S.top – S.base = S.stacksize ){ /