通信数据结构课件陈雄峰3第三章栈和队列.pptVIP

第三章 栈和队列 知识点： 栈概念及实现 队列概念及实现 栈的队列的综合应用 递归 重点：栈和队列的概念及实现； 难点：栈的队列的综合应用、递归。 3.1 栈 栈(stack): 限定仅在表尾进行插入或删除操作的线性表。 栈顶(top): 线性表的表尾端， 即允许插入和删除的一端。 栈底(bottom): 线性表的表头。 特点：后进先出 (LIFO) 或先进后出（FILO） 栈的抽象数据类型 ADT Stack { 数据对象：D＝{ ai |ai ∈ElemSet, i=1,2,...,n, n≥0 } 数据关系：R1＝{ ai-1 , ai| ai-1 , ai ∈D, i=2,...,n }　　　　　　　　　约定an端为栈顶，ai端为栈底。 基本操作： 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 已存在且非空。　　　操作结果：用 e 返回S的栈顶元素。Push(S, e)　　　初始条件：栈 S 已存在。　　　操作结果：插入元素 e 为新的栈顶元素。Pop(S, e)　　　初始条件：栈 S 已存在且非空。　　　操作结果：删除 S 的栈顶元素，并用 e 返回其值。StackTraverse(S, visit( ))　　　初始条件：栈 S 已存在且非空，visit( )为元素的访问函数。　　　操作结果：从栈底到栈顶依次对S的每个元素调用函数visit( )，　　　　　　　　一旦visit( )失败，则操作失败。} ADT Stack} 栈的表示和实现 顺序栈：栈的顺序存储结构，利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，指针top指向栈顶元素在顺序栈中的下一个位置， base为栈底指针，指向栈底的位置。 顺序栈的类型表示: #define STACK_INIT_SIZE 100； #define STACKINCREMENT 10； typedef struct { //顺序栈定义 SElemType *base; //栈底指针 SElemType *top; //栈顶指针 int stacksize；//当前已分配的存储空间 } SqStack； 顺序栈的类型表示: Status InitStack (SqStack S){ // 构造一个空栈 S S.base =(SElemType *)malloc(STACK_INIT_SIZE *sizeof( SElemType)); if (!S.base) exit(OVERFLOW); 　　 // 存储分配失败 S.top=S.base; S.stacksize = STACK_INIT_SIZE; } //InitStack  Status GetTop (SqStack S, SElemType e){ // 若栈不空，则用 e 返回S的栈顶元素，并返回TRUE； //否则返回FALSEif (S.top == S.base) return FALSE;e = *( S.top-1); 　　// 返回非空栈中栈顶元素return TRUE; } // GetTop Status Push (SqStack S, SElemType e){// 插入元素 e 为新的栈顶元素if (S.top –S.base= S.stacksize)　{ // 栈已满，追加存储空间  S.base=(SElemType *)realloc(S.base, (S.stacksize+STACKINCREMENT)*sizeof(SElemType));　 if(!S.base) exit(OVERFLOW); //存储分配失败 S.top=S.