1.基本概念
栈（也称下压栈，堆栈）是仅允许在表尾进行插入和删除操作的线性表。我们把允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom）。栈是一种后进先出（Last In First Out）的线性表，简称（LIFO）结构。栈的一个典型应用是在集合中保存元素的同时颠倒元素的相对顺序。
栈的实现通常有两种方式：
·基于数组的实现（顺序存储）
·基于链表的实现（链式存储）
2.栈的顺序存储结构
栈的顺序存储结构其实是线性表顺序存储结构的简化，我们可以简称它为「顺序栈」。其存储结构如图9-12所示：
图9-12 顺序栈
优点：
1.每项操作的用时都与集合大小无关；
2.空间需求总是不超过集合大小乘以一个常数；
缺点：出栈和入栈操作有时会调整数组大小，这项操作的耗时和栈的大小成正比；
3.两栈共享空间
用一个数组来存储两个栈，让一个栈的栈底为数组的始端，即下标为0，另一个栈的栈底为数组的末端，即下标为n-1。两个栈若增加元素，栈顶都向中间延伸。其结构如图9-13所示：
图9-13 两栈共享空间
这种结构适合两个栈有相同的数据类型并且空间需求具有相反的关系的情况，即一个栈增长时另一个栈缩短。如，买股票，有人买入，就一定有人卖出。
4.栈的链式存储结构
栈的链式存储结构，简称链栈。为了操作方便，一般将栈顶放在单链表的头部。通常对于链栈来说，不需要头节点。
其存储结构如图图9-14所示：(www.xing528.com)
图9-14 栈的链式存储
优点：
1.所需空间和集合的大小成正比；
2.操作时间和集合的大小无关；
3.链栈的出栈和入栈操作的时间复杂度都为O（1）。
缺点：每个元素都有指针域，增加了内存的开销。
顺序栈与链栈的选择和线性表一样，若栈的元素变化不可预料，有时很大，有时很小，那最好使用链栈。反之，若它的变化在可控范围内，使用顺序栈会好一些。
5.栈的应用——递归
栈的一个最重要的应用就是递归。那么什么是递归呢？递归从狭义上来讲，指的是计算机科学中一个模块的程序在其内部调用自身的技巧。
我们把一个直接调用自身或通过一系列语句间接调用自身的函数，称为递归函数。每个递归函数必须至少有一个结束条件，即不在引用自身而是返回值退出。否则程序将陷入无穷递归中。
一个递归的例子：斐波那契数列（Fibonacci）
递归实现：
迭代实现：
迭代与递归的区别：
·迭代使用的是循环结构，递归使用的是选择结构。
·递归能使程序的结构更清晰、简洁，更容易使人理解。但是大量的递归将消耗大量的内存和时间。
编译器使用栈来实现递归。在前行阶段，每一次递归，函数的局部变量、参数值及返回地址都被压入栈中；退回阶段，这些元素被弹出，以恢复调用的状态。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
