下载文档原格式
必备算法：递归！⽆论你是前端开发，还是后端开发，都需要掌握它！递归是⼀种⾮常重要的算法思想，⽆论你是前端开发，还是后端开发，都需要掌握它。
在⽇常⼯作中，统计⽂件夹⼤⼩，解析xml⽂件等等，都需要⽤到递归算法。
它太基础太重要了，这也是为什么⾯试的时候，⾯试官经常让我们⼿写递归算法。
本⽂呢，将跟⼤家⼀起深⼊挖掘⼀下递归算法~什么是递归？递归，在计算机科学中是指⼀种通过重复将问题分解为同类的⼦问题⽽解决问题的⽅法。
简单来说，递归表现为函数调⽤函数本⾝。
在知乎看到⼀个⽐喻递归的例⼦，个⼈觉得⾮常形象，⼤家看⼀下：❝递归最恰当的⽐喻，就是查词典。
我们使⽤的词典，本⾝就是递归，为了解释⼀个词，需要使⽤更多的词。
当你查⼀个词，发现这个词的解释中某个词仍然不懂，于是你开始查这第⼆个词，可惜，第⼆个词⾥仍然有不懂的词，于是查第三个词，这样查下去，直到有⼀个词的解释是你完全能看懂的，那么递归⾛到了尽头，然后你开始后退，逐个明⽩之前查过的每⼀个词，最终，你明⽩了最开始那个词的意思。
❞来试试⽔，看⼀个递归的代码例⼦吧，如下：递归的特点实际上，递归有两个显著的特征,终⽌条件和⾃⾝调⽤:✿⾃⾝调⽤：原问题可以分解为⼦问题，⼦问题和原问题的求解⽅法是⼀致的，即都是调⽤⾃⾝的同⼀个函数。
✿终⽌条件：递归必须有⼀个终⽌的条件，即不能⽆限循环地调⽤本⾝。
结合以上demo代码例⼦，看下递归的特点：递归与栈的关系其实，递归的过程，可以理解为出⼊栈的过程的，这个⽐喻呢，只是为了⽅便读者朋友更好理解递归哈。
以上代码例⼦计算sum（n=3）的出⼊栈图如下：为了更容易理解⼀些，我们来看⼀下函数sum（n=5）的递归执⾏过程，如下：✿计算sum（5）时，先sum（5）⼊栈，然后原问题sum（5）拆分为⼦问题sum（4），再⼊栈，直到终⽌条件sum（n=1）=1，就开始出栈。
✿ sum（1）出栈后，sum（2）开始出栈，接着sum（3）。
✿最后呢，sum（1）就是后进先出，sum（5）是先进后出，因此递归过程可以理解为栈出⼊过程啦~递归的经典应⽤场景哪些问题我们可以考虑使⽤递归来解决呢？即递归的应⽤场景⼀般有哪些呢？✿阶乘问题✿⼆叉树深度✿汉诺塔问题✿斐波那契数列✿快速排序、归并排序（分治算法体现递归）✿遍历⽂件，解析xml⽂件递归解题思路解决递归问题⼀般就三步曲，分别是：✿第⼀步，定义函数功能✿第⼆步，寻找递归终⽌条件✿第⼆步，递推函数的等价关系式这个递归解题三板斧理解起来有点抽象，我们拿阶乘递归例⼦来喵喵吧~1、定义函数功能定义函数功能，就是说，你这个函数是⼲嘛的，做什么事情，换句话说，你要知道递归原问题是什么呀？⽐如你需要解决阶乘问题，定义的函数功能就是n的阶乘，如下：2、寻找递归终⽌条件递归的⼀个典型特征就是必须有⼀个终⽌的条件，即不能⽆限循环地调⽤本⾝。
递归栈溢出解决方法递归是一种常见的解决问题的方法，但是它也容易引起栈溢出的问题，特别是当递归调用层次深或者问题规模较大时。
栈溢出通常发生在递归函数中，因为每次递归调用会将相关的数据存储在调用栈中，当递归调用层次过深时，栈的内存空间可能会耗尽，导致栈溢出的错误。
下面是一些解决递归栈溢出问题的方法：1.优化递归算法：在解决问题时，优先考虑优化递归算法，尽量减少递归调用次数和递归深度。
可以尝试使用迭代或其他非递归的方法来解决问题。
2.增加栈空间：如果递归调用确实无法避免，可以通过增加栈的大小来增加递归调用的容量。
一些编程语言或者编译器提供了设置栈大小的选项，可以在程序运行时调整栈的大小。
3.尾递归优化：尾递归是指递归函数中递归调用是函数最后一步操作的情况。
一些编译器或解释器支持尾递归优化，在优化过程中会将递归调用转化为迭代，从而避免栈溢出的问题。
4.分而治之：将大问题分解为多个小问题，在每个小问题中进行递归调用。
这样可以减少递归深度，缩小每个递归调用的规模，从而减少栈溢出的可能性。
5.动态规划：有些问题可以使用动态规划的方法解决，它通过保存中间结果来避免重复计算，从而减少递归调用的次数。
6.使用循环代替递归：在一些情况下，可以使用循环代替递归来解决问题。
循环通常比递归更高效，因为它不会占用大量的栈空间。
7.减少内存使用：除了减少递归调用的次数和递归深度外，还可以考虑减少每个递归调用所占用的内存空间。
可以通过优化数据结构的使用和算法的实现来减少内存使用。
总结起来，解决递归栈溢出问题的方法可以分为两类：一是通过优化递归算法和减少递归调用次数来避免栈溢出，二是通过增加栈空间、尾递归优化、分而治之、动态规划、使用循环代替递归和减少内存使用等方法来解决栈溢出的问题。
具体选择哪种方法取决于具体情况和问题的特点。
在实际应用中，我们可以综合考虑这些方法，根据具体情况选择适合的解决方案。
栈在递归中的作用栈是一种具有特殊性质的线性数据结构，在其中元素的插入和删除操作只能在栈的顶部进行。
栈的特点是元素按照后进先出的顺序进行处理，即最后插入到栈中的元素最先被访问到。
递归是一种程序设计技巧，通过一个函数在其定义中调用自身来解决问题。
递归函数在解决问题时以一种分而治之的办法，将原始问题划分为较小的子问题，并通过解决子问题来解决原始问题。
那么，栈在递归中起到了什么作用呢？一、存储临时变量：递归函数在每一次调用自身时都会入栈，该栈用来保存每个递归调用时的临时变量。
在递归函数内部定义的变量会保存在栈中，每次函数调用时，这些局部变量都会被压入栈中。
当函数的递归调用完成后，栈中保存的该函数的局部变量会被弹出，以便为下一个递归调用或其他操作提供内存空间。
这样，栈起到了一个保存临时变量的作用。
二、存储函数调用的返回地址：在递归调用时，每次调用后都需要返回到上一层调用处。
栈的另一个作用是存储函数调用的返回地址。
当一个函数调用了自身，并进行了递归调用时，当前函数的上下文信息（包括函数指针、参数和局部变量等）都会被保存在栈中，然后在递归调用完成后，栈中保存的上下文信息将被弹出，返回到上一层函数的下一条执行指令的位置，继续执行下去。
三、维护递归层次关系：递归调用时，每次调用自身都需要将当前的状态保存在栈中，这样可以保留每一次递归调用的上下文信息。
栈的深度也反映了递归的层次关系。
当递归调用层数很大时，栈的深度也会相应增加。
四、确保函数调用的正确性：栈在递归中还发挥了确保函数调用的正确性的作用。
每一次递归调用都会将当前的状态保存在栈中，包括参数、局部变量、返回地址等信息。
这样，即使在递归调用过程中发生了其他函数的调用，当递归调用完成后，栈中保存的状态信息都能够正确恢复，确保程序的正确执行。
总结来说，栈在递归中起到了存储临时变量、存储函数调用的返回地址、维护递归层次关系以及确保函数调用的正确性等作用。
栈的使用使递归函数能够按照正确的顺序进行递归调用，并在递归调用完成后正确返回上一层函数的下一条执行指令的位置。
递归树形结构的替代方案
1. 迭代算法，在某些情况下，可以使用迭代算法来替代递归。
迭代算法通常更高效，因为它们不会涉及到递归函数调用的开销。
例如，可以使用循环来遍历树结构，而不是使用递归。
2. 栈或队列，在处理树形结构时，可以使用栈或队列来代替递归。
这种方法通常被称为"迭代深度优先搜索"或"迭代广度优先搜索"。
通过维护一个栈或队列来跟踪待处理的节点，可以避免递归调用。
3. 并查集，在一些特定的场景下，可以使用并查集来代替递归
树形结构。
并查集是一种数据结构，用于维护元素之间的等价关系，通常用于解决连通性和等价性的问题。
4. 线索化二叉树，对于二叉树结构，可以使用线索化技术来代
替递归。
线索化二叉树是一种对普通二叉树进行改造，使得可以在
不使用递归的情况下进行中序遍历。
5. 哈希表或索引结构，在某些情况下，可以使用哈希表或其他
索引结构来代替递归树形结构。
这种方法通常适用于需要快速查找
和检索节点的场景。
总之，替代递归树形结构的方案取决于具体的问题和需求，需要根据实际情况进行选择。
在一些情况下，递归可能是最简洁和直观的解决方案，但在性能要求较高或者存在栈溢出风险的情况下，可以考虑使用上述的替代方案。
栈的出队顺序一、栈的出队顺序——先进后出的数据结构二、栈的基本操作——入栈和出栈栈的基本操作包括入栈和出栈。
入栈是指将元素添加到栈的顶部，出栈是指将栈顶的元素移除。
入栈和出栈是栈的两个基本操作，它们是栈的核心功能。
通过这两个操作，我们可以实现对栈中元素的添加和删除。
三、栈的应用——逆波兰表达式求值逆波兰表达式是一种不需要括号来标识优先级的数学表达式表示方法。
在逆波兰表达式中，操作符位于操作数的后面，这样可以避免使用括号来改变运算的顺序。
逆波兰表达式求值是栈的一个典型应用场景。
通过使用栈来保存操作数，我们可以按照逆波兰表达式的顺序依次计算出结果。
四、栈的应用——括号匹配括号匹配是栈的另一个重要应用场景。
在编程中，经常需要对括号进行匹配判断，以确保代码的正确性。
使用栈可以方便地实现对括号的匹配判断。
当遇到左括号时，将其入栈；当遇到右括号时，与栈顶元素进行匹配判断。
如果匹配成功，则将栈顶元素出栈；如果匹配失败，则表明括号不匹配。
五、栈的应用——浏览器的前进和后退功能浏览器的前进和后退功能是栈的又一个典型应用。
当我们在浏览器中点击前进按钮时，当前页面的URL将被压入栈中；当我们点击后退按钮时，栈顶元素将被弹出并打开对应的页面。
通过使用栈来保存浏览历史记录，我们可以方便地实现浏览器的前进和后退功能。
六、栈的应用——实现递归递归是一种常见的编程技巧，它可以简化代码的实现。
在递归过程中，每一次递归调用都会创建一个新的栈帧，用于保存函数的局部变量和返回地址。
通过使用栈来保存每个栈帧，我们可以实现递归的执行。
七、栈的应用——系统调用和中断处理在操作系统中，系统调用和中断处理是栈的重要应用场景。
当发生系统调用或中断时，当前的程序状态将被保存到栈中，包括程序计数器、寄存器的值和局部变量等。
通过使用栈来保存这些信息，操作系统可以在中断处理或系统调用结束后恢复程序的执行。
八、栈的应用——迷宫求解迷宫求解是一个经典的问题，可以通过使用栈来解决。
栈的应用及特性栈是计算机科学中一种非常重要的数据结构，具有广泛的应用和独特的特性。
下面将详细介绍栈的应用及特性。
一、栈的应用：1. 函数调用：在程序执行过程中，函数的调用和返回通常采用栈进行管理。
当一个函数被调用时，函数的参数和局部变量被压入栈中，函数执行完毕后，这些信息会被弹出栈恢复到调用函数的状态。
2. 表达式求值：在编程语言中，栈可用于表达式求值、中缀表达式转换为后缀表达式等相关操作。
通过利用栈的先进后出特性，可以方便地实现这些功能。
3. 递归算法：递归算法中的递归调用也可以通过栈来实现。
当算法需要递归调用时，将函数和相关变量的信息压入栈中，等到递归结束后，再从栈中弹出恢复状态。
4. 括号匹配：栈也常用于判断表达式中的括号是否匹配。
遍历表达式，遇到左括号时压入栈，遇到右括号时弹出栈顶元素，如果匹配则继续，不匹配则判定为括号不匹配。
5. 浏览器的前进后退：浏览器的前进后退功能可以使用栈实现。
每次浏览一个网页时，将该网页的URL压入栈中，点击后退按钮时，再从栈中弹出上一个URL，即可实现返回上一个网页的功能。
6. 撤销操作：在图形界面软件中，通常会有撤销操作。
使用栈可以将每一步操作的状态依次压入栈中，当用户需要撤销时，再从栈中弹出最近的状态，恢复到之前的操作状态。
二、栈的特性：1. 先进后出：栈是一种后进先出（LIFO）的数据结构，即最新添加的元素最先被访问或者删除。
这一特性使得栈能够方便地实现函数调用和返回等操作。
2. 只能操作栈顶元素：由于栈的特性，只能访问或者修改栈顶元素，无法直接访问或者修改栈中的其他元素。
需要先将栈顶元素弹出后，才能访问或者修改下一个栈顶元素。
3. 顺序存储结构：栈可以使用数组或者链表实现。
使用数组实现时，需要指定栈的最大容量，而使用链表实现时，没有容量限制。
4. 操作复杂度：栈的插入和删除操作只涉及栈顶元素，所以其操作复杂度为O(1)。
但是栈的搜索和访问操作需要从栈顶开始遍历，所以其操作复杂度为O(n)。
一、实验目的1. 理解栈的基本概念、特点及逻辑结构；2. 掌握栈的顺序存储和链式存储结构；3. 熟练掌握栈的基本操作，如入栈、出栈、判断栈空等；4. 理解栈在递归算法中的应用；5. 探究栈在实际问题中的应用。
二、实验内容1. 栈的定义与特点2. 栈的顺序存储结构3. 栈的链式存储结构4. 栈的基本操作5. 栈在递归算法中的应用6. 栈在实际问题中的应用三、实验步骤1. 栈的定义与特点（1）栈是一种后进先出（LIFO）的数据结构；（2）栈的元素只能从一端（栈顶）进行插入和删除操作；（3）栈具有两个基本操作：入栈和出栈。
2. 栈的顺序存储结构（1）使用数组来实现栈的顺序存储结构；（2）定义一个数组作为栈的存储空间；（3）定义栈顶指针top，初始值为-1；（4）定义栈的最大容量maxSize。
3. 栈的链式存储结构（1）使用链表来实现栈的链式存储结构；（2）定义一个链表节点，包含数据域和指针域；（3）定义栈顶指针top，初始时指向链表头节点。
4. 栈的基本操作（1）入栈操作：将元素插入到栈顶，栈顶指针向上移动；（2）出栈操作：删除栈顶元素，栈顶指针向下移动；（3）判断栈空：判断栈顶指针是否为-1，是则栈空，否则栈非空。
5. 栈在递归算法中的应用（1）斐波那契数列的递归算法；（2）汉诺塔问题；（3）迷宫问题。
6. 栈在实际问题中的应用（1）括号匹配问题；（2）表达式求值问题；（3）递归函数的调用栈。
四、实验结果与分析1. 栈的定义与特点通过本次实验，我们深入理解了栈的基本概念、特点及逻辑结构，掌握了栈的后进先出特性。
2. 栈的顺序存储结构使用数组实现栈的顺序存储结构，操作简单高效。
在实验过程中，我们实现了栈的基本操作，如入栈、出栈、判断栈空等。
3. 栈的链式存储结构使用链表实现栈的链式存储结构，具有灵活性和扩展性。
在实验过程中，我们实现了栈的基本操作，如入栈、出栈、判断栈空等。
4. 栈的基本操作通过实验，我们熟练掌握了栈的基本操作，如入栈、出栈、判断栈空等，为后续递归算法和实际问题中的应用奠定了基础。
目录摘要 (1)研究背景 (2)基本概念及特性.......................................................... (2)栈的运算 (3)栈的运用举例 (5)递归原理 (6)迷宫求解 (8)栈实现迷宫问题 (8)递归实现迷宫算法 (8)参考文献 (9)附录 (9)栈与递归的关系摘要：栈（stack）又称堆栈，他是线性表中的一种特殊情况，并且也是最简单的情况之一，它是一种运算受限的线性表，其限制是仅仅允许在表的一端进行插入和删除运算。
由于栈的插入和删除运算仅在栈的一端实现，后进栈的元素必定先出栈，所以又把栈称为后进先出表。
递归是一种非常重要的概念和解决问题的方法，在计算机科学和数学领域有着广泛的应用，递归调用是计算机解决部分疑难问题特别有效,易于实现的一种算法。
比如著名的汉诺塔问题、八皇后问题、树的遍历等如果不用递归算法解决,几乎难以实现,大部分计算机语言教材都涉及到这一重要算法。
在计算机系统内，执行递归函数是通过栈来实现的，栈中的每一个元素包含有递归函数的每一参数域、每一个局部变量和调用后的返回地址域，其中引用参数域只保存传送来的实参的地址，以便按此地址访问实参的储存空间存取其值，其他的每个域是用于存储其值的实际存储空间，每次进行函数调用的时候，都要把相应的填压入栈，每次结束调用时，都按照本次返回地址返回到指定的位置进行，并且自动做一次退栈操作，使得下一层所使用的参数称为新的栈顶，继续被使用。
栈与递归都能够解决一些实际问题，主要是通过C/C++语言来实现编程运算，得到相应的结果。
递归和栈是可以相互转换的，当编写递归算法时，虽然表面上没有使用栈，但是系统执行时会自动建立和使用栈，本文中在求解迷宫问题时就充分的体现出了这一点。
关键词：栈递归C/C++语言迷宫问题一、研究背景递归调用是计算机解决部分疑难问题特别有效,易于实现的一种算法。
比如著名的汉诺塔问题、八皇后问题、树的遍历等如果不用递归算法解决,几乎难以实现,大部分计算机语言教材都涉及到这一重要算法,计算机执行递归算法时，是通过栈来实现的。
具体说来，就是在（递归过程或递归函数）开始运行时，系统首先为递归建立一个栈，该栈的元素类型（数据域）包括值参、局部变量和返回地址；在每次执行递归调用语句时之前，自动把本算法中所使用的值参和局部变量的当前值以及调用后的返回地址压栈（一般形象地称为“保存现场”，以便需要时“恢复现场”返回到某一状态），在每次递归调用结束后，又自动把栈顶元素（各个域）的值分别赋给相应的值参和局部变量（出栈），以便使它们恢复到调用前的值，接着无条件转向（返回）由返回地址所指定的位置继续执行算法。
利用栈将递归向非递归转化时所采用的方法，实质是用人工写的语句完成了本该系统程序完成的功能，即：栈空间中工作记录的保存和释放。
二、基本概念及特性1．栈的概念和特性栈（stack）是一种特殊的线性表。
作为一个简单的例子，可以把食堂里冼净的一摞碗看作一个栈。
在通常情况下，最先冼净的碗总是放在最底下，后冼净的碗总是摞在最顶上。
而在使用时，却是从顶上拿取，也就是说，后冼的先取用，后摞上的先取用。
如果我们把冼净的碗“摞上”称为进栈（压栈），把“取用碗”称为出栈（弹出），那么上例的特点是：后进栈的先出栈。
然而，摞起来的碗实际上是一个线性表，只不过“进栈”和“出栈”都在最顶上进行，或者说，元素的插入和删除操作都是在线性表的一端进行而已。
一般而言，栈是一个线性表，其所有的插入和删除操作均是限定在线性表的一端进行，允许插入和删除的一端称栈顶(Top)，不允许插入和删除的一端称栈底(Bottom)。
若给定一个栈S=（a1, a2，a3，……，an），则称a1为栈底元素，an为栈顶元素，元素ai 位于元素ai-1之上。
栈中元素按a1, a2，a3，……，an的次序进栈，如果从这个栈中取出所有的元素，则出栈次序为an , an-1，……，a1。
也就是说，栈中元素的进出是按后进先出的原则进行，这是栈结构的重要特征。
因此栈又称为后进先出(LIFO—Last In First Out)表。
2.递归的概念和特性1.所谓的递归，是指函数在执行过程中自己调用了自己或者说某种数据结构在定义时又引用了自身。
这两种情况都可理解为递归。
比如：void fun(){..fun()..}//fun以上函数fun就是一个递归函数。
而针对于各种数据结构中的递归结构就更多了，如单链表，广义表，树。
在这些递归结构中，具有一个相同的特征：其中的某个域的数据类型是其结点类型本身！2.递归算法的大致结构为：a.递归出口b.递归体一个递归算法，当其问题求解的规模越来越小时必定有一个递归出口，就是不再递归调用的语句。
递归体则是每次递归时执行的语句序列。
比如以下简要描述的递归函数中：f(n)=1 (当n=0时)f(n)=n*f(n-1) （当n>0时）这个递归函数，实际是求n的阶乘。
当n=0时，不再递归调用，而当其值置为1；当n>0时，就执行n*f(n-1)，这是递归调用。
从整体上理解递归算法的大致结构有利于我们在设计递归算法时，从总体上把握算法的正确性。
三、栈的运算3.1栈运算的实现栈运算操作的具体实现取决于栈的存储结构，存储结构不同，其算法描述也不同，下面分别给出栈的运算在顺序存储结构和链接存储结构上实现的具体算法。
3.1.1 栈的操作在顺序存储结构上的实现假定采用顺序存储结构定义的栈用标识符S表示，其类型为已经给出过的Stack 记录类型。
（1）初始化栈：void InitStack(Stack& S)//初始化栈S，即把它置为空{S.top=-1;}(2)把一个栈清除为空在顺序存储方式下，同初始化栈的算法相同void ClearStack(Stack& S)//清除栈S中的所有元素，使之成为一个空栈{S.top=-1;}（3）检查栈是否为空void StackEmpty(Stack& S)//判断栈S是否为空，若是则返回1，否则返回0 {returnS.top=-1;}（4）读取栈顶元素ElemTepy Peek(Stack& S)//返回栈S的栈顶元素，但不移动栈顶指针{//若栈为空则终止程序运行If (S.top= =-1){cerr <<”Stack is empty!”<<endl；exit (1);}//返回栈顶元素值return S.Stack[S.top];}（5）向栈中插入元素void Push (Stack& S,const ElemType& item)//元素item进栈，即插入到栈顶{//若栈已满则终止程序运行if (S.top = =StackMaxSize-1){cerr<<”Stack overflow!”<<endl;Exit(1)}//栈顶指针后移一个位置S.top++;//将item的值赋给新的栈顶位置S.Stack[S.top]=item;}（6）从栈中删除元素ElemType Pop(Stack& S)//删除栈顶元素并返回之{//若栈为空则终止程序运行If (S.top= =-1){cerr <<”Stack is empty!”<<endl；exit (1);}//暂存栈顶元素以便返还ElemType temp = S.Stack[S.top];//栈顶指针元素向前移动一个位置S.top--；//返回原栈顶元素的值Return temp；}从出栈算法可以看出，原栈顶元素的值没有被概念，所以可以不使用临时变量保存它，返回语句中返回S.stack[S.top+1]的值即可。
（7）检查栈是否已满int StackFull(Stack & S)//若栈已满则返回到1，否则返回到0，此函数为顺序栈所特有{return S.top = = StackMaxSize-1;}3.1.2 栈的操作在链接存储结构上的实现假定链表中的结点采用LNode结点类型，并假定栈顶指针用HS表示，下面给出对HS所指向的链栈进行每一种栈操作的算法。
（1）初始化链栈void InitStack(LNode*&HS){HS=NULL;//将链栈置空}（2）清除链栈为空void ClearStack(LNode*&HS){LNode * cp,*cp;//用cp作为指向待删除的结点，np指向cp的后继结点cp=HS;//给cp指针附初值，使之指向栈顶结点while (cp!=NULL){//从栈顶到栈底依次删除每个结点np=cp->next;delete cp;cp = np;}HS=NULL;//置链栈为空}（3）检查链栈是否为空int StackEmpty(LNode*HS)//HS为值参或引用形参均可{return HS= =NULL;}（4）读取栈顶元素ElemType Peek(LNode * HS)//HS为值参或引用形参均可{if (HS = = NULL){cerr < < “linked stack is empty !”<<endl;Exit (1);}Return HS- >data;}（5）向链栈中插入一个元素void Push (LNode * & HS ,const ElemType &item){//为插入元素获取动态结点LNode*newtr = new LNode;if (newptr = =NULL){cerr <<”Memory allocation failare !”< <endl;Exit(1);}//给新分配的结点赋值newptr - > data = item;//向栈顶插入新结点newptr ->next = HS;HS = newptr;}（6）从链栈中删除一个元素ElemType Pop (LNode * & HS){if(HS = = NULL){cerr <<”Linked stack is empty !”<<endl;exit(1);}LNode * p=HS;//暂存栈顶结点HS=HS->next;//使栈顶指针指向其后继结点ElemType temp = p - > data ;//暂存原栈顶元素delete p；Return temp；//返回原栈顶元素}四、栈的应用举例下面就简单举两个例子来说明一下栈的应用例1、从键盘上输入一批整数，然后按照相反的次序打印出来。
