栈的ADT表示 第三章栈和队列 Elemfp Pop( SastkTp &s )i ∥若栈不空,则删去栈顶元素并返回元素值,否则返回空元素 NULL ElemTp GetTop(sastkrp s)i 一若栈不空,则返回栈顶元素,但stop ∥保持不变,香则返回空元素NULL Clearstack(sastkTp &s )i 若S为空栈,即stop=0 int Currentsize(sastkIp s )i 一/返回当前栈中元素个数,即stop 第16页
第三章 栈和队列 第16页 ElemTp Pop( SqStkTp &s ); //若栈不空，则删去栈顶元素并返回元素值，否则返回空元素 NULL ElemTp GetTop(SqStkTp s ); //若栈不空，则返回栈顶元素，但s.top //保持不变，否则返回空元素NULL ClearStack(SqStkTp &s ); //若S为空栈，即s.top=0 int CurrentSize(SqStkTp s ); //返回当前栈中元素个数，即s.top 栈的ADT表示
栈的ADT实现 第三章栈和队列 部分实现 Initstack( Sastkrp &s [ S top 0 B//init stack Status isstackEmpty(sastkTp s return( s top ==0)? True Falsei i//empty stack Status Push( SastkTp &s, ElemTp x if( s top = MAX STACK return false, s. top++i s elem [s top]=xi return True; 1 //push stack 第17页
第三章 栈和队列 第17页 部分实现 InitStack( SqStkTp &s) { s.top = 0 }//init_stack Status isStackEmpty(SqStkTp s) { return ( s.top == 0 ) ? True : False; } //empty_stack Status Push( SqStkTp &s, ElemTp x ) { if( s.top == MAX_STACK ) return false; s.top++; s.elem[s.top] = x; return True; } //push_stack 栈的ADT实现
栈的ADT实现 第三章栈和队列 ElemTp Pop( SqstkTp &s) if(s top return s. top--i return selem [s top+l —//pop- stack ElemT'p GetTop( Sastkfp s if(s.t。p==0) eturn; return s.eLem[s.t。p] )//gettop stack Clearstack( SqstkTp &s) s top 0 i //clear stack 第18页
第三章 栈和队列 第18页 ElemTp Pop( SqStkTp &s ) { if( s.top == 0 ) return; s.top--; return s.elem[s.top+1] } //pop_stack ElemTp GetTop( SqStkTp s ) { if( s.top == 0 ) return; return s.elem[s.top] } //gettop_stack ClearStack( SqStkTp &s ) { s.top = 0 } //clear_stack 栈的ADT实现
第三章栈和队列 栈的ADT实现 int Currentsize (SastkTp s) return s. top; )//currend size stack 注1.函数 isStackEmpty的体亦可写为 return(s top==0)i 注2.亦可在接口节定义判栈满函数 Status is StackEulL (SastkTp s) reutrn s top = MAX STACK //full stack 第19页
第三章 栈和队列 第19页 int CurrentSize (SqStkTp s ) { return s.top; } //currend_size_stack 注1. 函数isStackEmpty的体亦可写为 return ( s.top == 0 ); 注2. 亦可在接口节定义判栈满函数 Status isStackFull (SqStkTp s) { reutrn ( s.top == MAX_STACK ) } //full_stack 栈的ADT实现
找的表示和实现 第三章栈和队列 链式栈—栈的链式存储结构 设不带头结点 栈顶 栈底 栈空:1=NU 栈满:当内存分配无法实现时(堆区满); 进栈:在表头插入; 出栈:从表头删除; 即进栈、出栈操作均限制在单链表的表头端进行 数据结构的描述 elemtype//任何一种数据类型 typedef struct tlkstktp i ELemfype elem; tlkstktp *Next }*1 sttp冫 第20页
第三章 栈和队列 第20页 栈空：ls == NULL; 栈满：当内存分配无法实现时（堆区满）; 进栈：在表头插入; 出栈：从表头删除; 即进栈、出栈操作均限制在单链表的表头端进行。 数据结构的描述 elemtype … … //任何一种数据类型 typedef struct tlkstktp{ ElemType elem; tlkstktp *Next } *lkstktp; … ^ Ls 栈顶 栈底 链式栈——栈的链式存储结构 设不带头结点 ⚫ 栈的表示和实现