前一章《线性表的定义与实现》介绍了线性表，后面我们通过对线性表进行扩展实现常用的其他数据结构，比如限制线性表的一些基本操作来实现栈和队列。
一、定义
栈是限定在表的同一端进行插入或删除的线性表，进行插入或删除操作的一端称为栈顶，另一端为栈底。
插入数据元素的操作叫做入栈，删除数据元素的操作叫做出栈，它具有先进后出（First In Last Out，FILO）的特性。
二、栈的基本操作分析
线性表可以通过顺序存储和链式存储来实现，作为操作受限的线性表也一样。
顺序存储结构中，一般会使用数组来实现，定义一个栈，约定使用 top 来存放栈顶元素的位置，当 top=-1 时表示栈为空，当 top=array.length-1 时，表示栈满。
顺序栈的数据元素空间大小是预先分配好的，当空间全部满了后再入栈会溢出，栈为空时出栈会异常。
链式存储结构中，可以使用单向链表来实现，栈的插入和删除等操作都只会在栈顶一端进行，所以把链表头部作为栈顶效率更高。
1. 入栈
顺序存储中，通过 top 来定位栈顶位置，然后做入栈操作，执行完后 top 移到新的栈顶位置。
链式存储中，将新的结点添加到链表头部，完成入栈。
2. 出栈
顺序存储中，通过 top 定位并获取栈顶元素，然后做出栈操作，执行完后 top 移动到新的栈顶位置。
链式存储中，获取到头部结点元素后，然后删除该结点。
三、栈的常见应用场景
1. 函数调用
任何一种高级编程语言（C、Java 等）都支持把反复执行的程序段封装成一个函数（或方法）。
在函数中支持调用另一个函数，这种嵌套调用的方式就是基于栈来实现的。
函数相关的信息都存储在栈内的数据元素中，我们把这个称作栈帧。
例如在 Java 中，程序 main -> method_1 -> method_2 -> method_3 调用情况如下：
2. 表达式求值
我们可以使用两个栈结构来实现四则混合运算表达式的求值，两个栈分别用于存储操作数和运算符。
例如编程对
3. 浏览器的前进后退功能
浏览器中对历史页面的前进后退功能，也可以使用两个栈来实现。
例如先后请求 baidu.com、yahoo.com 和 sina.com。
四、代码示例
具体的代码实现如下：
Gitee：
https://gitee.com/code_artist/DataStructure
GitHub：
https://github.com/AiJiangnan/DataStructure
原文始发于微信公众号（CodeArtist）：栈的定义与实现
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/138022.html
