第三章栈和队列 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
76543 p
top 7654321－ 1
设S是 SeqStack类型的指针变量。若栈底 位置在向量的低端,即s->data[0]是栈底 元素,那么栈顶指针s->top是正向增加的, 即进栈时需将s->top加1,退栈时需将s top减1。因此,s->top<0表示空栈,s top= stacksize-1表示栈满。当栈满时再 做进栈运算必定产生空间溢出,简称“上 溢”;当栈空时再做退栈运算也将产生溢出, 简称“下溢”。上溢是一种出错状态,应 该设法避免之;下溢则可能是正常现象, 因为栈在程序中使用时,其初态或终态都 是空栈,所以下溢常常用来作为程序控制 转移的条件
设S是SeqStack类型的指针变量。若栈底 位置在向量的低端，即s–>data[0]是栈底 元素，那么栈顶指针s–>top是正向增加的， 即进栈时需将s–>top加1，退栈时需将s– >top 减1。因此，s–>toptop =stacksize-1表示栈满。当栈满时再 做进栈运算必定产生空间溢出，简称“上 溢”;当栈空时再做退栈运算也将产生溢出， 简称“下溢”。上溢是一种出错状态，应 该设法避免之；下溢则可能是正常现象， 因为栈在程序中使用时，其初态或终态都 是空栈，所以下溢常常用来作为程序控制 转移的条件
3.1.3、判断栈满 int stackfull(segstack * s) return(s->top==stacksize-1) 3.1.4、进栈 void push (seastack *s, datatype x) if (stackfull(s)) printf(“ stack overflow”) s->data[++s->top]=x
3.1.3、判断栈满 int stackfull(seqstack *s) { return(s–>top==stacksize-1); } 3.1.4、进栈 void push(seqstack *s，datatype x) { if (stackfull(s)) printf(“stack overflow”); s–>data[++s–>top]=x; }
3.1.5、置空栈 void initstack(segstack *s) s->top=-1; 3.1.6、判断栈空 int stackempty(seqstack as) return(s->top==-1)
3.1.5、置空栈 void initstack(seqstack *s) { s–>top=-1; } 3.1.6、判断栈空 int stackempty(seqstack *s) { return(s–>top==-1); }
3.1.7、退栈 datatype pop ( segstack *s) if (stackempty(s)) error(“ stack underflow”); x=S->dataltop s->top-- return (x) //return(s->datals->top-])
3.1.7、退栈 datatype pop(seqstack *s) { if (stackempty(s)) error(“stack underflow”); x=s–>data[top]; s–>top--; return(x) //return(s–>data[s–>top--]); }