chap14_栈和队列.ppt

Chap 14 栈和队列 栈例：一叠书或一叠盘子。 a n a n-1 a2 a1 …… 栈顶 栈底 栈的定义及基本运算 栈(Stack)是限定仅在表尾进行插入或删除操作的线性表。 栈的表尾称为栈顶(Top) ，表头称为栈底(Bottom) ，不含元素的空表称为空栈。 栈的修改是按后进先出的原则进行的。因此，栈称为后进先出表（LIFO）。 栈的抽象数据类型定义 ADT Stack{ 数据对象： D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 } 数据关系： R1＝{ ai-1, ai | ai-1, ai∈D, i=2,...,n } 约定an 端为栈顶，a1 端为栈底。 基本操作: InitStack(S) 构造一个空栈S DestroyStack(S) 栈S存在则栈S被销毁 ClearStack(S) 栈S存在则清为空栈 StackEmpty(S) 栈S存在则返回TRUE,否则FALSE StackLength(S) 栈S存在则返回S的元素个数,即栈的长度 GetTop(S,e) 栈S存在且非空则返回S的栈顶元素 Push(S,e) 栈S存在则插入元素e为新的栈顶元素 Pop(S,e) 栈S存在且非空则删除S的栈顶元素并用e返回其值 StackTraverse(S,visit())栈S存在且非空则从栈底到栈顶依次对S的每个数据元素调用函数visit()一旦visit()失败,则操作失败 }ADT Stack 栈的表示和实现 顺序栈 利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,同时附设指针top指示栈顶元素在顺序栈中的位置 链栈 利用链表实现 顺序栈 由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应。 栈的顺序存储结构简称为顺序栈，它是运算受限的线性表。因此，可用数组来实现顺序栈。因为栈底位置是固定不变的，所以可以将栈底位置设置在数组的两端的任何一个端点；栈顶位置是随着进栈和退栈操作而变化的，故需用一个整型变量top 顺序栈的结构定义 typedef struct{ ElemType *base;//栈底指针，书上为SElemType，不必要 ElemType *top; //栈顶指针 //设栈顶栈底两指针的目的是便于判断栈是否为空 int StackSize; //栈的当前可使用的最大容量. }SqStack; 顺序栈的实现 Status InitStack(SqStack S) /* 构造一个空栈S */ Status DestroyStack(SqStack S) /* 销毁栈S，S不再存在 */ Status ClearStack(SqStack S) /* 把S置为空栈 */ Status StackEmpty(SqStack S) { /* 若栈S为空栈，则返回TRUE，否则返回FALSE */ int StackLength(SqStack S) { /* 返回S的元素个数，即栈的长度 */ Status GetTop(SqStack S,ElemType e) { /* 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR */ Status Push(SqStack S,ElemType e) /* 插入元素e为新的栈顶元素 */ Status Pop(SqStack S,ElemType e) /* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */ Status StackTraverse(const SqStack S,Status(*visit)(const ElemType ))//书上此处不妥 /* 从栈底到栈顶依次对栈中每个元素调用函数visit()。 */ 01 栈的应用举例 栈结构具有的后进先出的固有特性，致使栈成为程序设计中常用的工具 数制转换 例： 十进制N和其它进制数的转换: 如 (1348)10=(2504)8，其运算过程如下： N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2 数制转换 void co