栈的链表实现(缺点：对malloc和free的调用的开销昂贵)
栈ADT链表实现的类型声明
#ifndef _Stack_h struct Node; typedef struct Node *PtrToNode; typedef PtrToNode Stack; int IsEmpty( Stack S ); Stack CreateStack( void ); void DisposeStack( Stack S ); void MakeEmpty( Stack S ); void Push( ElementTyep 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!\n" ); } 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 ); }
Push进栈
void Push( ElementType X, Stack S ) { PtrToNode TmpCell; TmpCell = malloc( sizeof( struct Node ) ); if( TmpCell == NULL ) FatalError( "Out of sapce !" ); else { TmpCell->Element = X; TmpCell->Next = S->Next; S->Next = TmpCell; } }
返回栈顶元素
ElementType Top( Stack S ) { if( !IsEmpty( S ) ) return S->Next->Element; Error( "Empty stack" ); return 0; /* Return value used to avoid warning */ }
Pop出栈
void Pop( Stack S ) { PtrToNode FirstCell; if( IsEmpty( S ) ) Error( "Empty stack" ); else { FirstCell = S->Next; S->Next = S->Next->Next; free( FirstCell ); } }
栈的数组实现（避免使用指针并且可能是更流行的解决方案，这种策略的唯一潜在问题是我们需要提前声明一个数组的大小。不过，一般来说，这并不是一个问题，因为在典型的应用程序中，即使有相当多的栈操作，在任一时刻栈元素的实际个数从不会太大。声明一个数组足够大而不至于浪费太多的空间通常并没有什么困难。如果不能做到这一点，那么节省的做法是使用链表来实现。）栈的数组实现的类型声明
#ifndef _Stack_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_h */ /* place in implementation file */ /* Stack implementaion is a dynamically allocated array */ #define EmptyTOS ( -1 ) #define MinStackSize ( 5 ) struct StackRecord { int Capacity; int TopOfStack; ElementType *Array; };
栈的创建
Stack CreateStack( int MaxElements ) { Stack 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 DisposeStack( Stack S ) { if( S != NULL ) { free( S->Array ); free( S ); } }
检测一个栈是否为空
int IsEmpty( Stack S ) { return S->TopOfStack == EmptyTOS; }
创建一个空栈
void MakeEmpty( Stack S ) { 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; /* return value used to avoid warning */ }
从栈弹出元素
void Pop( Stack S ) { if( IsEmpty( S ) ) Error( "Empty stack" ); esle S->TopOfStack--; }
返回栈顶元素并将其从栈弹出
ElementType TopAndPop( Stack S ) { if( !IsEmpty( S ) ) return S->Array[ S->TopOfStack-- ]; Error( "Empty satck" ); return 0; /* return value used to avoid warning */ }
原文：http://www.cnblogs.com/nufangrensheng/p/3608736.html