栈的数组实现

 1         typedef int ElementType;
 2 /* START: fig3_45.txt */
 3         #ifndef _Stack_h
 4         #define _Stack_h
 5 
 6         struct StackRecord;
 7         typedef struct StackRecord *Stack;
 8 
 9         int IsEmpty( Stack S );
10         int IsFull( Stack S );
11         Stack CreateStack( int MaxElements );
12         void DisposeStack( Stack S );
13         void MakeEmpty( Stack S );
14         void Push( ElementType X, Stack S );
15         ElementType Top( Stack S );
16         void Pop( Stack S );
17         ElementType TopAndPop( Stack S );
18 
19         #endif  /* _Stack_h */
20 
21 /* END */

  1         #include "stackar.h"
  2         #include "fatal.h"
  3         #include <stdlib.h>
  4 
  5         #define EmptyTOS ( -1 )
  6         #define MinStackSize ( 5 )
  7 
  8         struct StackRecord
  9         {
 10             int Capacity;
 11             int TopOfStack;
 12             ElementType *Array;
 13         };
 14 
 15 /* START: fig3_48.txt */
 16         int
 17         IsEmpty( Stack S )
 18         {
 19             return S->TopOfStack == EmptyTOS;
 20         }
 21 /* END */
 22 
 23         int
 24         IsFull( Stack S )
 25         {
 26             return S->TopOfStack == S->Capacity - 1;
 27         }
 28 
 29 /* START: fig3_46.txt */
 30         Stack
 31         CreateStack( int MaxElements )
 32         {
 33             Stack S;
 34 
 35 /* 1*/      if( MaxElements < MinStackSize )
 36 /* 2*/          Error( "Stack size is too small" );
 37 
 38 /* 3*/      S = malloc( sizeof( struct StackRecord ) );
 39 /* 4*/      if( S == NULL )
 40 /* 5*/          FatalError( "Out of space!!!" );
 41 
 42 /* 6*/      S->Array = malloc( sizeof( ElementType ) * MaxElements );
 43 /* 7*/      if( S->Array == NULL )
 44 /* 8*/          FatalError( "Out of space!!!" );
 45 /* 9*/      S->Capacity = MaxElements;
 46 /*10*/      MakeEmpty( S );
 47 
 48 /*11*/      return S;
 49         }
 50 /* END */
 51 
 52 /* START: fig3_49.txt */
 53         void
 54         MakeEmpty( Stack S )
 55         {
 56             S->TopOfStack = EmptyTOS;
 57         }
 58 /* END */
 59 
 60 /* START: fig3_47.txt */
 61         void
 62         DisposeStack( Stack S )
 63         {
 64             if( S != NULL )
 65             {
 66                 free( S->Array );
 67                 free( S );
 68             }
 69         }
 70 /* END */
 71 
 72 /* START: fig3_50.txt */
 73         void
 74         Push( ElementType X, Stack S )
 75         {
 76             if( IsFull( S ) )
 77                 Error( "Full stack" );
 78             else
 79                 S->Array[ ++S->TopOfStack ] = X;
 80         }
 81 /* END */
 82 
 83 
 84 /* START: fig3_51.txt */
 85         ElementType
 86         Top( Stack S )
 87         {
 88             if( !IsEmpty( S ) )
 89                 return S->Array[ S->TopOfStack ];
 90             Error( "Empty stack" );
 91             return 0;  /* Return value used to avoid warning */
 92         }
 93 /* END */
 94 
 95 /* START: fig3_52.txt */
 96         void
 97         Pop( Stack S )
 98         {
 99             if( IsEmpty( S ) )
100                 Error( "Empty stack" );
101             else
102                 S->TopOfStack--;
103         }
104 /* END */
105 
106 /* START: fig3_53.txt */
107         ElementType
108         TopAndPop( Stack S )
109         {
110             if( !IsEmpty( S ) )
111                 return S->Array[ S->TopOfStack-- ];
112             Error( "Empty stack" );
113             return 0;  /* Return value used to avoid warning */
114         }
115 /* END */