第三章栈和队列 栈和队列的基本操 作是线性表操作的子集 是限定性(操作受限制) 的数据结构。 3.1栈 据>定义:是限定仅在表尾进行插入或删除操作 物的线性表。(后进先出线性表LIFO) 栈底指针(base):是线性表的基址; 栈顶指针(op:指向线性表最后一个元素的后面 当top=base时,为空栈 基本操作 InitStack(&S), Destroy Stack(&S), StackEmpty (s), ClearStack(&s), GetTop(s, &e), StackLength(S) 2Push(&S,e:完成在表尾插入一个元素e Pop(&S,&e):完成在表尾删除一个元素
1 栈和队列的基本操 作是线性表操作的子集， 是限定性（操作受限制） 的数据结构。 第三章 栈和队列 数 据 结 构 之 栈 和 队 列 2 3. 1 栈 ¾ 定义：是限定仅在表尾进行插入或删除操作 的线性表。(后进先出线性表LIFO) ¾ 栈底指针(base) :是线性表的基址； ¾ 栈顶指针(top):指向线性表最后一个元素的后面。 ¾ 当top=base 时，为空栈。 ¾ 基本操作： InitStack(&S), DestroyStack(&S), StackEmpty(S) , ClearStack(&S), GetTop(S ,&e), StackLength(S) , Push(&S, e): 完成在表尾插入一个元素e. Pop(&S,&e): 完成在表尾删除一个元素
栈的表示和实现 据结构 顺序栈:是利用一组地址连续的存储单元 依次存放自栈底到栈顶的数据元素;栈满 之后,可再追加栈空间即为动态栈。 顺序栈的结构类型定义: typedef int SElem Type; 栈 typedef struct SElemType*base;/栈底指针*/ SElemType *top; 栈顶指针 int stacksize;/栈空间大小*/ iSqStack 基本算法描述 建立能存放50个栈元素的空栈 w #define STACK INIT SIZE 50 *#define STACKINCREMENT 10 Status InitStack Sq(stack &S) S base=(SET")malloc(STACK INIT SIZE sizeof(SET)); /为栈分配空间 if(s base=NULL) 栈和队列 exit(oVErFLoW);/存储分配失败* Stop=S base S. stacksize= STACK INIT SIZE; return OK; 3
2 数 据 结 构 之 栈 和 队 列 3 ¾ 栈的表示和实现 ¾ 顺序栈：是利用一组地址连续的存储单元 依次存放自栈底到栈顶的数据元素；栈满 之后，可再追加栈空间即为动态栈。 ¾ 顺序栈的结构类型定义： typedef int SElemType; typedef struct{ SElemType *base; /* 栈底指针 */ SElemType *top; /* 栈顶指针 */ int stacksize; /* 栈空间大小 */ }SqStack ; 数 据 结 构 之 栈 和 队 列 4 ¾ 基本算法描述 ¾建立能存放50个栈元素的空栈 #define STACK_INIT_SIZE 50 #define STACKINCREMENT 10 Status InitStack_Sq(Stack &S){ S.base=(SET*)malloc(STACK_INIT_SIZE *sizeof(SET)); /*为栈分配空间*/ if(S.base==NULL) exit(OVERFLOW); /*存储分配失败*/ S.top=S.base; S.stacksize = STACK_INIT_SIZE; return OK; }
出栈操作算法 *t void pop(Sqstack S, SElemType e) 据结构 if(s top==Sbase return ERROR: top eise 栈和队列 s to top base 出栈操作 return OK 压栈操作算法 void Push(SqStack S, SElemType e) st if(s top-s base>=S. stacksize; )i 据 N S base=(SET*)realloc(S, base, (S stacksize-+STACKINCREMEN 构T) sizeof(sET);/为栈重新分配空间 if(l S base exit(OVERFLOW); Stop=S base+S.stacksize; S. stacksize+=STACKINCREMENT top 栈和队列 S S top++; 3 return OK; ase 压栈操作
3 数 据 结 构 之 栈 和 队 列 5 ¾出栈操作算法 void pop(Sqstack s, SElemType e) { if(s.top= = s.base) return ERROR; else{ s.top--; e= *s.top; } return OK; } 出栈操作 top A B Y top A B base base Y 数 据 结 构 之 栈 和 队 列 6 ¾压栈操作算法 void Push(SqStack s, SElemType e) if(s.top-s.base>= S.stacksize;) { S.base=(SET*)realloc(S,base,(S.stacksize+STACKINCREMEN T) *sizeof(SET)); /*为栈重新分配空间*/ if(！S.base) exit(OVERFLOW); S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; } *S.top=e; S.top++;} return OK; } top A B 压栈操作 top A B e base base
栈的销毁 void Destroy Stack_Sq(Stack &S) 结 if (S base) free(S base); S base=NULL; S top=NULL S stacks 栈的清除 5 void Clear Stack_ Sq(Stack &s) Stop=S base 判断栈是否为空栈 据 Status Stack Empty Sq(Stack S) 构 if(S. top-==S base) return TRUE else return false 获得栈的实际长度 队 int StackLength Sq(stack S) n(abs(s top-S base)
4 数 据 结 构 之 栈 和 队 列 7 ¾栈的销毁 void DestroyStack_Sq(Stack &S){ if (S.base) free(S.base); S.base=NULL;S.top=NULL; S.stacksize=0; } ¾栈的清除 void ClearStack_Sq(Stack &S){ S.top = S.base ; } 数 据 结 构 之 栈 和 队 列 8 ¾判断栈是否为空栈 Status StackEmpty_Sq(Stack S){ if(S.top==S.base) return TRUE; else return FALSE; } ¾获得栈的实际长度 int StackLength_Sq(Stack S){ return(abs(S.top-S.base)); }
多个栈共享邻接空间 结 地址 中间可用空间 两个栈共享一空间 3.3栈与递归 >递归函数:一个直接调用自己或通 过一系列的调用语句间接地调用自 己的函数 调用函数前,系统需先完成三件事: 将所有的实在参数、返回地址等信息传 递给被调用函数保存; 队 为被调用函数的局部变量分配存储区 将控制转移到被调用函数的入口
5 数 据 结 构 之 栈 和 队 列 9 ¾ 多个栈共享邻接空间 两个栈共享一空间 : : : : : : top1 top2 1 m 中间可用空间 栈1 栈2 地址 Base1 Base 2 …… 数 据 结 构 之 栈 和 队 列 10 3. 3 栈 与 递归 ¾ 递归函数：一个直接调用自己或通 过一系列的调用语句间接地调用自 己的函数。 ¾ 调用函数前，系统需先完成三件事： ¾将所有的实在参数、返回地址等信息传 递给被调用函数保存； ¾为被调用函数的局部变量分配存储区； ¾将控制转移到被调用函数的入口