首页 > 代码库 > 算法导论 10.1-2 用一个数组实现两个栈
算法导论 10.1-2 用一个数组实现两个栈
一、题目
用一个数组A[ 1....N ]实现两个栈，除非数组的每一个单元都被使用，否则栈例程不能有溢出，注意PUSH和POP操作的时间应为O(1)。
二、解法
对于一个数组，由它的两端作为栈底，栈向数组中间扩展。当数组中每个元素被用到时，栈满。
三、代码
struct Node;typedef Node *ComStack;struct Node{ int Capacity; int TopL; int TopR; ElementType *Array;};ComStack CreatComStack( int MaxElements );int IsEmpty_L( ComStack S );int IsEmpty_R( ComStack S );int IsFull( ComStack S );void MakeEmpty( ComStack S );void Push_L( ElementType X, ComStack S );void Push_R( ElementType X, ComStack S );ElementType Pop_L( ComStack S );ElementType Pop_R( ComStack S );void DisposeComStack( ComStack S );ComStack CreatComStack( int MaxElements ){ ComStack S; S = (ComStack)malloc( sizeof(struct Node) ); if ( S == NULL ) { printf( "Out of space" ); return NULL; } S->Array = (ElementType *)malloc( sizeof(ElementType) * MaxElements ); if ( S->Array == NULL ) { printf( "Out of space" ); return NULL; } S->Capacity = MaxElements; MakeEmpty(S); return S;}int IsEmpty_L( ComStack S ){ if ( S->TopL == -1 ) return true; else return false;}int IsEmpty_R( ComStack S ){ if ( S->TopR == S->Capacity ) return true; else return false;}int IsFull( ComStack S ){ if ( S->TopL + 1 == S->TopR ) return true; else return false;}void MakeEmpty( ComStack S ){ S->TopL = -1; S->TopR = S->Capacity; // Capacity在数组界外}void Push_L( ElementType X, ComStack S ){ if ( IsFull(S) ) printf( "Stack is full" ); else { S->TopL++; S->Array[S->TopL] = X; }}void Push_R( ElementType X, ComStack S ){ if ( IsFull(S) ) printf( "Stack is full" ); else { S->TopR--; S->Array[S->TopR] = X; }}ElementType Pop_L( ComStack S ){ ElementType TmpCell; if ( IsEmpty_L(S) ) printf( "Left Stack is empty" ); else { TmpCell = S->Array[S->TopL]; S->TopL--; } return TmpCell;}ElementType Pop_R( ComStack S ){ ElementType TmpCell; if ( IsEmpty_R(S) ) printf( "Right stack is empty" ); else { TmpCell = S->Array[S->TopR]; S->TopR++; } return TmpCell;}void DisposeComStack( ComStack S ){ if ( S != NULL ) { free( S->Array ); free( S ); }}
算法导论 10.1-2 用一个数组实现两个栈
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。