03 第三章栈与队列.ppt

第三章 栈和队列 3.1 栈 栈的表示和实现 3.2 栈的应用举例 3.2.1 数制转换 3.2.2 括号匹配的检验 3.2.4 行编辑程序 3.2.5 迷宫求解 3.2.5 表达式求值 3.3 栈与递归的实现 3.4 队列 顺序栈 由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应。 栈的顺序存储结构简称为顺序栈，它是运算受限的线性表。 实现： 数组来实现顺序栈。 栈底位置是固定不变的，所以可以将栈底位置设置在数组的两端的任何一个端点； 栈顶位置是随着进栈和退栈操作而变化的，故需用一个整型变量top来指示当前栈顶的位置(栈顶元素的下一个位置)，通常称top为栈顶指针 顺序栈的类型定义如下：方式一（静态数组） # define StackSize 100 typedef char datatype; struct seqstack{ datatype data[stacksize]; int top; }; 栈的各种状态 设S是SeqStack类型的指针变量。若栈底位置在向量的低端，即s–data[0]是栈底元素，那么栈顶指针s–top是正向增加的，即进栈时需将s–top加1，退栈时需将s–top 减1。 因此： s–top＝0表示空栈， s–top =stacksize表示栈满。 当栈满时再做进栈运算必定产生空间溢出，简称“上溢”; 当栈空时再做退栈运算也将产生溢出，简称“下溢”。 顺序栈的定义，方式二 采用C语言中动态分配的一维数组表示顺序表 顺序栈的特性 top=0 或top=base 表示空栈 base=NULL表示栈不存在 当插入新的栈顶元素时,指针top+1 删除栈顶元素时，指针top-1 当topstacksize时，栈满，溢出 顺序栈的主要操作 ADT Stack { 数据对象：D = {ai | ai∈ElemSet, i=1,2,3,…,n} 数据关系：R = {ai-1, ai | ai-1,ai∈D} 基本操作：InitStack(S) // 构造空栈 Push(S, e) // 进栈 Pop(S, e) // 出栈 GetTop(S, e) // 取栈顶元素值 　　StackEmpty(S) // 栈是否为空 　 } ADT Stack 1、创建顺序栈 Status InitStack(SqStack S) { S.base = (SElemType *) malloc(STACK_INIT_SIZE * sizeof(SElemType)); if (!S.base) exit(OVERFLOW); // 存储分配失败 S.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK; } // InitStack 2、进栈（插入新元素） Status Push(SqStack S, SElemType e) { if (S.top – S.base = S.stacksize) { // 栈满，追加存储空间 S.base = (SElemType *) realloc(S.base, (S.stacksize + STACKINCRMENT* sizeof(SElemType)); if (!S.base) exit(OVERFLOW); S.top = S.base + S.stacksize; S.stacksize += STACKINCRMENT;} *S.top++ = e; return OK; } // Push 3、出栈（删除元素） Status Pop(SqStack S, SElemType e) { if (S.top == S.base) return ERROR; e = *--S.top; return OK; } // Pop 4、取栈顶元素 Status GetTop(SqStack S, SElemType e) { if (S.top == S.base) return ERROR; e = *(S.top-1); return OK; } // GetTop 编译系