栈 ADT
头文件

#ifndef _Stack_H

struct Node;
typedef struce Node *PtrToNode;
typedef PtrToNode Stack;

int IsEmpty( Stack S );
Stack CreateStack( void );
void DisposeStack( Stack S );
void MakeEmpty( Stack S );
void Push( ElementType X, Stack S );
ElementType Top( Stack S );
void Pop( Stack S );

#endif /*_Stack_H*/

/* Place in implementation file */
/* Stack implementation is a linked list with a header */
struct Node
{
	ElementType Element;
	PtrToNode Next;
}

关键例程

int IsEmpty( Stack S )
{
	return S->Next == NULL;
}

Stack CreateStack( void )
{
	Stack S;

	S = malloc( sizeof ( struct Node ) );
	if( S == NULL )
		FatalError( "Out of space!!!" );
	S->Next = NULL;
	MakeEmpty( S );
	return S;
}

void MakeEmpty( Stack S )
{
	if( S == NULL )
		Error( "Must use CreateStack First" );
	else
		while( !IsEmpty( S ) )
			Pop( S );
}

void Pop( Stack S )
{
	PtrToNode TempNode;

	if( IsEmpty( S ) )
		Error( "Empty Stack" );
	else
	{
		TempNode = S->Next;
		S->Next = S->Next->Next;
		free( TempNode );
	}
}

void Push( ElementType X, Stack S )
{
	PtrToNode TempNode;

	TempNode = malloc( sizeof ( struct Node ) );
	if( TempNode == NULL )
		Error( "Out of space !!!" );
	else
	{
		TempNode->Element = X;
		TempNode->Next = S->Next;
		S->Next = TempNode;
	}
}

ElementType( Stack S )
{
	if( !IsEmpty( S ) )
		return S->Next->Element;
	else
		Error( "Empty Stack" );
	return 0;/*return value used to avoid warning*/
}