栈介绍

想象一下网球筒，羽毛球筒，薯片灌装。一个洞口的那种。

栈是一个先进后出，后进先出的有序表
栈是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端为变化的一段，称为栈顶（Top），另一端为固定的一段，称为栈底（Bottom）
入栈叫Push，出栈叫Pop
image.png

栈的引用场景

  1. 子程序的调用：在跳往子程序前，会将下一个指令的地址存到队栈中，直到子程序执行完后再将地址取出，以回到原来的程序中
  2. 处理递归调用：和子程序的调用类似，只是除了储存下一个指令的地址外，也将参数，局部变量等数据存入堆栈中
  3. 表达式的转换[中缀表达式转后缀表达式]与求值（实际解决）
  4. 二叉树的遍历
  5. 图形的深度优先（depth-first）搜索法

    关于栈溢出

    在内存中栈和堆两个存放数据的地方。
    栈很小。每次调用一个方法，都会在栈里面开辟一个内存空间，用来存放这个未执行完的方法，执行完了就出栈。

拿递归说。

  1.         static void Main(string[] args)
  2.         {
  3.             A(10);
  4.         }
  5.         static void A(int n)
  6.         {
  7.             Console.WriteLine(n);
  8.             if(n!=0)
  9.                 A(n - 1);
  10.         }

一个简单的递归代码，首先调用A(10)这个方法，在栈中开辟一块内存空间存放这个方法变量等。最开始A(10)入栈，在栈底。
在A(10)还没执行完，又调用A(9)这个方法，又在栈中开辟空间存放，入栈，A(9)入栈在A(10)上面，因为A(10)先入栈，A(9)也没执行完，在A(9)里面又调用A(8)，入栈……..
最终栈结构

A(0) A(1) ……….. A(9) A(10)

执行A(0)，不递归了，A(0)这个方法彻底执行完了，出栈，然后A(1)出栈………..

我这栈里面才10个方法，那哪儿够啊。递归多一点，使劲往栈里面加等待执行的方法，这些方法不断地被新方法压在栈底层，都盼望着栈顶别加了，赶紧执行完我们好排队出去，结果一直入栈，栈底的方法不堪重负，直接压死，栈溢出错误。
公司的笔记本递归三万多次就溢出了。