堆栈的操作

栈是一种线性的数据结构，它的操作限定在了栈顶，即只能够在栈顶进行数据的插入，删除以及其它各种操作；栈的操作特性为先进后出，下面给出

一张图来说明一下栈的入栈操作。

通过这个图，发现入栈都是在栈顶进行的，top等于base表示此栈为空栈。上面的入栈顺序为A、B、C、D，在出栈的时候由于只能在栈顶操作，因此

在出栈的时候，顺序就反过来了；所以栈的操作特性就是先进后出。

另外，栈分为顺序栈和链栈，在这里呢，我是用顺序栈来实现的，个人认为顺栈的实现更简洁方便。另外虽然c++STL标准库里封装了栈结构，并且使用起来

也很方便，但是还是很有必要了解一下它的实现原理的。下面代码详细的写了栈的常见操作，并且测试过了。

  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 #include<malloc.h>
  4 #define MAXSIZE 100
  5 typedef struct
  6 {
  7     int  *top;    //始终指向栈顶的空位置        
  8     int  *base;   //栈底
  9     int  stacksize;  //当前栈的大小
 10 }sqstack;
 11 
 12 int Initstack(sqstack *s)
 13 {
 14     s->base=(int *)malloc(sizeof(int)*MAXSIZE); //为堆栈开辟空间
 15     if(!s->base)    
 16     {
 17        printf("存储分配失败");
 18        exit(-1);
 19     }
 20    s->top=s->base; //空栈的话top和base指向同一位置
 21    s->stacksize= MAXSIZE;
 22    return  1;
 23 }
 24 int push(sqstack *s,int e)   //入栈
 25 {  
 26       if(s->top-s->base==MAXSIZE)
 27       {
 28              printf("堆栈已满，无法入栈
");
 29              exit(-1);
 30       }
 31       *s->top=e;
 32       s->top++;   //入栈后栈顶指针top指向下一个空位置
 33       //*(s->top)++=e;
 34       return  1;
 35 }
 36 int pop(sqstack *s,int *e)  //出栈
 37 {  
 38       if(s->top==s->base)
 39       {
 40           printf("栈是空的，无法出栈");
 41           return 0;
 42       }
 43       s->top--;  //因为top指向栈顶的下一个位置，是空的，所以要通过自减来指向栈顶元素
 44       *e=*s->top;
 45       return 1;
 46 }
 47 void printstack(sqstack s)  //由于是打印堆栈，不需要修改原来堆栈的值，所以形参设为普通变量就行，不需要设成指针
 48 {         
 49         int *p=s.top;
 50         while(p>s.base)
 51         {
 52          p--;
 53          printf("%d ",*p);  
 54         }   
 55         printf("
");
 56 }
 57 int Gettop(sqstack s,int *e)  //获取栈顶元素,不需要修改原来堆栈的值,所以形参设为普通变量就行,不需要设成指针
 58 {
 59          if(s.top==s.base)    
 60              return  0;
 61          s.top--;
 62          *e=*s.top;
 63          return   1;
 64 }
 65 int stacklength(sqstack s) //获取栈的长度
 66 {
 67     if(s.top==s.base)
 68         return 0;
 69     else
 70         return(s.top-s.base);
 71 } 
 72 int isempty(sqstack s)  //判断堆栈是否为空
 73 {
 74     if(s.top==s.base)  //空栈返回1，非空返回0
 75         return 1;
 76     else
 77         return 0;
 78 }
 79 void clear(sqstack *s)  //清空堆栈
 80 {
 81     s->top=s->base;
 82 }
 83 int main()
 84 {
 85       int e;
 86       char ch;
 87       sqstack  s;
 88       Initstack(&s);  ///初始化堆栈
 89       printf("输入栈中的元素：
");
 90       do{
 91            scanf("%d",&e);
 92            push(&s,e);
 93       }while((ch=getchar())!='
');
 94 
 95       printf("栈中元素为：
");
 96       printstack(s);
 97       printf("栈的长度为：%d
", stacklength(s));
 98       Gettop(s,&e);
 99       printf("栈顶元素为：%d
",e);
100       for(int i=1;i<=5;i++)
101       {
102           pop(&s,&e);
103           printf("第%d次出栈的元素为：%d
",i,e);     
104       }
105       printf("弹栈后栈中剩余元素为：");
106       printstack(s);
107       printf("弹栈后栈的长度为：%d
", stacklength(s));
108       Gettop(s,&e);
109       printf("弹栈后栈顶元素为：%d
",e);
110       printf("结果为1表示空栈，结果为0表示非空栈：%d
",isempty(s));
111       clear(&s);
112       printf("清空后栈的长度为：%d
", stacklength(s));
113       printf("结果为1表示空栈，结果为0表示非空栈：%d
",isempty(s));
114       return 0;
115 }

结果如下：

注意，由于栈是先进后出的，所以栈中数据的顺序和输入的数据顺序是相反的。

2020-04-29 17:10:06