纪念逝去的岁月——C++实现一个栈（使用类模板）

  1 #include <stdio.h>
  2 #include <string.h>
  3 
  4 //#define USEDEBUG
  5 
  6 #ifdef USEDEBUG
  7 #define DEBUG(fmt, arg...)  8     do{  9         printf("%s %d %s() : ", __FILE__, __LINE__, __func__); 10         printf(fmt, ##arg); 11     }while(0)
 12 #else
 13 #define DEBUG(fmt, arg...)
 14 #endif
 15 
 16 template<typename T> class ClsStack
 17 {
 18     private :
 19         T **    __m_Data;
 20         int     __m_pos;
 21         size_t  __m_memsize;
 22 
 23     protected :
 24         int     __resize(size_t n);
 25         size_t  __doublesize(size_t n);
 26 
 27     public :
 28         ClsStack(size_t n = 0);
 29         ~ClsStack();
 30 
 31         int  pop (T ** ppData);
 32         int  top (T ** ppData);
 33         int  push(T * pData);
 34         void clear();
 35 
 36         void printStack(T * p[], size_t pos);
 37 };
 38 
 39 template<typename T> ClsStack<T>::ClsStack(size_t n)
 40 {
 41     __m_Data = NULL;
 42     __m_pos = -1;
 43     __m_memsize = 0;
 44 
 45     if(0 != n)
 46     {
 47         __m_Data = new T * [n];
 48         if(NULL != __m_Data)
 49         {
 50             __m_memsize = n;
 51         }
 52     }
 53 }
 54 
 55 template<typename T> ClsStack<T>::~ClsStack()
 56 {
 57     if(NULL != __m_Data)
 58     {
 59         delete __m_Data;
 60         __m_Data = NULL;
 61     }
 62     __m_pos = -1;
 63     __m_memsize = 0;
 64 }
 65 
 66 template<typename T> size_t ClsStack<T>::__doublesize(size_t n)
 67 {
 68     size_t x = 0;
 69     if(0 == n)
 70     {
 71         x = 1;
 72     }
 73     else
 74     {
 75         x = n * 2;
 76     }
 77 
 78     return x;
 79 }
 80 
 81 template<typename T> int ClsStack<T>::__resize(size_t n)
 82 {
 83     T ** p = new T * [n];
 84     if(NULL == p)
 85     {
 86         return -1;
 87     }
 88     memset(p, 0, sizeof(T *) * (n));
 89     if(NULL != __m_Data)
 90     {
 91         //printStack(__m_Data, __m_pos);
 92         if( NULL == memcpy(p, __m_Data, __m_memsize * sizeof(T *)))
 93         {
 94             DEBUG("memcpy faild\n");
 95             delete p;
 96             return -1;
 97         }
 98         //printStack(p, __m_pos);
 99         delete __m_Data;
100     }
101     __m_Data = p;
102     __m_memsize = n;
103 
104     return 0;
105 }
106 
107 template<typename T> int ClsStack<T>::pop(T ** ppData)
108 {
109     if(NULL == ppData)
110     {
111         return -1;
112     }
113     int r = 0;
114     if(-1 == __m_pos)
115     {
116         *ppData = NULL;
117         r = -1;
118     }
119     else
120     {
121         *ppData = __m_Data[__m_pos --];
122         r = 0;
123         DEBUG("memsize : [%u], pos : [%d], p = [0X%08X]\n", __m_memsize, __m_pos + 1, (unsigned int)*ppData);
124     }
125 
126     return r;
127 }
128 
129 template<typename T> int ClsStack<T>::top(T ** ppData)
130 {
131     if(NULL == ppData)
132     {
133         return -1;
134     }
135     int r = 0;
136     if(-1 == __m_pos)
137     {
138         *ppData = NULL;
139         r = -1;
140     }
141     else
142     {
143         *ppData = __m_Data[__m_pos];
144         r = 0;
145     }
146 
147     return r;
148 }
149 
150 template<typename T> int ClsStack<T>::push(T * pData)
151 {
152     if(__m_pos + 1 >= __m_memsize)
153     {
154         size_t n = __doublesize(__m_memsize);
155         if(0 != __resize(n))
156         {
157             return -1;
158         }
159     }
160     __m_Data[++__m_pos] = pData;
161     DEBUG("memsize : [%u], pos : [%d], p = [0X%08X]\n", __m_memsize, __m_pos, (unsigned int)__m_Data[__m_pos]);
162 
163     return 0;
164 }
165 
166 template<typename T> void ClsStack<T>::clear()
167 {
168     if(NULL != __m_Data && 0 != __m_memsize)
169     {
170         delete __m_Data;
171     }
172     __m_Data = NULL;
173     __m_pos = -1;
174     __m_memsize = 0;
175 }
176 
177 template<typename T> void ClsStack<T>::printStack(T * p[], size_t pos)
178 {
179     int i = 0;
180     for(i = 0; i <= pos; i++)
181     {
182         printf("[%08u] = [0X%08X]\n", i, NULL == p ? 0 : p[i]);
183     }
184     printf("----------------------------\n");
185 }
186 
187 #define TEST_EQ(a, b)188     do{189         if(a == b)190         {191             printf("\033[0;32m[SUCCESS %5d]\033[0m\n", __LINE__);192         }193         else194         {195             printf("\033[0;31m[FAILD   %5d]\033[0m\n", __LINE__);196         }197     }while(0)
198 
199 int main()
200 {
201     ClsStack<int> objStack;
202     int x = 10;
203     int * p = &x;
204     objStack.push(p);
205     int i = 0;
206     for(i = 0; i <= 10; i++)
207     {
208         int * z = new int;
209         *z = i;
210         objStack.push(z);
211     }
212     for(i = 10; i >= 0; i--)
213     {
214         int * z = NULL;
215         int r = objStack.pop(&z);
216         if(NULL == z)
217         {
218             printf("z == NULL\n");
219             continue;
220         }
221         TEST_EQ(i, *z);
222         delete z;
223     }
224     int * g = NULL;
225     int r = objStack.pop(&g);
226     TEST_EQ(x, *g);
227 }

g++ -g    -c -o stack.o stack.cpp
g++ -g -o stack stack.o

$ ./stack 
[SUCCESS   221]
[SUCCESS   221]
[SUCCESS   221]
[SUCCESS   221]
[SUCCESS   221]
[SUCCESS   221]
[SUCCESS   221]
[SUCCESS   221]
[SUCCESS   221]
[SUCCESS   221]
[SUCCESS   221]
[SUCCESS   226]