axSize-1 初始状态 b0] 612 b{3 b(5] t2] t3 maxSize-1 V 某时刻状态 610 6[21 b{3 b(4] b5] t1插入图→t2→+31 maxSize-1 Bm插入x之后 b0] 612 b3] 614 65 2]→3 插入新元素时的栊满处理 Stack Full()
插入新元素时的栈满处理 StackFull ( )
template <class Type> void Push( const int i, const Type item)t if(t团=b+11)SacF(),式 else++=item;/第i个 进栈 template <class Type> Type *Pop( const i)( if(=b引) i StackEmpty(i; return 0; j else return&it-];第i个栈出栈
template <class Type> void Push ( const int i, const Type & item ) { if ( t [i] == b[i+1] ) StackFull (i); else V[++t[i]] = item; //第i 个栈进栈 } template <class Type> Type *Pop ( const i) { if ( t[i] == b[i] ) { StackEmpty(i); return 0; } else return & V[t[i]--]; //第i 个栈出栈 }
栈的链接表示一链式栈 ∧ 链式栈无栈满问题,空间可 扩充 插入与删除仅在栈顶处执行 链式栈的栈顶在链头 适合于多栈操作
链式栈( Linkedstack)类的定义 template <class Type> class Stack template <class Type> class StackNode i friend class Stack<Type>, rivate Ty ype aatag /结点数据 Stacknode<ype>*ink;∥结点链指针 StackNode( type d=0, StackNode< Type> LENULL): data(d), link2)d
template <class Type> class Stack; template <class Type> class StackNode { friend class Stack<Type>; private: Type data; //结点数据 StackNode<Type> *link; //结点链指针 StackNode ( Type d=0, StackNode<Type> *l=NULL ) : data (d), link (l) { } };
template <class Type> class Stack i ublic Stack(: top(null)& Stack( void Push( const Type item); Type Pop (; Type GetTop o; void MakeEmpty (i top=NULL; 3 int IsEmpty( const f return top==NULL; 3 private Stacknode<Type>*top;∥l顶指针
template <class Type> class Stack { public: Stack ( ) : top ( NULL ) { } ~Stack ( ); void Push ( const Type & item); Type Pop ( ); Type GetTop ( ); void MakeEmpty ( ) { top=NULL; } int IsEmpty ( ) const { return top == NULL; } private: StackNode<Type> *top; //栈顶指针 }