数据结构
数据结构
第三章栈和队列 31栈 311抽象数据类型栈的定义 312栈的表示和实现 3.2栈的应用举例 321数制转换 3.2.2括号匹配的检验 3.2.3行编辑程序 3.2.4迷宫求解 325表达式求值
第三章 栈和队列 3.1 栈 3.1.1 抽象数据类型栈的定义 3.1.2 栈的表示和实现 3.2 栈的应用举例 3.2.1 数制转换 3.2.2 括号匹配的检验 3.2.3 行编辑程序 3.2.4 迷宫求解 3.2.5 表达式求值
33栈与递归的实现 34队列 341抽象数据类型队列的定义 342链队列—队列的链式表示和实现 34.3循环队列—队列的顺序表示和实现 3.5离散事件模拟
3.3 栈与递归的实现 3.4 队列 3.4.1 抽象数据类型队列的定义 3.4.2 链队列——队列的链式表示和实现 3.4.3 循环队列——队列的顺序表示和实现 3.5 离散事件模拟
3.1.1 栈 311栈的定义及基本运算 栈Sac是限制在表的一端进行插入和删除 运算的线性表,通常称插入、删除的这一端 为栈顶p),另一端为栈底 Bottom)当表 中没有元素时称为空栈。 假设栈S=(a1,a2,a3…,a,则a1称为栈底 元素,a为栈顶元素。栈中元素按a1,a2 an的次序进栈,退栈的第一个元素应为 栈顶元素。换句话说,栈的修改是按后进先 出的原则进行的。因此,栈称为后进先出表 (ⅠIFO)
3.1.1 栈 3.1.1 栈的定义及基本运算 栈(Stack)是限制在表的一端进行插入和删除 运算的线性表，通常称插入、删除的这一端 为栈顶(Top)，另一端为栈底(Bottom)。当表 中没有元素时称为空栈。 假设栈S=(a1，a2，a3，…an )，则a1称为栈底 元素，an为栈顶元素。栈中元素按a1，a2， a3，…an的次序进栈，退栈的第一个元素应为 栈顶元素。换句话说，栈的修改是按后进先 出的原则进行的。因此，栈称为后进先出表 （LIFO）
3.12顺序栈 由于栈是运算受限的线性表,因此线性 表的存储结构对栈也适应。 栈的顺序存储结构简称为顺序栈,它是 运算受限的线性表。因此,可用数组来实 现顺序栈。因为栈底位置是固定不变的 所以可以将栈底位置设置在数组的两端的 任何一个端点;栈顶位置是随着进栈和退 栈操作而变化的,故需用一个整型变量top 来表示
3.1.2 顺序栈 由于栈是运算受限的线性表，因此线性 表的存储结构对栈也适应。 栈的顺序存储结构简称为顺序栈，它是 运算受限的线性表。因此，可用数组来实 现顺序栈。因为栈底位置是固定不变的， 所以可以将栈底位置设置在数组的两端的 任何一个端点；栈顶位置是随着进栈和退 栈操作而变化的，故需用一个整型变量top 来表示