栈的链式实现

 1         typedef int ElementType;
 2 /* START: fig3_39.txt */
 3         #ifndef _Stack_h
 4         #define _Stack_h
 5 
 6         struct Node;
 7         typedef struct Node *PtrToNode;
 8         typedef PtrToNode Stack;
 9 
10         int IsEmpty( Stack S );
11         Stack CreateStack( void );
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 
18         #endif  /* _Stack_h */
19 
20 /* END */

 1         #include "stackli.h"
 2         #include "fatal.h"
 3         #include <stdlib.h>
 4 
 5         struct Node
 6         {
 7             ElementType Element;
 8             PtrToNode   Next;
 9         };
10 
11 /* START: fig3_40.txt */
12         int
13         IsEmpty( Stack S )
14         {
15             return S->Next == NULL;
16         }
17 /* END */
18 
19 /* START: fig3_41.txt */
20         Stack
21         CreateStack( void )
22         {
23             Stack S;
24 
25             S = malloc( sizeof( struct Node ) );
26             if( S == NULL )
27                 FatalError( "Out of space!!!" );
28             S->Next = NULL;
29             MakeEmpty( S );
30             return S;
31         }
32 
33         void
34         MakeEmpty( Stack S )
35         {
36             if( S == NULL )
37                 Error( "Must use CreateStack first" );
38             else
39                 while( !IsEmpty( S ) )
40                     Pop( S );
41         }
42 /* END */
43 
44         void
45         DisposeStack( Stack S )
46         {
47             MakeEmpty( S );
48             free( S );
49         }
50 
51 /* START: fig3_42.txt */
52         void
53         Push( ElementType X, Stack S )
54         {
55             PtrToNode TmpCell;
56 
57             TmpCell = malloc( sizeof( struct Node ) );
58             if( TmpCell == NULL )
59                 FatalError( "Out of space!!!" );
60             else
61             {
62                 TmpCell->Element = X;
63                 TmpCell->Next = S->Next;
64                 S->Next = TmpCell;
65             }
66         }
67         //有头节点，栈顶是第一个节点，入栈是插到第一个节点前面，变成第一个节点
68         //这样出栈方便
69 /* END */
70 
71 /* START: fig3_43.txt */
72         ElementType
73         Top( Stack S )
74         {
75             if( !IsEmpty( S ) )
76                 return S->Next->Element;
77             Error( "Empty stack" );
78             return 0;  /* Return value used to avoid warning */
79         }
80 /* END */
81 
82 /* START: fig3_44.txt */
83         void
84         Pop( Stack S )
85         {
86             PtrToNode FirstCell;
87 
88             if( IsEmpty( S ) )
89                 Error( "Empty stack" );
90             else
91             {
92                 FirstCell = S->Next;
93                 S->Next = S->Next->Next;
94                 free( FirstCell );
95             }
96         }
97 /* END */