2.3-2.4栈和队列 1、线和从列都是线性表。 2、找和丛列都是操作受原的线性表。 3、对栈和队列的基本操作进行限制的目的是:为 了保证其数据元素存取的特定序。 即:栈可保证数据元素存取的后进先出顺序。 队列可保证数据元素存取的先进先出顺序
2.3-2.4 栈和队列 1、栈和队列都是线性表。 2、栈和队列都是操作受限的线性表。 3、对栈和队列的基本操作进行限制的目的是：为 了保证其数据元素存取的特定顺序。 即：栈可保证数据元素存取的后进先出顺序。 队列可保证数据元素存取的先进先出顺序。
2.3.1栈的定义及基本操作 一.栈的定义 栈:限定只能在表的一端进行插入和删除的特殊的线性表。 设栈s=(a1,a2, a 9 其中a1是栈底元素,an是栈顶元素。 栈顶 a n a 栈底 a
一.栈的定义 栈：限定只能在表的一端进行插入和删除的特殊的线性表。 设栈s=（a1，a2，. . . ,ai，. . . ，an）， 其中a1是栈底元素， an是栈顶元素。 a1 a2 …. 栈顶 an 栈底 2.3.1 栈的定义及基本操作
2.3栈 一.栈的定义 栈:限定只能在表的一端进行插入和删除的特殊的线性表。 设栈s=(a1,a2, a 9 其中a1是栈底元素,an是栈顶元素。 栈顶(top):允许插入和删除的一端; top始终指向栈中最后一个元素所在的位置。栈顶 a n 栈底( bottom):不允许插入和删除的一端。 思考:对栈的操作一旦进行了这样的限制,它 a 栈底 普通线性表会有怎样的区别? a
栈顶（top)：允许插入和删除的一端； top始终指向栈中最后一个元素所在的位置。 栈底（bottom):不允许插入和删除的一端。 思考 ：对栈的操作一旦进行了这样的限制，它和 普通线性表会有怎样的区别？ 2.3 栈 一.栈的定义 栈：限定只能在表的一端进行插入和删除的特殊的线性表。 设栈s=（a1，a2，. . . ,ai，. . . ，an）， 其中a1是栈底元素， an是栈顶元素。 a1 a2 …. 栈顶 an 栈底
栈的插入操作被称为进栈; 栈的删除操作被称为出栈。 进栈 出栈 栈顶 栈底 今栈的特点:后进栈的元素在出栈时较其它元素先。 因此栈被称为后进先出(LIF0)的线性表
a1 a2 …. 栈顶 an 栈底 栈的插入操作被称为进栈； 栈的删除操作被称为出栈。 进栈 出栈 ❖栈的特点：后进栈的元素在出栈时较其它元素先。 因此栈被称为后进先出（LIFO）的线性表
二.栈的存储结构 顺序栈、链栈 1顺序栈: 用顺序存储结构表示的栈。 顺序栈用一组连续的存储单元存放 栈底到栈顶的数据元素,一般用一维 数组表示,设置一个简单变量top指示 栈顶位置,它始终指向栈中最后一个元 素的位置。 . op a 2 a
二.栈的存储结构 顺序栈、链栈 a2 aa11 a2 top 1.顺序栈： 用顺序存储结构表示的栈。 顺序栈用一组连续的存储单元存放 自栈底到栈顶的数据元素，一般用一维 数组表示，设置一个简单变量top指示 栈顶位置，它始终指向栈中最后一个元 素的位置
设数组是个孩的最容量m取使成 空栈 2插入一个新的栈顶元素 s[4] S[4] 栈空 3 10进栈 3210 2 010 top top=1←top cop=top+1 s[top]=x S[4] S[4 top=3 3210 top 3 40 30 30出栈)230 栈满 25 10 25 0 x=S[top] 10 top=top-1 top=maxsize-1
设数组S是一个顺序栈，栈的最大容量maxsize=4，初始状态top=-1 10 25 30 S[4] 2 3 1 0 top x=s[top] top=top-1 10 S[4] 2 3 1 0 top=top+1 s[top]=x top 10进栈 30出栈 栈空 S[4] 2 3 1 0 top=-1 top 栈满 top=maxsize-1 10 25 30 40 S[4] 2 3 1 0 top=3 栈中的运算：1.设置空栈 ； 2. 插入一个新的栈顶元素(入栈) 3. 删除栈顶元素(出栈）； 4. 读取栈顶元素
stack[o] S stack[1] 用C语言对顺序栈类型进行的描述 #define maxsize 100 typedef struct stacktype i datatype stack [maxsize]; int top, ystacktype; stacktype *S; 注意: datatype在此泛指栈中元素的类型, 实际应用时需按具体情况确定。例如:栈 stack [98 中元素为整型,则 stack应定义为整型数组 stack[99] top
#define maxsize 100 typedef struct stacktype { datatype stack[maxsize]; int top; }stacktype; stacktype *s； . . . . . . . . stack[0] stack[1] stack[98] stack[99] top s 用C语言对顺序栈类型进行的描述 注意：datatype在此泛指栈中元素的类型， 实际应用时需按具体情况确定。例如：栈 中元素为整型，则stack应定义为整型数组
三、顺序栈操作的算法描述(C语言) 1构造空栈 void initstack(stacktype *s) {初始化栈s,置为空栈* S->top 1; 2判断一个栈是否为空栈 int stackEmpty (stacktype *s) {*判断s是否为空栈,若为空栈,返回1,否则返回0* return s->top==-1;+ if(s->top==-1)return 1; else return 0:
三、顺序栈操作的算法描述（C语言） 1 构造空栈 void initStack(stacktype *s) {/*初始化栈s，置为空栈*/ s->top = -1; } 2 判断一个栈是否为空栈 int stackEmpty(stacktype *s) {/* 判断s是否为空栈，若为空栈，返回1，否则返回0 */ return s->top = = -1; } if(s->top==-1) return 1; else return 0;
进栈算法(假定栈为整型) #define maxsize 10 typedef struct stacktype f int stack[maxsizel Int top; 通过地址传递,用s带 87 ystacktype; 回进栈操作后新栈的信 意 void push(stacktypes, int x) if(s→>top== maxsize-1 printf("stack overflow! ) 6543210 top exit(1; else s->top++;/*实际栈顶位置加1*/ s->stack[s->top]=x; a } s->stack[++s->top]=x;
·进栈算法 （假定栈为整型 ） #define maxsize 10 typedef struct stacktype { int stack[maxsize]; int top ; }stacktype ; void push(stacktype *s, int x) {if(s ->top= =maxsize - 1 ) {printf(“stack overflow!”) ; exit( 1 ) ; } else{ s ->top++ ; /*实际栈顶位置加 1*/ s ->stack[s ->top]=x ; } } a 2 a 3 a 4 9876543210 a 1 top top x s ->stack[++s ->top]=x ; 通过地址传递，用 s 带 回进栈操作后新栈的信息
出栈算法(假定栈为整型) int pop(stacktype s) tint y; 通过地址传递, 用s带回出栈操 if(s->top==-1) 作后新栈的信息 Cprintf("stack empty! \n") exit(1); else {y=s→> stack[s->top]l S->top- y=s->stack[s->top-1) 9876543210 top return(y);/*返回出栈元素*/ a
int pop(stacktype *s) {int y ; if(s ->top= = - 1 ) {printf(“stack empty! \n”) ; exit( 1 ) ; } else{ y=s ->stack[s ->top] ; s ->top-- ; /*栈顶位置下移 * / return(y) ; /*返回出栈元素 * / } } a 2 a 3 a 4 9876543210 a 1 top ·出栈算法 （假定栈为整型 ） top y=s->stack[s->top--]); 通过地址传递， 用s带回出栈操 作后新栈的信息
