栈的数组实现

  1 /*
  2   栈的数组实现
  3 */
  4 
  5 /*接口头文件*/
  6 
  7 typedef int ElementType;
  8 #ifndef _STACK_H
  9 #define _STACK_H
 10 #include <stdbool.h>
 11 struct StackRecord;
 12 typedef struct StackRecord * Stack;
 13 
 14 /*操作集*/
 15 bool IsEmpty( Stack S );
 16 bool IsFull( Stack S );
 17 Stack CreateStack( int MaxElements );
 18 void MakeEmpty( Stack S );
 19 void Push( ElementType X, Stack S );
 20 void Pop( Stack S );
 21 ElementType Top( Stack S );
 22 void DisposeStack( Stack S );
 23 void PrintfStack( Stack S );
 24 
 25 #endif
 26 
 27 
 28 /*接口实现*/
 29 #include <stdio.h>
 30 #include <stdlib.h>
 31 #include "stack.h"
 32 
 33 #define EMPTYTOS ( -1 )        //空栈标志 
 34 #define MinStackSize ( 5 )     //指定栈的最小空间
 35 
 36 /*特定结构体定义*/
 37 struct StackRecord
 38 {
 39     int Capacity;   //栈空间大小
 40     int TopOfStack; //栈顶。当其值为0，则栈为空
 41     ElementType * Array; //存储数据 
 42 };
 43 
 44 /*由MaxElements指定栈的大小*/ 
 45 Stack CreateStack( int MaxElements )
 46 {
 47     Stack S;
 48     
 49     if ( MaxElements < MinStackSize )
 50     {
 51        printf( "Stack is smallr
" );
 52        exit( 1 );
 53     }
 54     S = ( Stack )malloc( sizeof( struct StackRecord ) );
 55     if ( S == NULL )
 56     {
 57        printf( "No Space!!!
" );
 58        exit( 1 );
 59     }
 60     S->Array = ( ElementType )malloc( sizeof( ElementType ) * MaxElements );
 61     if ( S->Array == NULL )
 62     {
 63        printf( "No Space!!!
" );
 64        exit( 1 );
 65     }
 66     S->Capacity = MaxElements;
 67     MakeEmpty( S );
 68     
 69     return S;
 70 }
 71 
 72 void MakeEmpty( Stack S )
 73 {
 74     S->TopOfStack = EMPTYTOS;
 75 }
 76 
 77 bool IsEmpty( Stack S )
 78 {
 79     return S->TopOfStack == EMPTYTOS;
 80 }
 81 
 82 bool IsFull( Stack S )
 83 {
 84     return S->TopOfStack == S->Capacity - 1;
 85 }
 86 
 87 void Push( ElementType X, Stack S )
 88 {
 89     if ( IsFull( S ) )
 90     {
 91        printf( "Stack is full
" );
 92        exit( 1 );
 93     }
 94     else
 95         S->Array[ ++S->TopOfStack ] = X;
 96 }
 97 
 98 void Pop( Stack S )
 99 {
100     if ( IsEmpty( S ) )
101     {
102        printf( "Stack is empty
" );
103        exit( 1 );
104     }
105     else
106         S->TopOfStack--;
107 }
108 
109 ElementType Top( Stack S )
110 {
111     if ( IsEmpty( S ) )
112     {
113        printf( "Stack is empty
" );
114        exit( 1 );
115     }
116     else
117         return S->Array[ S->TopOfStack ];
118 }
119 
120 void DisposeStack( Stack S )
121 {
122     free( S->Array );
123     free( S );
124 }
125 
126 void PrintfStack( Stack S )
127 {
128     if ( IsEmpty( S ) )
129        printf( "No Data
" );
130     else
131         for ( int i = S->TopOfStack; i >=0; i-- )
132             printf( "%3d", S->Array[ i ] );
133             
134     printf( "
" );
135 }