首页 > 代码库 > 数据结构：顺序栈
数据结构：顺序栈
这是严蔚敏吴伟民版本的算法，感觉没《大话数据结构》里面的简单易懂
这个版本里面的top指针指向下一个空单元格，这个其实是有些问题的，因为栈满的时候，top是指向栈外的，有些不安全。
1 #ifndef SQ_STACK_HEAD 2 #define SQ_STACK_HEAD 3 #include <stdio.h> 4 #include <stdlib.h> 5 #define Status int 6 #define OVERFLOW -1 7 #define OK 0 8 #define ERROR 1 9 #define MAX_SIZE 100 //初始容量10 #define STEP_SIZE 5 //容量增长步长11 typedef int ElemType;12 13 typedef struct{14 ElemType *base; //栈底，这个是不变的15 ElemType *top; //栈顶，指向下一个空单元，所以取栈顶元素要用*(top-1)16 int size; //当前栈容量上限17 } SqStack;18 19 /* 栈初始化20 * 1.申请栈区21 * 2.top和base指针同时指向第一个单元22 */23 Status init(SqStack *s)24 {25 s->size = MAX_SIZE;26 s->base = (ElemType *)malloc(MAX_SIZE * sizeof(ElemType));27 if (s->base == NULL) return OVERFLOW; //分配失败28 s->top = s->base; //s->top指向下一个新单元29 return OK;30 }31 32 /*33 * 销毁栈34 * 1.释放栈区域35 * 2.base和top指针置空36 */37 Status destroy(SqStack *s)38 {39 if (s->base == NULL) {40 s->top = NULL;41 return ERROR;42 }43 free(s->base);44 s->top = s->base = NULL;45 s->size = 0;46 return OK;47 }48 49 /* 入栈50 * 1.如果栈已满，则realloc()51 * 2.将新元素写入top指向的单元52 * 3.top向上移动一格53 */54 Status push(SqStack *s, ElemType e)55 {56 ElemType *new_base;57 if (s->top - s->base >= s->size) {//如果栈已满，注意测试边界值58 /* 注意一下这里，之所以要多用一个new_base，是因为如果写成：59 * s->base = realloc(s->base, new_size)60 * 此时如果realloc()失败则s->base之前指向的地址会丢失而不可控61 */62 new_base = (ElemType *)realloc(s->base, (s->size + STEP_SIZE) * sizeof(ElemType));63 if (new_base == NULL) {64 return OVERFLOW;65 }66 s->base = new_base;67 s->top = s->base + s->size;68 s->size += STEP_SIZE;69 new_base = NULL;70 }71 *s->top++ = e;//由于s->top指向的是空单元，所以直接将e写入，然后s->top移动一格72 return OK;73 }74 75 /*76 * 出栈77 * 1.top向下退一格78 * 2.取top指向的值79 */80 Status pop(SqStack *s, ElemType *e)81 {82 if (s->top == s->base) return ERROR;//空栈或者已经被销毁83 *e = *--s->top;//s->top指向的是空单元，所以要先移动s->top才能取值84 return OK;85 }86 87 /* 取栈顶值:取top下一格的值 */88 Status getTop(SqStack s, ElemType *e)89 {90 if (s.top == s.base) return ERROR;91 *e = *(s.top - 1);//s->top指向的是空单元，所以s->top下一格才是栈顶元素92 return OK;93 }94 95 #endif
优化后的算法：
1 #ifndef SQ_STACK_HEAD 2 #define SQ_STACK_HEAD 3 #include <stdio.h> 4 #include <stdlib.h> 5 #define Status int 6 #define OVERFLOW -1 7 #define OK 0 8 #define ERROR 1 9 #define MAX_SIZE 10 //初始容量10 #define STEP_SIZE 5 //容量增长步长11 typedef int ElemType;12 13 typedef struct{14 ElemType *base; //栈底，这个是不变的15 ElemType *top; //栈顶，指向最后一个单元格16 int size; //当前栈容量上限17 } SqStack;18 19 /* 栈初始化20 * 1.申请栈区21 * 2.top置空22 */23 Status init(SqStack *s)24 {25 s->size = MAX_SIZE;26 s->base = (ElemType *)malloc(MAX_SIZE * sizeof(ElemType));27 if (s->base == NULL) return OVERFLOW; //分配失败28 s->top = NULL;29 return OK;30 }31 32 /*33 * 销毁栈34 * 1.释放栈区域35 * 2.base和top指针置空36 */37 Status destroy(SqStack *s)38 {39 s->top = NULL;40 if (s->base == NULL) {41 return ERROR;42 }43 free(s->base);44 s->base = NULL;45 s->size = 0;46 return OK;47 }48 49 /* 入栈50 * 1.如果栈已满，则realloc()51 * 2.top向上移动一格52 * 3.将新元素写入top指向的单元53 */54 Status push(SqStack *s, ElemType e)55 {56 ElemType *new_base;57 if (s->top - s->base >= s->size - 1) {//如果栈已满，注意测试边界值58 new_base = (ElemType *)realloc(s->base, (s->size + STEP_SIZE) * sizeof(ElemType));59 if (new_base == NULL) {60 return OVERFLOW;61 }62 s->base = new_base;63 s->top = s->base + (s->size - 1);64 s->size += STEP_SIZE;65 new_base = NULL;66 }67 if (s->top == NULL)68 s->top = s->base;69 else70 s->top++;71 *s->top = e;72 return OK;73 }74 75 /*76 * 出栈77 * 1.取top指向的值78 * 2.top向下退一格79 */80 Status pop(SqStack *s, ElemType *e)81 {82 if (s->top == NULL) return ERROR;//空栈或者已经被销毁83 *e = *s->top--;84 return OK;85 }86 87 /* 取栈顶值:取top下一格的值 */88 Status getTop(SqStack s, ElemType *e)89 {90 if (s.top == s.base) return ERROR;91 *e = *s.top;//s->top指向的是空单元，所以s->top下一格才是栈顶元素92 return OK;93 }94 #endif
《大话数据结构》中的算法，简单易懂，就是把栈当数组用
1 #ifndef SQ_STACK_HEAD 2 #define SQ_STACK_HEAD 3 #include <stdio.h> 4 #include <stdlib.h> 5 #define Status int 6 #define OVERFLOW -1 7 #define OK 0 8 #define ERROR 1 9 #define STACK_INIT_SIZE 100 //初始容量10 #define STEP_SIZE 5 //容量增长步长11 typedef int ElemType;12 13 /*14 * 注意跟上面算法的区别15 * 主要是top指针不一样16 * 这个版本更简单易懂17 */18 typedef struct{19 ElemType *data; //栈底，这个是不变的20 int top; //栈顶，指向最后一个元素21 int size; //当前栈容量上限22 } SqStack;23 24 /* 栈初始化25 * 1.申请栈区,data当成数组使用26 * 2.top=-1，现在栈空所以只能指向-127 */28 Status init(SqStack *s)29 {30 s->size = STACK_INIT_SIZE;31 s->data = http://www.mamicode.com/(ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));32 if (s->data =http://www.mamicode.com/= NULL) return OVERFLOW; //分配失败33 s->top = -1;34 return OK;35 }36 37 /*38 * 销毁栈39 * 1.释放栈区域40 * 2.data指针置空, top置为-141 */42 Status destroy(SqStack *s)43 {44 s->top = -1;45 if (s->data =http://www.mamicode.com/= NULL) return ERROR;46 free(s->data);47 s->data =http://www.mamicode.com/ NULL;48 s->size = 0;49 return OK;50 }51 52 /* 入栈53 * 1.如果栈已满，则realloc()54 * 2.top上移55 * 3.将新元素写入top指向的单元56 */57 Status push(SqStack *s, ElemType e)58 {59 ElemType *new_data;60 if (s->top == s->size - 1) {//如果栈已满，注意测试边界值61 new_data = http://www.mamicode.com/(ElemType *)realloc(s->data, (s->size + STEP_SIZE) * sizeof(ElemType));62 if (new_data =http://www.mamicode.com/= NULL) {63 return OVERFLOW;64 }65 s->data =http://www.mamicode.com/ new_data;66 s->size += STEP_SIZE;67 new_data =http://www.mamicode.com/ NULL;68 }69 s->data[++s->top] = e;//top先移动到下一个空单元，然后再将e写入70 return OK;71 }72 73 /*74 * 出栈75 * 1.取top指向的值76 * 2.top后退一格77 */78 Status pop(SqStack *s, ElemType *e)79 {80 if (s->top == -1) return ERROR;//空栈或者已经被销毁81 *e = s->data[s->top--];82 return OK;83 }84 85 /* 取栈顶值:top指向的值 */86 Status getTop(SqStack s, ElemType *e)87 {88 if (s.top == -1) return ERROR;89 *e = s.data[s.top];90 return OK;91 }92 93 #endif
数据结构：顺序栈
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。