数据结构讲义第3章节.pptVIP

第三章 栈和队列 栈和队列是两种重要的数据结构。 从结构特性角度看，栈和对列也是线性表，其特殊性在于它们的基本操作是线性表的子集，是操作受限的线性表，可称为限定性的数据结构。 从数据类型角度看，其操作规则与线性表大不相同，是完全不同于线性表的抽象数据类型。 第一节 栈 栈的表示与实现 顺序栈操作的实现 顺序栈操作的实现 顺序栈操作的实现 顺序栈操作的实现 链式栈的实现 第二节 栈的应用 栈的应用 栈的应用—表达式求值 栈的应用—表达式求值 栈的应用—表达式求值 栈的应用—表达式求值 第三节 栈与递归的实现 栈与递归的实现 第四节 队列 队列的链式表示及实现 链队列基本操作 链队列基本操作 链队列基本操作 队列的顺序表示及实现 队列的顺序表示及实现 队列的顺序表示及实现 循环队列 循环队列算法 循环队列算法 循环队列算法 队列的应用 作业 * 一、栈的定义 栈是限定在表的一端进行插入和删除操作的线性表。 插入：称为进栈（或压栈）。 删除：称为出栈（或退栈）。 栈顶（top）：允许进行插入和删除操作的一端。 栈底（bottom）：不允许插入和删除操作的一端。 基本操作： Initstack(s): 栈初始化 Destroystack(s)：撤消栈 Clearstack(s)：置栈空 Stackempty(s) ：判栈空 Stacklength(S)：求栈中元素个数 Gettop(S,e)： 取栈顶元素 Push(S,e)： 入栈 Pop(S,e)： 出栈 特点：后进先出----LIFO Last In First Out 栈底 … an a2 a1 栈顶 三、栈的顺序存储结构----顺序栈 利用一组地址连续的存储单元依次存放从栈底到栈顶的数据元素。 顺序栈存储结构定义： #define STACK_INIT_SIZE 100 //存储空间初始分配量； #define STACKINCREMENT 10 //存储空间分配增量 typedef struct { SElemType *base; SElemType *top; int stacksize; }SqStack; Base指向存储空间开始地址，top指示栈顶当前位置。 若栈空间未分配，则base为NULL； top==base:栈空 top-base==stachsize:栈满 元素进栈：在top位置插入元素，top增1 元素出栈：top减1。 top指针始终指向栈顶元素的下一个位置 。 1、栈初始化：分配初始存储空间，初始化各变量。 Status Initstack(Sqstack s) { s.base=（SElemType *） malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!b.base) exit(OVERFLOW); s.top=s.base; s.stacksize= STACK_INIT_SIZE； return Ok； } 2、撤消栈：释放栈空间。 status Destroystack(SqStack s) { if(s.base) { free(s.base); s.base=NULL;return OK;} return ERROR; } 3、置栈空：将栈设置成空栈。 status Clearstack(SqStack s) { if(s.base) { s.top=s.base;return OK;} return ERROR; } 4、取栈顶元素：返回栈顶元素的值。 status GetTop(SqStack s,SElemType e) { if(s.top==s.base) return ERROR; e=*(s.top-1); return OK } 5、入栈操作：把元素压入栈中。 status Push(SqStack s，SElemType e)