答是要 4.1 °顺序找 °链式栈 °找的应用 4.2栈和递归的实现 °基本概念 基本问题 4.3队列 饭序队列 °链式队列 °从列的应用 4.4栈和队列的应用范例
内容提要 4.1 栈 • 顺序栈 • 链式栈 • 栈的应用 4.2 栈和递归的实现 • 基本概念 • 基本问题 4.3 队列 • 顺序队列 • 链式队列 • 队列的应用 4.4 栈和队列的应用范例
41传 1、定义 栈( Stack):一种后进先出(L|FO的线性表 向栈中插入和删除元素,必须在栈的 端进行。因此,栈是操作受限的! 栈顶top):元许插入和删除的一端 栈底( bottom:不允许插入和删除的一端 栈的主要操作: 建立空栈 进线 出栈 判断栈是否空 判断栈是否满获取栈顶元素值
4.1 栈 1、定义 栈(Stack)：一种后进先出(LIFO)的线性表。 栈顶(top)：允许插入和删除的一端 栈底(bottom)：不允许插入和删除的一端 栈的主要操作： 建立空栈 进栈 出栈 判断栈是否空 判断栈是否满 获取栈顶元素值 向栈中插入和删 除元素，必须在栈的一 端进行。因此，栈是操作受限的！
出栈 进栈 栈的修改是按后进先出 栈顶 an Last In First Out,简称 a2 a1 L|FO的原则进行的 栈的示意图
栈(cont’d) a1 a2 … an 出栈 进栈 栈顶 栈的示意图 栈的修改是按后进先出 (Last In First Out，简称 LIFO)的原则进行的
传之顺序线 2、版序:用版序表实现的线 (1)顺序的数据类型定义: #define maXsize 50 typedef struct elemtype elem MAXSIE: int top /*栈顶*/ JSQSTACK
栈之顺序栈 2、顺序栈：用顺序表实现的栈 (1) 顺序栈的数据类型定义： #define MAXSIZE 50 typedef struct { elemtype elem[MAXSIZE]; int top; /*栈顶*/ }SQSTACK;
之顺序c( (2)顺序线的基本操作(建线: 建立空栈 void initstack(SQSTACK *s s→>top=-1;/*-1表示空栈*
栈之顺序栈(cont’d) (2) 顺序栈的基本操作(建栈)： void initstack(SQSTACK *s) { s→top= -1; /*-1表示空栈*/ } • 建立空栈