栈

栈，是限定仅在表尾进行插入或删除操作的线性表。（栈就像一个杯子），，表头是栈底，表尾是栈顶。需要注意的是，栈是先进后出，后进先出。

同样，和线性表类似，栈也有两种储存表示方法（这里就用顺序栈的模块说明）

 1 #include <stdlib.h>
 2 #include <stdio.h>
 3 
 4 /****** 宏定义 ******/
 5 #define ERROR 0
 6 #define OVERFLOW -2
 7 #define OK 1
 8 #define STACK_INIT_SIZE 100    //存储空间初始分配量
 9 #define STACKINCREMENT 10    //存储空间分配增量
10 
11 /******** 取别名 *********/
12 typedef int SElemType;    //所需存的元素的类型
13 typedef int Status;
14 
15 /******** 栈的定义 *******/
16 typedef struct{
17     SElemType *base;    //栈的基地址，也就是栈底指针
18     SElemType *top;        //栈定指针
19     int stacksize;        //当前已分配的储存空间，就是最大能存储的数量
20 }SqStack;
21 
22 /********* 构建一个空栈 *******/
23 Status InitStack(SqStack &S){
24     S.base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));    //分配内存给S.base
25     if (!S.base) exit(OVERFLOW);    //存储分配失败
26     S.top = S.base;    //初始时，栈顶=栈底
27     S.stacksize = STACK_INIT_SIZE;    //当前最大存储量就是初始分配量
28     return OK;
29 }
30 
31 /********** 用e返回栈顶元素 ********/
32 Status GetTop(SqStack &S, SElemType &e){
33     if (S.top == S.base)
34         return ERROR;     //栈为空，ERROR
35     e = *(S.top - 1);    //栈顶指针的下一位就是栈顶元素
36     return OK;
37 }
38 
39 /********** 插入e为新的栈顶元素 ******/
40 Status Push(SqStack &S, SElemType e){
41     if (S.top - S.base >= S.stacksize){    //栈满，增加空间
42         S.base = (SElemType *)realloc(S.base, (S.stacksize + STACKINCREMENT)*sizeof(SElemType));
43         if (!S.base)
44             exit(OVERFLOW);
45         S.top = S.base + S.stacksize;    //栈顶指针的位置在栈底向上移 S.stacksize 个
46         S.stacksize += STACKINCREMENT;    //储存空间增大了  STACKINCREMENT 个
47     }
48     *S.top++ = e;    //栈顶指针的位置放值元素e, 然后上移一个
49     return OK;
50 }
51 
52 /********** 删除栈顶元素，并用e返回其值 ******/
53 Status Pop(SqStack &S, SElemType &e){
54     if (S.top == S.base)    //若为空
55         return ERROR;    
56     e = *--S.top;        //栈顶指针下移一个，并把值给e
57     return OK;
58 }
59 
60 int main(){
61     //略
62     return 0;
63 }