栈的数组实现

stackar.h

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

stackar.c

  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 
 17         /* 判断栈是否为空 */
 18         int
 19         IsEmpty( Stack S )
 20         {
 21             return S->TopOfStack == EmptyTOS;
 22         }
 23 /* END */
 24 
 25         /*判断栈是否满了 */
 26         int
 27         IsFull( Stack S )
 28         {
 29             return S->TopOfStack == S->Capacity - 1;
 30         }
 31 
 32 /* START: fig3_46.txt */
 33 
 34         /* 创建一个空栈 */
 35         Stack
 36         CreateStack( int MaxElements )
 37         {
 38             Stack S;
 39 
 40 /* 1*/      if( MaxElements < MinStackSize )
 41 /* 2*/          Error( "Stack size is too small" );
 42 
 43 /* 3*/      S = malloc( sizeof( struct StackRecord ) );
 44 /* 4*/      if( S == NULL )
 45 /* 5*/          FatalError( "Out of space!!!" );
 46 
 47 /* 6*/      S->Array = malloc( sizeof( ElementType ) * MaxElements );
 48 /* 7*/      if( S->Array == NULL )
 49 /* 8*/          FatalError( "Out of space!!!" );
 50 /* 9*/      S->Capacity = MaxElements;
 51 /*10*/      MakeEmpty( S );
 52 
 53 /*11*/      return S;
 54         }
 55 /* END */
 56 
 57 /* START: fig3_49.txt */
 58 
 59         /* 使栈顶指向-1，即空栈 */
 60         void
 61         MakeEmpty( Stack S )
 62         {
 63             S->TopOfStack = EmptyTOS;
 64         }
 65 /* END */
 66 
 67 /* START: fig3_47.txt */
 68 
 69         /* 释放栈 */
 70         void
 71         DisposeStack( Stack S )
 72         {
 73             if( S != NULL )
 74             {
 75                 free( S->Array );
 76                 free( S );
 77             }
 78         }
 79 /* END */
 80 
 81 /* START: fig3_50.txt */
 82 
 83         /* 入栈 */
 84         void
 85         Push( ElementType X, Stack S )
 86         {
 87             if( IsFull( S ) )
 88                 Error( "Full stack" );
 89             else
 90                 S->Array[ ++S->TopOfStack ] = X;
 91         }
 92 /* END */
 93 
 94 
 95 /* START: fig3_51.txt */
 96 
 97         /* 返回栈顶元素 */
 98         ElementType
 99         Top( Stack S )
100         {
101             if( !IsEmpty( S ) )
102                 return S->Array[ S->TopOfStack ];
103             Error( "Empty stack" );
104             return 0;  /* Return value used to avoid warning */
105         }
106 /* END */
107 
108 /* START: fig3_52.txt */
109 
110         /* 出栈 */
111         void
112         Pop( Stack S )
113         {
114             if( IsEmpty( S ) )
115                 Error( "Empty stack" );
116             else
117                 S->TopOfStack--;
118         }
119 /* END */
120 
121 /* START: fig3_53.txt */
122 
123         /* 返回栈顶元素和出栈 */
124         ElementType
125         TopAndPop( Stack S )
126         {
127             if( !IsEmpty( S ) )
128                 return S->Array[ S->TopOfStack-- ];
129             Error( "Empty stack" );
130             return 0;  /* Return value used to avoid warning */
131         }
132 /* END */