1、代码
1.1 调试信息的配置
//一个调试开关,如果要看调试信息,就把这个开关的注释去掉 //#define USEDEBUG //如果调试开关打开了,就定义好调试的输出函数(其实是个宏), #ifdef USEDEBUG #define DEBUG(fmt, arg...)\ do{\ printf("%s %d %s() : ", __FILE__, __LINE__, __func__);\ printf(fmt, ##arg);\ }while(0) #else //如果没有打开,这个函数什么也不做 #define DEBUG(fmt, arg...) #endif
1.2 栈类的声明
//定义模版类 ClsStack template<typename T> class ClsStack { //这个类的=型私有数据,主要用于对栈的内存分配进行管理, //用户不需要关心内存,只需要调用对外提供的几个方法就可以了 private : T ** __m_Data;//存储数据的内存开始地址 int __m_pos;//记录栈尾的位置,插入数据时插入这个位置 int __m_memsize;//记录内存的总数 protected : //重新分配内存空间,可以减小,也可以增大 int __resize(int n); //获取给定参数的双倍内存,其实主要目的是防止参数是0 int __doublesize(int n); public : ClsStack(int n = 0); ~ClsStack(); //弹出栈顶 int pop (T ** ppData); //获取栈顶元素,但是不弹出 int top (T ** ppData); //向栈添加数据 int push(T * pData); //清空整个栈的数据 int clear(void (*)(T*)); //输出整个栈的数据,用于调试 void printStack(T * p[], int pos); };
1.3 构造函数的实现
//构造函数 //默认参数值是0 //参数非零时的作用是用于初始化栈空间的大小 template<typename T> ClsStack<T>::ClsStack(int n) { __m_Data = NULL; __m_pos = -1; __m_memsize = 0; if(0 != n) { __m_Data = new T * [n]; if(NULL != __m_Data) { __m_memsize = n; } } }
1.4) 析构函数的实现
//析构函数 //在栈对象被销毁时,需要把申请的内存空间释放 template<typename T> ClsStack<T>::~ClsStack() { if(NULL != __m_Data) { delete __m_Data; __m_Data = NULL; } __m_pos = -1; __m_memsize = 0; }
1.5)内存控制函数
//计算新的内存空间 //当参数是0的时候,指定内存空间是1 //参数不是0的时候,内存加倍 template<typename T> int ClsStack<T>::__doublesize(int n) { int x = 0; if(0 == n) { x = 1; } else { x = n * 2; } return x; } //重新设定栈的大小 //就是扩展当前的内存容量到指定的大小 template<typename T> int ClsStack<T>::__resize(int n) { T ** p = new T * [n]; if(NULL == p) { return -1; } memset(p, 0, sizeof(T *) * (n)); if(NULL != __m_Data) { //printStack(__m_Data, __m_pos); if( NULL == memcpy(p, __m_Data, __m_memsize * sizeof(T *))) { DEBUG("memcpy faild\n"); delete p; return -1; } //printStack(p, __m_pos); delete __m_Data; } __m_Data = p; __m_memsize = n; return 0; }
1.6)栈操作函数的实现
//弹出数据 //数据通过参数指定的指针返回 template<typename T> int ClsStack<T>::pop(T ** ppData) { if(NULL == ppData) { return -1; } int r = 0; if(-1 == __m_pos) { *ppData = NULL; r = -1; } else { *ppData = __m_Data[__m_pos --]; r = 0; DEBUG("memsize : [%u], pos : [%d], p = [0X%08X]\n", __m_memsize, __m_pos + 1, (unsigned int)*ppData); } return r; } //获取栈顶元素,并不弹出 template<typename T> int ClsStack<T>::top(T ** ppData) { if(NULL == ppData) { return -1; } int r = 0; if(-1 == __m_pos) { *ppData = NULL; r = -1; } else { *ppData = __m_Data[__m_pos]; r = 0; } return r; } //向栈压入元素 //栈会自己判断内存,如果内存不足会自动增加内存 template<typename T> int ClsStack<T>::push(T * pData) { if(__m_pos + 1 >= __m_memsize) { int n = __doublesize(__m_memsize); if(0 != __resize(n)) { return -1; } } __m_Data[++__m_pos] = pData; DEBUG("memsize : [%u], pos : [%d], p = [0X%08X]\n", __m_memsize, __m_pos, (unsigned int)__m_Data[__m_pos]); return 0; }
1.7)清空栈数据函数
//清空栈,需要指定回收元素数据的函数, //否则无法知道如何回收由用户申请的内存空间 template<typename T> int ClsStack<T>::clear(void (*F)(T *)) { if(NULL == F && __m_pos >= 0) { return -1; } if(NULL != __m_Data && 0 != __m_memsize) { for(int i = 0; i <= __m_pos; i++) { F(__m_Data[i]); __m_Data[i] = NULL; } delete __m_Data; } __m_Data = NULL; __m_pos = -1; __m_memsize = 0; }
1.8)调试辅助函数
//输出栈的内存状态,调试时使用 template<typename T> void ClsStack<T>::printStack(T * p[], int pos) { int i = 0; for(i = 0; i <= pos; i++) { printf("[%08u] = [0X%08X]\n", i, NULL == p ? 0 : p[i]); } printf("----------------------------\n"); }
1.9)测试代码
//test 函数定义 #define TEST_EQ(a, b)\ do{\ if(a == b)\ {\ printf("\033[0;32m[SUCCESS %5d]\033[0m\n", __LINE__);\ }\ else\ {\ printf("\033[0;31m[FAILD %5d]\033[0m\n", __LINE__);\ }\ }while(0) int main() { ClsStack<int> objStack; int x = 10; int * p = &x; //向栈内压入数据 objStack.push(p); int i = 0; for(i = 0; i <= 10; i++) { int * z = new int; *z = i; objStack.push(z); } //开始弹出数据 for(i = 10; i >= 0; i--) { int * z = NULL; objStack.pop(&z); if(NULL == z) { printf("z == NULL\n"); continue; } //测试弹出的数据和压入的数据是否一致 TEST_EQ(i, *z); delete z; } int * g = NULL; objStack.pop(&g); TEST_EQ(x, *g); }
完整代码如下(折叠了) :
View Code
2、运行结果
2.1、编译
g++ -g -c -o stack.o stack.cpp -Wall -I./
g++ -g -o stack stack.o -Wall -I./
2.2、运行结果
$ ./stack [SUCCESS 288] [SUCCESS 288] [SUCCESS 288] [SUCCESS 288] [SUCCESS 288] [SUCCESS 288] [SUCCESS 288] [SUCCESS 288] [SUCCESS 288] [SUCCESS 288] [SUCCESS 288] [SUCCESS 293]
本文转自郝峰波博客园博客,原文链接:http://www.cnblogs.com/fengbohello/p/4547598.html,如需转载请自行联系原作者