引言
数据结构中有
四大基础结构
，即
四大线性表
：顺序表、链表、**
栈
**、队列
被称为线性表是因为，数据用以上四种结构存储，在逻辑结构上都是
在一条线上相邻连续的
线性结构逻辑结构图示：顺序表
链表
**
栈
**
队列
前面已经介绍了前两个：
顺序表
和
链表
本篇文章就来介绍一下
栈
这种数据结构。
栈
什么是栈
前几篇文章介绍的
顺序表
和
链表
都属于比较自由的数据结构，没有限制存入数据应该从哪里存入
但是，
栈
就不一样了
栈
规定 只能从固定的一端
入数据(存放数据)
，
出数据(删除数据)
，并称这一端为
栈顶
。另一端称为
栈底
而
入数据(存放数据)
的操作，通常被称作：
压栈
出数据(删除数据)
的操作，通常被称为：
出栈
也就是说，
压栈
和
出栈
都是从
栈顶
进行操作的
数据结构中的
栈与 操作系统中的
栈，本质上是完全不同的，相同的 只有
名字及
创建销毁（出入数据）顺序操作系统中的
栈，如果调用函数，创建栈帧是从栈顶创建的，销毁栈帧也是从栈顶销毁的
详情可阅读博主本篇文章：【程序员的自我修养】[动态图文] 超详解函数栈帧
栈
存放数据的方式就像 砌砖，在
不破坏结构
的情况下只能这样 放 和 拿：
由图 可以看出
栈
是一种
后进先出(LIFO)
的数据结构，即 最后放入的数据，最先出来
基于这种
只能从栈顶存入删除数据，后进先出
的规则，
栈
结构的实现一般由
数组
来实现
当然也可以用
链表进行实现，不过 用单链表的话，想要效率只能
头插 头删， 不便于理解；更复杂的链表的话，会有多出的节点什么的也不方便。所以最好还是
用数组实现栈
以下 栈 也由 数组 实现
栈的结构
栈
指定了 只能从栈顶进行
压栈出栈
的操作。所以结构内，除数组之外，还需要记录栈顶位置的变量
所以
栈
结构一般为：
typedefint StackDataType;typedefstructStack{
StackDataType *data;int Top;//记录栈顶位置int Capacity;//记录数组容量}Stack;
这里注意：
Top(记录栈顶位置)变量的初值一般有两种情况：
-1和
0Top初值不同，接口的实现 会有细微的差异：
初值为-1，
Top指向数组最后一个元素的位置；压栈时，
Top先加一，再入数据
初值为
0，
Top指向数组最后一个元素的下一位置；压栈时，先入数据，
Top再加一
并且，由于 Top 有不同的情况，与栈有关的操作最好使用已有接口进行
栈的接口及实现
栈的常用接口
由于
栈
规定了
入栈出栈
的位置，所以只有固定的
压栈出栈
操作，不支持其他位置的插入
所以
栈
的接口一般有：
- 初始化 StackInit
- 入栈 StackPush
- 出栈 StackPop
- 取栈顶元素 StackTop
- 栈元素个数 StackSize
- 判空 StackEmpty
- 栈销毁 StackDestroy
初始化 StackInit
Top
初始化有两种情况，这里选择 初始化为
0
voidStackInit(Stack *pst){assert(pst);
pst->data =NULL;
pst->Top = pst->Capacity =0;}
入栈 StackPush
因为只有 压栈 时，栈的容量可能会满，所以就不需要单独写一个判断栈满的函数了
voidStackPush(Stack *pst, StackDataType x){assert(pst);if(pst->Top == pst->Capacity)// 数组已满 扩容{int newCapacity = pst->Capacity ==0?4: pst->Capacity *2;
StackDataType *tmp =(StackDataType*)realloc(pst->data,sizeof(StackDataType)* newCapacity);if(tmp ==NULL){printf("realloc fail\n");exit(-1);}
pst->data = tmp;
pst->Capacity = newCapacity;}
pst->data[pst->Top++]= x;/* Top 初值为 -1
psy->data[++pst->Top] = x;
*/}
出栈 StackPop
因为 由
数组
实现的栈，开辟的空间是
不能单独释放
的。即：
出栈
，不需要释放空间，也不需要修改数据
所以
出栈
非常的简单！！
voidStackPop(Stack *pst){assert(pst);assert(pst->Top >0);//保证栈不为空/* Top 初值为 -1
assert(pst->Top > -1);
*/--pst->Top;}
因为，在
栈
中是由
Top
来决定
栈
存放数据的数量的，所以
Top
减小就代表
有数据出栈
取栈顶元素 StackTop
// 取栈顶元素
StackDataType StackTop(const Stack *pst){assert(pst);assert(pst->Top >0);return pst->data[pst->Top -1];/* Top 初值为 -1
return pst->data[pst->Top];
*/}
判空 StackEmpty
// 判空
bool StackEmpty(const Stack *pst){assert(pst);return pst->Top ==0;/* Top 初值为 -1
return pst->Top == -1;
*/}
栈元素个数 StackSize
intStackSize(const Stack *pst){assert(pst);return pst->Top;/* Top 初值为 -1
return pst->Top + 1;
*/}
栈销毁 StackDestroy
voidStackDestory(Stack *pst){assert(pst);free(pst->data);
pst->data =NULL;
pst->Capacity = pst->Top =0;}
至此，
栈
的结构以及
常用接口
的 分析与实现 都已经完成了。
栈结构及接口
是非常简单的，但是关于
栈
的题可能会很麻烦
(因为后进先出)
结语
本篇文章 对 数据结构：
栈 结构及接口
进行了 分析和实现。
但只是 由
数组实现的栈
，有兴趣可以
用链表实现栈
OK~ 本篇文章到此结束~
求点赞、评论、收藏~
版权归原作者 七月July. 所有， 如有侵权，请联系我们删除。