0多栈共享存区的链接分配一链 第三章栈和队列 个链栈由其栈顶指针1s唯一确定 多个链栈可共享内存中的堆(heap)区域。 链栈为满的条件:堆区满。new(p)过程无法实现内存 分配 data next 栈顶 ∧栈底 第21页
第三章 栈和队列 第21页 一个链栈由其栈顶指针ls唯一确定。 多个链栈可共享内存中的堆(heap)区域。 链栈为满的条件：堆区满。new(p)过程无法实现内存 分配。 ^ ls data next 栈顶 栈底 ⚫ 多栈共享存储区的链接分配——链栈
找的表示和实现 第三章栈和队列 PushStack (lkstktp &ls; elemtp x) 算法中p为结点类型指针变量 p new(ElemType)i p->elem xi p->next= ls; //push stack elemtp Pop Stack(lkstktp &ls /算法中p为结点类型指针变量 i￡(1s==NULL) return Nul//pop为 elemtp类型变量 p= ls;ls= p->nexti pop p->elemi free(p) re turn pop i //pop stack 第22页
第三章 栈和队列 第22页 PushStack(lkstktp &ls; elemtp x) { //算法中p为结点类型指针变量 p = new(ElemType); p->elem = x; p->next = ls; ls = p } //push_stack elemtp PopStack(lkstktp &ls) { //算法中p为结点类型指针变量 if( ls == NULL ) return NULL // pop为elemtp类型变量 p = ls; ls = p->next; pop = p->elem; free(p); return pop; } //pop_stack ⚫ 栈的表示和实现
两个共享一个存储区 第三章栈和队列 且的:提高存储空间的使用效率,并减少发生栈上溢的可能性。 示例两个栈共享一维数组空间 空闲区 栈1底 栈1顶 栈2顶栈2底 栈可利用的最大室间:有可能大于整个数组的一半 上溢情况:两个栈顶相遇 双栈的类C描述 # define m= mansize;/′两个栈的容量之和 Elemtp=任何一种数据类型 struct dustktpi elemtp elem[m] i int top[2] }; 第23页
第三章 栈和队列 第23页 目的：提高存储空间的使用效率，并减少发生栈上溢的可能性。 示例 两个栈共享一维数组空间 栈可利用的最大空间：有可能大于整个数组的一半。 上溢情况：两个栈顶相遇。 双栈的类C描述 #define m = maxsize; // 两个栈的容量之和 Elemtp = 任何一种数据类型 struct dustktp{ elemtp elem[m]; int top[2]; }; 空闲区 栈1底 栈1顶 栈2顶 栈2底 ⚫ 两个栈共享一个存储区
两个共享一个存储区 第三章栈和队列 init stack( dustktp &s, int sno) i(sno==1)s.t。p[0]=0; else s top[1]= m +1 }//: init stack push stack( dus tktp &s, elemtp x, int sno if(s,top[0]+1=s.t。P[1]) return stack over flow switch( sno)[ case 1: s top[0]++; breaki case 2:s top[1]--; break i } s,eLem[s.t。p[sn。-1]]=x 3 //push stack 第24页
第三章 栈和队列 第24页 init_stack( dustktp &s, int sno) { if( sno == 1 ) s.top[0] = 0; else s.top[1] = m + 1 } //init_stack push_stack( dustktp &s, elemtp x, int sno ) { if( s.top[0]+1 == s.top[1] ) return stack_over_flow; switch( sno ){ case 1: s.top[0]++; break; case 2: s.top[1]--; break; } s.elem[s.top[sno-1]] = x } //push_stack ⚫ 两个栈共享一个存储区
两个共享一个存储区 第三章栈和队列 status pop stack( dustktp &s elemyp &x, int sno if( empty( s, sno ) return stack under flow x= selem [s top [sno-1]] switch( sno )I case l:s top [0] breaki case 2: s top[1]++i break i //pop stack Status gettop stack(dustktp s,, elemyp &x int sno) if( empty(s, sno)) return stack empty s elem [s top[sno-1]] //top stack 第25页
第三章 栈和队列 第25页 Status pop_stack( dustktp &s, elemyp &x,int sno ) { if( empty( s, sno )) return stack_under_flow; x = s.elem[s.top[sno-1]]; switch( sno ){ case 1:s.top[0]--; break; case 2:s.top[1]++; break; } } //pop_stack Status gettop_stack(dustktp s,elemyp &x, int sno) { if( empty(s,sno)) return stack_empty; s.elem[s.top[sno-1]] } // top_stack ⚫ 两个栈共享一个存储区