データ構造——スタック、シーケンススタック、ダブルスタックは同じスタック空間、チェーンスタックを共有する.

  1 // ，    、      
  2 
  3 
  4 //                         ，       ，        ，           
  5 #define maxSize 100   //       
  6 typedef int SElemType;
  7 typedef struct
  8 {
  9     SElemType elem[maxSize];
 10     int top;
 11 }SeqStack;
 12 
 13 //          
 14 #define initSize 100   //       
 15 typedef int SElemType;//       
 16 typedef struct//        
 17 {
 18     SElemType *elem;//       
 19     int maxSIze, top;//            (  )
 20 }SeqStack;
 21 //        
 22 void InitStack(SeqStack& S)
 23 {//         initSize   ，             
 24     S.elem = new SElemType[initSize];
 25     if(!S.elem){cerr<

 37 //         ，        
 38 void OverflowProcess(SeqStack S)
 39 {
 40     SElemType *newArray = new SElemType[S.maxSize*2];
 41     if(!newArray){cerr<

 74 //      
 75 int StackSize(SeqStack& S)
 76 {
 77     return S.top+1;//     S   ，  S      
 78 }

 81 //           ，           Vector[maxSize],       0   1  。                ，
 82 // b[0](=-1) b[1](=maxSize)  。
 83 //    ：  0  ，         t[0] 1;  1  ，         t[1] 1。           ，
 84 // t[0] + 1 == t[1]    
 85 //    ：  0  ，         t[0] 1;  1  ，         t[1] 1.               。
 86 //       。
 87 
 88 //               
 89 int push(DualStack& DS, SElemType x, int d)
 90 {// d          x。d=0,  0  ;d=1,  1  ，     ，    1,    0
 91     if(DS.t[0]+1 == DS.t[1] || d != 0 && d !=1)
 92         return 0;
 93     if(d == 0)
 94         DS.t[0]++;//     1
 95     else
 96         DS.t[1]--;//   1
 97     DS.Vector[DS.t[d]] = x;//  
 98     return 1;
 99 }
100 //              
101 int pop(DualStack& DS, SElemType& x, int d)
102 {// d            ，       x  。d=0, 0    ;d=1, 1    。     ，    1,      0
103     if(d != 0 && d != 1 || DS.t[d] == DS.b[d])
104         return 0;
105     x= DS.Vector[DS.t[d]];//        
106     if(d == 0)//     1
107         DS.t[0]--;
108     else
109         DS.t[1]++;
110     return 1;
111 }

116 //   
117 //           ，          ，               ，            ，         
118 //     。              ，                   。  ，                  
119 //                      。            ，            ，           
120 //   ，                。
121 
122 //      
123 typedef int SElemType;
124 typedef struct node
125 {
126     SElemType data;
127     struct node *link;
128 }LinkNode, *LinkStack ;
129 
130 void InitStack(LinkStack& S)
131 {//      ：     ，        
132     S = new LinkNode;//    
133     if(!S){cerr<link = NULL;//    
135 }
136 void Push(LinkStack& S, SElemType x)
137 {//  ：   x         ，    
138     LinkNode *p = new LinkNode;//     
139     if(!p){cer<data = x;
141     p->link = S->link;//         
142     S->link = p;
143 }
144 int Pop(LinkStack& S, SElemType& x)
145 {//  ：    ，              x          ，     ，    1,      0,  x      
146     if(S->link == NULL)//       ，  0
147         return 0;
148     LinkNode *p = S->link;//        
149     S->link = p->link;//             
150     x = p->data;//    ，        
151     delete p;//
152     return 1;
153 }

154 int GetTop(LinkStack& S, SElemType& x)
155 {//    ：    ，       x        ，     1,   ，    0,  x      
156     if(S->link == NULL)return 0;//      0
157     x = S->link->data;//            
158     return 1;
159 }
160 int StackEmpty(LinkStack& S)
161 {//       ：   ，     1,      0
162     return S->link == NULL;//  S->link == NULL  
163 }
164 int StackSize(LinkSize& S)
165 {//     ：       
166     LinkNode *p = S->link;
167     int k=0;
168     while(p != NULL)//      
169     {
170         p = p->link;
171         k++;
172     }
173     return k;
174 }