第三章栈和队列 3.1栈的表示和实现 3.2递归过程 3.4队列的表示和实现 >栈和队列的逻辑结构、物理结构,以 及它们之间的相互关系; >定义与之相适应的运算; >设计相应的算法; 分析算法的效率
第三章 栈和队列 3.1 栈的表示和实现 3.2 递归过程 3.4 队列的表示和实现 ➢栈和队列的逻辑结构、物理结构，以 及它们之间的相互关系； ➢定义与之相适应的运算； ➢设计相应的算法； ➢分析算法的效率
3.1找的表示和实现 3.1.1、栈的概念 线( stack)是插入和删除操作限定在表尾进行 的线性表。 栈的逻辑表示为:S=(a1,a2,….an) 表尾元素an称为栈页(top) 表头元素a1称为栈底( bottom 不含元素的空表称为空栈 ·栈的运算特性是 后进先出( Last in first out-LIFO) 或先进后出( First In last out-FIL0)
3.1.1、栈的概念 栈（stack）是插入和删除操作限定在表尾进行 的线性表。 • 栈的逻辑表示为：S =（a1,a2, …,an） 表尾元素an称为栈顶(top) 表头元素a1称为栈底(bottom) • 不含元素的空表称为空栈 • 栈的运算特性是 后进先出(Last In First Out--LIFO) 或先进后出(First In Last Out--FILO) 3.1 栈的表示和实现
3.1找的表示和实现 3.12顺序栈 由于栈是运算受限的线性表,因此线性 表的存储结构对栈也适应。 急栈的顺序存储结构简称为顺序栈,它 算受限的线性表。因此,可用数组来 实现顺序栈。因为栈底位置是固定不变的 所以可以将栈底位置设置在数组的两端的 任何一个端点;栊顶位置是随着进栈和退 栈操作而变化的,故需用一个整型变量top
3.1.2 顺序栈 由于栈是运算受限的线性表，因此线性 表的存储结构对栈也适应。 栈的顺序存储结构简称为顺序栈，它 是运算受限的线性表。因此，可用数组来 实现顺序栈。因为栈底位置是固定不变的， 所以可以将栈底位置设置在数组的两端的 任何一个端点；栈顶位置是随着进栈和退 栈操作而变化的，故需用一个整型变量top 3.1 栈的表示和实现
来指示当前栈顶的位置,通常称top为栈顶 指针。因此,顺序栈的类型定义只需将顺 序表的类型定义中的长度属性改为top即可。 顺序栈的类型定义如下: f define stacksize 100 typedef char datatype; typedef struct t datatype data stacksize]; int top; 3seqstack;
来指示当前栈顶的位置，通常称top为栈顶 指针。因此，顺序栈的类型定义只需将顺 序表的类型定义中的长度属性改为top即可。 顺序栈的类型定义如下： # define StackSize 100 typedef char datatype; typedef struct { datatype data[stacksize]; int top; }seqstack;
例、一疊书或一叠盘子。 栈的抽象数据类型的定义如下:P4 栈顶 top 栈底 ba
例、一叠书或一叠盘子。 栈的抽象数据类型的定义如下：P44 a n a n-1 a2 a1 …… 栈顶 栈底 top base