顺序栈的基本操作，C语言

　　由于现在只学了C语言所以就写这个C语言版的栈的基本操作

这里说一下 ：网上和书上都有这种写法 int InitStack(SqStack &p)

&p是取地址 但是这种用法好像C并不支持 ，C++才支持，所以用

C语言写就需要使用指针

代码如下：

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #define STACK_INIT_SIZE 100//储存空间初始分配量
  4 #define STACKINCREMENT  10//存储空间分配增量
  5 #define OK 1
  6 #define ERROR 0
  7 typedef int StackType; //栈元素类型
  8  
  9 typedef struct {
 10     StackType *base;   //在构造之前和销毁之后，base的值为NULL
 11     StackType *top;    //栈顶指针
 12     int stacksize;     //当前已分配的存储空间，以元素为单位
 13 }SqStack; //顺序栈
 14 
 15 //栈的初始化
 16 int InitStack(SqStack *p) {
 17     
 18     
 19     p->base = (StackType*)malloc(STACK_INIT_SIZE * sizeof(StackType));
 20     if (p->base == NULL)  return ERROR;  //内存分配失败
 21     p->top = p->base;     //栈顶与栈底相同表示一个空栈
 22     p->stacksize = STACK_INIT_SIZE;
 23     return OK;
 24 
 25 }
 26 //判断栈是否为空
 27 int EmptyStack(SqStack *p) {
 28     //若为空栈 则返回OK，否则返回ERROR
 29     if (p->top == p->base) return OK;
 30     else return ERROR;
 31 }
 32 //顺序栈的压入
 33 int Push(SqStack *p,StackType e) {
 34     //插入元素e为新的栈顶元素
 35     if ((p->top - p->base)>= p->stacksize)   //栈满，追加储存空间
 36     {
 37         p->base = (StackType*)realloc(p->base, (p->stacksize + STACKINCREMENT) * sizeof(StackType));
 38         if (p->base == NULL)   return ERROR;// 储存空间分配失败
 39         p->top = p->base + p->stacksize;    //可能有人觉得这句有点多余(我当时也是这么想的 后面有解释)
 40         p->stacksize += STACKINCREMENT;
 41     }
 42     *(p->top) = e;
 43     (p->top)++;
 44     return OK;
 45 }
 46  // 顺序栈的弹出     
 47 int Pop(SqStack *p,StackType *e) {
 48     //若栈不空，则删除p的栈顶元素，用e返回其值
 49     if (p->top == p->base) return ERROR;
 50     --(p->top);
 51     *e = *(p->top);
 52     return OK;
 53     
 54 
 55 }
 56 //顺序栈的销毁
 57 int DestroyStack(SqStack *p) {
 58     //释放栈底空间并置空
 59         free(p->base);
 60         p->base = NULL;
 61         p->top = NULL;
 62         p->stacksize = 0;
 63         
 64         return OK;
 65 }
 66 //将顺序栈置空 栈还是存在的，栈中的元素也存在，如果有栈中元素的地址任然能调用
 67 int ClearStack(SqStack *p) {
 68     p->top= p->base;
 69     return OK;
 70 }
 71 //返回顺序栈的元素个数
 72 int StackLength(SqStack p) {
 73     //栈顶指针减去栈底指针等于长度，因为栈顶指针指向当前栈顶元素的下一个位置
 74     return p.top - p.base;
 75 }
 76 //返回顺序栈的栈顶元素
 77 int GetTop(SqStack *p, StackType *e) {
 78     //若栈不为空，则用e返回p的栈顶元素
 79     if (p->top > p->base) {
 80         *e = *(p->top - 1); return OK;
 81     }
 82     else return ERROR;
 83 }
 84 //从栈顶到栈底对每个元素调用某个函数
 85 int StackTraverse(SqStack p,void (*pfun)(StackType)/*函数指针*/){
 86 //从栈底到栈顶依次对栈中的每个元素调用函数pfun()
 87     while (p.top > p.base)
 88     pfun(*(p.base)++);                //先调用后递增
 89     printf("\n");
 90     return OK;
 91 }
 92 //打印栈中元素
 93 void print(StackType stack) {
 94     printf("%d\n", stack);
 95     
 96 }
 97 //测试栈的各种操作
 98 int main() {
 99     int n,i;
100     StackType *e,a;
101     SqStack *pstack,stack;
102     pstack = &stack;
103     e=(StackType*)malloc(sizeof(StackType));    //为指针e分配内存地址
104     InitStack(pstack);                            //初始化栈
105 
106     if (EmptyStack(pstack) == 1) printf("-------栈为空-------\n");
107     printf("请输入栈的元素个数:");
108     scanf("%d", &n);
109     for (i = 0; i < n; i++)
110     {
111         scanf("%d", &a);
112         Push(pstack, a);
113     }
114     if (EmptyStack(pstack) == 0) printf("-------栈不为空-----\n");
115         
116     printf("栈的长度为:%d\n", StackLength(stack));
117     printf("--------------------\n");
118     printf("请输入一个入栈元素:");
119     scanf("%d", &a);
120     Push(pstack, a);
121     printf("--------------------\n");
122     printf("栈中的元素个数为:%d\n", StackLength(stack));
123     printf("--------------------\n");
124     GetTop(pstack, e);
125     printf("栈顶元素为:%d\n", *e);
126     printf("--------------------\n");
127     printf("打印栈中的元素:\n");
128     StackTraverse(stack, print);
129     printf("---弹出栈顶元素---\n");
130     Pop(pstack, e);
131     printf("弹出的栈顶元素为:%d\n", *e);
132     printf("--------------------\n");
133     GetTop(pstack, e);
134     printf("栈顶元素为:%d\n", *e);
135     printf("--------------------\n");
136     printf("打印栈中的元素:\n");
137     StackTraverse(stack, print);
138     printf("--------------------\n");
139 
140     printf("----------清空栈-------\n");
141     if (ClearStack(pstack) == 0)  printf("已清空栈\n");
142     
143     printf("----------销毁栈-------\n");
144     if (DestroyStack(pstack) == 0)  printf("已销毁栈\n");
145     return 0;
146    
147 }

第39行 p->top = p->base + p->stacksize;这句有必要加上吗? 答案是肯定的。

这一个问题的关键在于 realloc 是怎么实现的，有两种情况：

　　 如果有足够空间用于扩大mem_address指向的内存块，则分配额外内存，并返回mem_address。

这里说的是“扩大”，我们知道，realloc是从堆上分配内存的，当扩大一块内存空间时，

realloc()试图直接从堆上现存的数据后面的那些字节中获得附加的字节，如果能够满足，自然天下太平。

也就是说，如果原先的内存大小后面还有足够的空闲空间用来分配，加上原来的空间大小= newsize。

那么就ok。得到的是一块连续的内存。

　　 如果原先的内存大小后面没有足够的空闲空间用来分配，那么从堆中另外找一块newsize大小的内存。

并把原来大小内存空间中的内容复制到newsize中。返回新的mem_address指针。（数据被移动了）。老块被放回堆上。

如果是第二种情况的话，s->top 就不是原来的 top 了 --百度百科

　　写这些代码的时候还是遇到了一些问题 在这里总结一下：

　　第一 对于指针的使用要慎重 因为它传递进函数会改变原始数据，所以对于不需要改变

指针指向的值的情况就不要使用指针。

　　第二 对于指针的使用 如下定义 int *e=NULL； *e=3;

看着好像没有问题 编译也没问题 但是运行程序就出错

为什么？ 没有为指针e分配内存地址 所以引用肯定错误啊（我这个逗逼错误-_-）

正确的用法应该是 int *e=NULL；e=(int*)malloc(sizeof(int)); *e=3;

我之前都是 int *e,a; e=&a; e=3; 这种用法 所以......