堆栈相关知识

在数据结构中，栈是一种重要的线性结构。从广义上来看，栈也是线性表，其特殊性在于栈的基本操作是线性表操作的子集，是操作受限的线性表。栈的相关知识如下所示，也将一些基本操作实现出来了。
  1 /**
  2 堆栈  栈顶top 栈底base  后进先出LIFO结构
  3 两种存储方式：线性存储结构和链式存储结构
  4 
  5 */
  6 #include<stdio.h>
  7 #include<stdlib.h>
  8 
  9 //***********************栈的顺序存储结构说明*****************************
 10 #define STACK_INIT_SIZE 100 //存储空间初始容量
 11 #define STACKINCREMENT 10   //存储空间分配增量
 12 typedef struct
 13 {
 14     int *base;        //栈底指针，在栈构造之前和栈销毁之后，base的值为NULL
 15     int *top;         //栈顶指针
 16     int stacksize;    //当前已经分配的大小，以元素为单位,不是当前栈中已有元素的个数
 17 }SqStack;
 18 
 19 //***********************栈的基本操作函数说明及实现************************
 20 void InitStack(SqStack &S)
 21 {
 22     //构造一个空栈
 23     S.base = (int *)malloc(STACK_INIT_SIZE * sizeof(int));
 24     if(!S.base)
 25     {   //存储分配失败
 26         printf("空栈初始化失败，任意键退出！
");
 27         getchar();
 28         exit(1);
 29     }
 30     S.top = S.base;
 31     S.stacksize = STACK_INIT_SIZE;
 32 }
 33 //***************************************************************************
 34 void PrintStack(SqStack S)
 35 {
 36     //输出栈中的元素
 37     if (S.base ==S.top)
 38     {
 39         printf("该栈目前为空，无需删除，任意键退出！
");
 40         getchar();
 41         exit(1);
 42     }
 43     //从栈顶依次向下输出栈中元素
 44     while(S.top !=S.base)
 45     {
 46         printf("%d ",*(S.top-1));
 47         S.top--;
 48     }
 49     printf("
");
 50 }
 51 //***************************************************************************
 52 int GetTop(SqStack S)
 53 {
 54     //若栈不空，返回栈顶元素，否则，错误提示
 55     if (S.base == S.top)
 56     {    //空栈，返回
 57         printf("空栈，返回！任意键退出
" );
 58         getchar();
 59         exit(1);
 60     }
 61     //非空栈中的栈顶指针始终指向栈顶元素的下一个位置
 62     return *(S.top - 1);
 63 }
 64 //***************************************************************************
 65 void Push(SqStack &S,int e)
 66 {
 67     //插入元素e为新的栈顶元素
 68     if (S.top - S.base >=S.stacksize)
 69     {    //栈满，追加存储空间
 70         S.base = (int *)realloc(S.base,(S.stacksize + STACKINCREMENT)*sizeof(int));
 71         if (!S.base)
 72         {
 73             printf("追加存储空间失败！任意键退出
");
 74             getchar();
 75             exit(1);
 76         }
 77         S.top = S.base + S.stacksize;
 78         S.stacksize += STACKINCREMENT;
 79     }
 80 
 81     *S.top++ = e;
 82 }
 83 //**************************************************************************
 84 void Pop(SqStack &S)
 85 {
 86     //若栈不空，删除栈顶元素，否则，返回错误
 87     if (S.base == S.top)
 88     {
 89         printf("该栈目前为空，无需删除，任意键退出！
");
 90         getchar();
 91         exit(1);
 92     }
 93 
 94     --S.top;
 95 }
 96 
 97 //*************************************************************************
 98 int main()
 99 {
100     SqStack S;
101     int count;//初始化栈中的元素个数
102     int value;
103     //初始化一个空栈
104     InitStack(S);
105     //向栈中压入数据
106     printf("请输入栈中初始化元素个数：");
107     scanf("%d",&count);
108     for (int i = 0; i < count; ++i)
109     {
110         scanf("%d",&value);
111         Push(S,value);
112     }
113     //输出栈中的数据元素
114     printf("当前栈中的元素为：");
115     PrintStack(S);
116     //测试取栈顶数据
117     printf("栈顶数据为：");
118     printf("%d
",GetTop(S));
119     //测试删除栈数据
120     Pop(S);
121     printf("删除栈顶元素之后的数据为：");
122     PrintStack(S);
123     return 0;
124 }