数据结构－第03章－栈和队列.ppt

第3章 栈和队列 栈和队列是两种重要的线性结构。 栈和队列是操作受限的线性表。 本章讨论栈和队列的定义、表示方法和实现外，还将给出一些应用的例子。 第3章 栈和队列 栈 栈的应用举例 队列 队列的应用举例 3.1 栈 (Stack) 3.1.1 栈的定义 栈的基本操作 栈的抽象数据类型的定义： ADT Stack{ 数据对象：D={ ai | ai∈Elemset , i =1,2,…,n, n=0} 数据关系：R1={ ai-1， ai | ai-1，ai ∈ D, i = 1,2,…,n} 约定an端为栈顶， a1端为栈底。 基本操作： InitStack(S) 操作结果：构造一个空栈s。 DestroyStack(S) 初始条件：栈s已存在。作结果：栈s被销毁。 ClearStack(S) 初始条件：栈s已存在。操作结果：将s清为空栈。 StackEmpty(S) 初始条件：栈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 3.1.2 栈的表示和实现 1. 顺序栈 2. 链栈 1. 顺序栈 顺序栈：利用数组存放自栈底到栈顶的数据元素，附设指针top指示栈顶元素在顺序栈中的位置。 #define STACK_INIT_SIZE 1024 typedef struct{ SElemType *base; //栈底指针 SElemType *top; //栈顶指针 int StackSize; //栈的当前可使用的最大容量. }SqStack; 栈底初值 base= NULL 空栈 top=base 栈满 top=STACK_INIT_SIZE-1 栈的初始化 Status InitStack(SqStack s){ //构造一个空栈S S.base = (SElemType*) malloc ( Stack_INT_SIZE * sizeof ( SElemType ) ); If ( !.S.base ) exit ( OVERFLOW ): s.top = s.base; s.stacksze = STACK-INIT-SIZE; return ok; }//InitStack 栈空判别 Status GeTop(SqStack s, selemType e){ //若栈不空，则用E返回S的栈顶元素，并返回OK；否则返回ERROR if(s.top==s.base ) return Error; e=*(s.top-1); return ok; }//GetTop 元素进栈 Status Push (SqStack s, SelemType E){ //插入元素E为新的栈顶元素 if(S.top-S.base = S.stacksize){ s.base = (ElemType *) realloc(b.base, (s.stacksize+STACKINCREMENT*sizeof(ElemType)); if(!s.base ) exit(OVERRLOW); 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 问题 能否两个栈共享一个数组空间? 2. 链栈（参考） 链栈：栈的链式表示。 3.2 栈的应用举例 栈具有后进先出的特性，成为程序设计中的有用工具。 数制转换 迷宫求解 表达式求值