栈 ADT (数组实现)
头文件
#ifndef _Stack_Array_H
struct StackRecord;
typedef struct StackRecord *Stack;
int IsEmpty( Stack S );
int IsFull( Stack S );
Stack CreateStack( int MaxElements );
void DisposeStack( Stack S );
void MakeEmpty( Stack S );
void Push( ElementType X, Stack S );
ElementType Top( Stack S )
void Pop( Stack S );
ElementType TopAndPop( Stack S );
#endif /*_Stack_Array_H*/
/* Place in implementation file */
/* Stack implementation is a dynamically allocated array */
#define EmptyTOS ( -1 )
#define MinStackSize ( 5 )
struct StackRecord
{
int Capacity;
int TopOfStack;
ElementType *Array;
};
详细例程
Stack CreateStack( int MaxElements )
{
StackRecord S;
if( MaxElements < MinStackSize )
Error( "Stack size is too small!" );
S = malloc( sizeof ( struct StackRecord ) );
if( S == NULL )
FatalError( "Out of space !!!" );
S->Array = malloc( sizeof ( ElementType ) * MaxElements );
if( S->Array == NULL )
FatalError( "Out of space!!!" );
S->Capacity = MaxElements;
MakeEmpty( S );
return S;
}
void MakeEmpty( Stack S )
{
S->TopOfStack = EmptyTOS;
}
void DisposeStack( Stack S )
{
if( S != NULL )
{
free( S-> Array );
free( S );
}
}
int IsEmpty( Stack S )
{
return S->TopOfStack == EmptyTOS;
}
void Push( ElementType X, Stack S )
{
if( IsFull( S ) )
Error( "Full stack!" );
else
S->Array[ ++S->TopOfStack ] = X;
}
ElementType Top( Stack S )
{
if( !IsEmpty( S ) )
return S->Array[ S->TopOfStack-- ];
Error( "Empty stack!" );
return 0;
}
void Pop( Stack S )
{
if( IsEmpty( S ) )
Error( "Empty stack!" );
else
S->TopOfStack--;
}
ElementType TopAndPop( Stack S )
{
if( !IsEmpty( S ) )
return S->Array[ S->TopOfStack-- ];
Error( "Empty Stack" );
return 0;
}