《数据结构》 第三章(上)
《 数据结构》 第三章(上)
第三章栈和队列 数据结构 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表达式求值 3.3栈与递归的实现 3.4队列 3.4.1抽象数据类型队列的定义 3.4.2链队列一队列的链式表示和实现 3.4.3循环队列一队列的顺序表示和实现 tim
数据结构 tjm
数据结构 3.1栈 3.1.1抽象数据类型栈的定义 栈( Stack)是限制在表的一端进行插入和删除 运算的线性表,通常称插入、删除的这一端为栈顶 (Top),另一端为栈底( Bottom)。当表中没有 元素时称为空栈。 假设栈S=(a1,a2,a3,an),则a1称为 栈底元素,an为栈顶元素。栈中元素按a1,a2, a3,,an的次序进栈,退栈的第一个元素应为栈 顶元素
数据结构 tjm
数据结构 例、一叠书或一叠盘子 栈顶 特点:后进先出 (LIFo)。 a2 栈底 G 1 栈的ADT定义参见p45
数据结构 tjm ……
数据结构 3.12栈的表示和实现 顺序栈 由于栈是操作受限的线性表,因此线性表的存 储结构对栈也适应 栈的顺序存储结构简称为顺序栈,可用数组来 实现顺序栈。因为栈底位置是固定不变的,所以可 以将栈底位置设置在数组的两端的任何一个端点 栈顶位置是随着进栈和退栈操作而变化,故需 用一个指针t。p来指示当前栈顶的位置,通常称 top为栈顶指针。因此,顺序栈的类型定义只需将 顺序表的类型定义中的长度属性改为top指针即可
数据结构 tjm