- 01.栈的顺序存储结构及实现
- 02.进栈
- 03.出栈
- 04.栈的链式存储结构及实现
- 05.进栈
- 06.出栈
- 07.两种栈形式比较
- 博客笔记大汇总【16年3月到至今】，包括Java基础及深入知识点，Android技术博客，Python学习笔记等等，还包括平时开发中遇到的bug汇总，当然也在工作之余收集了大量的面试题，长期更新维护并且修正，持续完善……开源的文件是markdown格式的！同时也开源了生活博客，从12年起，积累共计N篇[近100万字，陆续搬到网上]，转载请注明出处，谢谢！
- 链接地址：https://github.com/yangchong211/YCBlogs
- 如果觉得好，可以star一下，谢谢！当然也欢迎提出建议，万事起于忽微，量变引起质变！
- 顺序存储结构的栈简称为顺序栈，它利用一组地址连续的存储单元依次存放从栈底到栈顶的数据元素。栈底位置固定不变，它的栈顶可以直接通过顺序栈底层数组的数组元素arr[size-1]来访问。顺序栈的存储示意图如下图：
image
- 顺序栈中数据元素的物理关系和逻辑关系是一致的，先进栈的元素位于栈底，栈底元素的存储位置相对也比较小。
- 对于顺序栈的进栈操作而言，只需将新的数据元素存入栈内，然后让记录栈内元素个数的变量加1，程序即可再次通过arr[size-1]重新访问新的栈顶元素。进栈操作示意图如下：
image
- 由于顺序栈底层通常会采用数组来保存数据元素，因此可能出现的情况是：当程序试图让一个数据元素进栈时，底层数据已满，那么就必须扩充底层数组的长度来容纳新进栈的数据元素。
- 对于顺序栈的出栈操作而言，需要将栈顶元素弹出栈，程序要做两件事。
- 让记录栈内元素个数的变量减1.
- 释放数组对栈顶元素的引用。
- 出栈操作示意图如下图:
image
- 程序可以采用单链表来保存栈中所有元素，这种链式结构的栈也被称为栈链。对于栈链而言，栈顶元素不断地改变，程序只要使用一个top引用来记录当前的栈顶元素即可。top引用变量永远引用栈顶元素，再使用一个size变量记录当前栈中包含多少个元素即可。如下图：
image
- 对于栈链的进栈操作，程序只需要做如下两件事：
- 让top引用指向新元素添加的元素，新元素的next引用指向原来的栈顶元素。
- 让记录栈内元素个数的size变量加1.
- 进栈操作示意图如下：
image
- 对于链栈的出栈操作，需要将栈顶元素弹出栈，程序需要做两件事情：
- 让top引用指向原栈顶元素的下一个元素，并释放原来的栈顶元素
- 让记录栈内元素个数的size变量减1.
- 出栈操作示意图如下：
image
- 对于顺序栈来说，程序开始就需要在底层为他开辟一块连续的内存（数组）,这个空间浪费其实很大.从空间利用率的角度说，链栈的空间利用率比顺序栈的空间利用率要高一些。
- github：https://github.com/yangchong211
- 知乎：https://www.zhihu.com/people/yczbj/activities
- 简书：http://www.jianshu.com/u/b7b2c6ed9284
- csdn：http://my.csdn.net/m0_37700275
- 喜马拉雅听书：http://www.ximalaya.com/zhubo/71989305/
- 开源中国：https://my.oschina.net/zbj1618/blog
- 泡在网上的日子：http://www.jcodecraeer.com/member/content_list.php?channelid=1
- 邮箱：yangchong211@163.com
- 阿里云博客：https://yq.aliyun.com/users/article?spm=5176.100- 239.headeruserinfo.3.dT4bcV
- segmentfault头条：https://segmentfault.com/u/xiangjianyu/articles
- 掘金：https://juejin.im/user/5939433efe88c2006afa0c6e
