一、概念
1、栈的定义
栈 是仅限在 表尾 进行 插入 和 删除 的 线性表。
栈 又被称为 后进先出 （Last In First Out） 的线性表，简称 LIFO 。
2、栈顶
栈 是一个线性表，我们把允许 插入 和 删除 的一端称为 栈顶。
3、栈底
和 栈顶 相对，另一端称为 栈底，实际上，栈底的元素我们不需要关心。
二、接口
1、可写接口
1）数据入栈
栈的插入操作，叫做 入栈，也可称为 进栈、压栈。如下图所示，代表了三次入栈操作：
2）数据出栈
栈的删除操作，叫做 出栈，也可称为 弹栈。如下图所示，代表了两次出栈操作：
3）清空栈
一直 出栈，直到栈为空，如下图所示：
2、只读接口
1）获取栈顶数据
对于一个栈来说只能获取 栈顶 数据，一般不支持获取 其它数据。
2）获取栈元素个数
栈元素个数一般用一个额外变量存储，入栈 时加一，出栈 时减一。这样获取栈元素的时候就不需要遍历整个栈。通过 �(1)O(1) 的时间复杂度获取栈元素个数。
3）栈的判空
当栈元素个数为零时，就是一个空栈，空栈不允许 出栈 操作。
三、栈的基本运算
创建空栈 : CreateStack (len)
清空栈 : ClearStack (S)
判断是否栈空 : EmptyStack (S)
判断是否栈满 : FullStack (S)
元素进栈 : PushStack (S,x)
元素出栈 : PopStack (S)
取栈顶元素 : GetTop (S)
四、顺序栈（Sequential Stack）实现
1、数据结构定义
对于顺序表，在 C语言 中表现为 数组，在进行 栈的定义 之前，我们需要考虑以下几个点：
1）栈数据的存储方式，以及栈数据的数据类型；
2）栈的大小；
3）栈顶指针；
- 我们可以定义一个 栈 的 结构体，C语言实现如下所示：
typedef int datatype; typedef struct node{ /*定义栈中数据元素的数据类型*/ datatype *data; /*用指针指向栈的存储空间*/ int maxlen; /*当前栈的最大元素个数*/ int top; /*指示栈顶位置(数组下标)的变量*/ }sqstack; /*顺序栈类型定义*/
2、创建栈
C语言实现如下所示：
sqstack* stack_create(int len) { sqstack *s; if((s=(sqstack *)malloc(sizeof(sqstack)))==NULL) { puts("malloc failed"); return NULL; } if((s->data=(datatype *)malloc(len*sizeof(datatype)))==NULL) { puts("malloc failed"); return NULL; } s->maxlen=len; s->top=-1; return s; }
3、清空栈
C语言实现如下所示：
void stack_clear(sqstack* s) { s->top = -1; }
4、判断栈是否为空
C语言实现如下所示：
int stack_empty(sqstack* s) { return (s->top==-1 ? 1:0); }
5、判断栈是否饱和
C语言实现如下所示：
int stack_full(sqstack* s) { return (s->top==(s->maxlen-1) ? 1:0); }
6、入栈
C语言实现如下所示：
int stack_push(sqstack* s,datatype value) { if(s->top==s->maxlen-1){ puts("stack is full"); return -1; } s->data[s->top+1]=value; s->top++; return 1; }
数据结构——顺序栈与链式栈的实现-2
https://developer.aliyun.com/article/1507981
