Chapter3：栈队列.pptVIP

Chapter 3:栈、队列 第三章 栈和队列 3.1 栈 3.1.1 抽象数据类型栈的定义 3.1.2 栈的表示和实现 3.2 栈的应用举例 3.2.1 数制转换 3.2.2 括号匹配的检验 3.2.4 行编辑程序 3.2.5 迷宫求解 3.2.5 表达式求值 §3.1 栈 §3.1.1　栈的逻辑结构 　　 限定仅在表的一端进行插入与删除的线性表。也称作FILO-先进后出（First In Last Out）的线性表。 ADT Stack{ 数据对象:D={ai|ai(- ElemSet,i=1,2,...,n,n=0} 数据关系:R1={ai-1,ai|ai-1,ai(- D,i=2,...,n} 基本操作: 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 栈的实例1-火车扳道站 栈事例2-中断处理 中断1打断过程0，中断2打断中断1，中断3打断中断2 §3.1.2　栈的顺序实现 用一组连续的存贮空间存放栈元素 顺序栈的类C语言定义 typedef struct{ SElemType *base; SElemType *top; //设栈顶栈底两指针的目的是便于判断栈是否为空 int StackSize; //栈的当前可使用的最大容量. }SqStack; 二、基本操作实现 Status InitStack(SqStack S) { S.base=(SelemType *)malloc(STACK_INIT_SIZE *sizeof(ElemType)); if(!S.base)exit(OVERFLOW); S.top=S.base; S.stacksize=STACK_INI_SIZE; return OK; }//IniStack Status ClearStack(SqStack S); { S.top=S.base; } //ClearStack Status StackEmpty(SqStack S); { if(S.top==S.base) return TRUE; else return FALSE; } //StackEmpty Status GetTop(SqStack S,SElemType e); { if(S.top==S.base) return ERROR; e=*(S.top-1); return OK; } //GetTop Status Push(SqStack S,SElemType e); { if(S.top - s.base=S.stacksize) { S.base=(ElemType *) realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(ElemType)); if(!S.base)exit(OVERFLOW); S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; } *S.top++=e; return OK; } //Push Status Pop(SqStack S,SElemType e); { if(S.top==S.base) return ERROR; e=*--S.top; return OK; }//Pop 我们要了解的是，在顺序栈中有“上溢”和“下溢”的概念。顺序栈好比一个盒子，我们在里头放了一叠书，当我们要用书的话只能从第一本开始拿,那么当我们把书本放到这个栈中超过盒子的顶部时就放不下了，这时就是上溢,上溢也就是栈顶指针指出栈的外面，显然是出错了。反之，当栈中已没有书时，我们再去拿，看看没书，把盒子拎起来看看盒底，还是没有，这就是下溢。下溢本身可以表示栈为空栈,因此可以用它来作为控制转移的条件。 三、多栈共享存贮空间 栈采用连续存贮结构时，要预分配足够大的存贮空间。若系统中使用n个栈， 每个栈的最大尺寸ni