什么是栈？
栈是限制插入和删除只能在同一个位置上进行的表，这个位置就是栈的顶端，对于栈的操作主要有三种形式：入栈(将元素插入到表中)，出栈(将表最后的元素删除，也就是栈顶的元素)，返回栈顶元素。栈有时又叫LIFO(后进先出)表。
栈的实现
栈可以有两种实现方式：1）数组实现 2）链表实现
栈的双向链表实现
public class StackForLinked<T> { private int num = 0; public int count { get{return num;} } private Node<T> root = null; private class Node<T> { public T data; public Node<T> prev; public Node<T> next; public Node(T value) { this.data = value; this.prev=null; this.next=null; } public Node(T value,Node<T> prev,Node<T> next):this(value) { this.prev = prev; this.next=next; } } public void Push(T value) { Node<T> node = new Node<T>(value); if(root==null) { root = node; } else { var last= GetLastNode(); last.next = node; node.prev= last; } num++; } public T Pop() { var node=GetLastNode(); if(node==null) throw new Exception(); node.prev.next=null; num--; return node.data; } public T GetTop() { var node =GetLastNode(); if(node==null) throw new Exception(); return node.data; } private Node<T> GetLastNode() { Node<T> p = root; if(root==null) { return null; } while(true) { if(p.next!=null) { p=p.next; } else break; } return p; } }栈的数组实现
public class StackForArray<T> { private static int length = 100; private T[] objList = new T[length]; private int currentIndex = 0； public int count { get { return this.currentIndex;} } private void ensureCapcity(int capcity) { if(capcity < currentIndex) { return; } T[] old = objList; objList = new T[capcity]; for(int i=0;i<old.Length;i++) { objList[i] = old[i]; } } public void Push(T value) { if(currentIndex == length) { ensureCapcity(currentIndex * 2 +1); } objList[currentIndex] = value; currentIndex++; } public T Pop() { if(currentIndex == 0) throw new Exception(); currentIndex--; return objList[currentIndex]; } public T GetTop() { if(currentIndex == 0) { throw new Exception(); } return objList[currentIndex -1]; } }PS：对于链表在添加和删除方面是O(1), 但是在查找方面则是O(N)；数组在查找方面是O(1)操作,但是在插入或者是删除方面涉及到表的中元素的位置上的移动，若数据中的元素较多会带来性能上的损失。所以在考虑使用链表还是使用数组进行存储数据的时候，应该考虑上述所说(数据量大小，插入和删除多还是查找的多)。当前这与栈的关系不太大，因为栈都是在一端进行操作，不会涉及元素移动的问题。
栈的应用
栈的应用有很多，这里只举一些简单的例子：
1.平衡符号：例如判断括号是否成对出现，通过将括号入栈然后碰见成对的括号就出栈，最后判断栈中的元素是否为空，为空则是成对出现，反之则不成对
2.中缀表达式转化为后缀表达式：
中缀表达式和后缀表达式: 例如表达式 a + b * c 这就是我们平时所见的正常的数学计算表达式，在数学上我们也知道怎么计算，但是你把这一段表达式告诉计算机，然后计算出结果，那么这个结果是怎么计算出来的呢？这里就涉及一个概念叫做后缀表达式，首先 a + b * c 会先通过栈转化为 a b c * + 然后再通过栈进行计算从而得出结果，前者通常叫做中缀表达式。随后会有一段代码的例子，可以让你真正的了解数学表达式是如何通过栈进行计算的
3.方法调用：类似于平衡符号的检测，所有的方法调用和返回都是成对的，在开始调用的时候需要在栈内存储一些信息(位置,对应变量的名字和返回地址等)，方法完成后需要从栈中出栈拿到当初存储的信息然后做一些操作,这也正好印证了，当递归调用的时候，不当的递归会出现 Stackoverflow 异常，也就是说在栈(在window下，默认大小是1M )中已经存储不下每一次递归的信息了，就会报这个错误。
PS： 我这里说的都是同步方法，存在一个方法的调用需要等待另一个方法的完成，异步方法还不太了解，期待后续学习会有更多的收获
栈实现基本操作的运算
用栈来实现简单的基本数学运算：+ ，- ，* ， ／ 和（ ）在数学中我们都知道这几种符号的优先级，那么计算机时怎么做到的呢？ 下面我们以一个表达式为例子来实现一下计算机的计算过程
表达式：a + b * c + ( d * e + f ) * g ，除栈外，我们还需要一个输出字符串用来存储生成的后缀表达式，默认情况下为空，出于方便我会使用 [] 代表一个栈，[ 代表栈底，] 代表栈顶，用 | 分割每个元素。
原理
1.对常数输出，对操作符号入栈操作，根据优先级别判断是出栈还是入栈；
2.优先级低的不允许出现在优先级高的后面(栈中存在一个优先级高的符号，此时来了一个低优先级符号，需要进行先把高优先级的符号出栈，然后将低优先级的符号入栈)；
3.同优先级的符号先出栈再入栈；
4.对于存在括号的情况，当前栈顶的元素是 ( 那么接下来的一个符号不比较优先级直接入栈，接下来的操作遵循前3条规则;
5.当遇见 ）的时候，执行出栈操作直到遇见出栈的第一个（ 为止；
6.得到后缀表达式之后再次使用栈进行计算，将后缀表达式中的值入栈，碰见操作符，出栈两个元素执行运算符计算，将计算的结果插入到栈中，直到后缀表达式的尽头，最终结果位于栈顶，出栈即可得到
步骤：
1.将中缀表达式转化为后缀表达式
Step 1 : 我们第一次读取的是常数 a ，直接输出，此时输出的字符串中的值为 a
Step 2 : 继续读取，接下来读取的是操作符号 + ，入栈操作，此时栈中的元素为 [ + ]
Step 3 : 继续读取，接下来读取的是常数 b , 直接输出，此时输出的字符串中的值为 a b
Step 4 : 继续读取，接下来读取的是操作符号 * , 入栈操作，此时栈中的元素为 [ + | * ]
Step 5 : 继续读取，接下来读取的是常数 c , 直接输出，此时输出的字符串中的值为 a b c
Step 6 : 继续读取，接下来读取的是操作符号 + , 栈顶元素 * 的优先级高于 + ，将 * 出栈，之后发现栈顶元素为 +，优先级相同，继续出栈，然后将 + 进栈，此时栈中的元素为[ + ]，输出字符串中的值为 a b c * +
Step 7 : 继续读取，接下来读取的是操作符号 ( , 入栈操作，此时栈中的元素为 [ + | ( ]
Step 8 : 继续读取，接下来读取的是常数 d , 直接输出，此时输出的字符串中的值为 a b c * + d
Step 9 : 继续读取，接下来读取的是操作符号 * , 入栈操作，此时栈中的元素为[ + | ( | * ]
Step 10 : 继续读取，接下来读取的是常数 e , 直接输出，此时输出的字符串中的值为 a b c * + d e
Step 11 : 继续读取，接下来读取的是操作符号 + , 栈顶元素 * 的优先级高于 + ，先执行出栈操作，在执行 + 入栈操作，此时栈中的元素为[ + | ( | +] , 输出字符串中的值为 a b c * + d e *
Step 12 : 继续读取，接下来读取的是常数 f , 直接输出，此时输出的字符串中的值为 a b c * + d e * f
Step 13 : 继续读取，接下来读取的是操作符号 ) , 开始执行出栈操作，直到遇见第一个出栈的元素为 ( 停止，此时栈中的元素为[ + ] , 输出字符串中的值为 a b c * + d e * +
Step 14 : 继续读取，接下来读取的是操作符号 * , 入栈操作，此时栈中的元素为[ + | * ]
Step 15 : 继续读取，接下来读取的是常数 g , 直接输出，此时输出的字符串中的值为 a b c * + d e * f + g
Step 16: 继续读取，到达了末端，开始执行中出栈操作，直到栈为空，此时输出的字符串中的值为 a b c * + d e * f + g * + ，从而得出后缀表达式为：a b c * + d e * f + g * +
2.计算后缀表达式 (Step中的括号的使用是起到辅助清晰的作用，因为并没给字符实际的值)
Step 1 : 读取后缀表达式，第一个遇到的是 a 执行入栈操作，此时栈中的元素为 [ a ]
Step 2 : 继续读取，解下来遇到的是 b ，执行入栈操作，此时栈中的元素为 [ a | b ]
Step 3 : 继续读取，解下来遇到的是 c ，执行入栈操作，此时栈中的元素为 [ a | b | c ]
Step 4 : 继续读取，解下来遇到的是 * ，出栈两个元素，计算 b * c ，然后在执行入栈， 此时栈中的元素为 [ a | b * c ]
Step 5 : 继续读取，解下来遇到的是 + ，出栈两个元素，计算 a + b * c，然后执行入栈操作，此时栈中的元素为 [ a + b * c ]
Step 6 : 继续读取，解下来遇到的是 d ，执行入栈操作，此时栈中的元素为 [ a + b * c | d ]
Step 7 : 继续读取，解下来遇到的是 e ，执行入栈操作，此时栈中的元素为 [ a + b * c | d | e ]
Step 8 : 继续读取，解下来遇到的是 * ，出栈两个元素，计算 d * e ，然后执行入栈操作，此时栈中的元素为 [ a + b * c | d * e ]
Step 9 : 继续读取，解下来遇到的是 f ，执行入栈操作，此时栈中的元素为 [ a + b * c | d * e | f ]
Step 10 : 继续读取，解下来遇到的是 + ，出栈两个元素，计算 d * e + f ，然后执行入栈操作，此时栈中的元素为 [ a + b * c | d * e + f ]
Step 11 : 继续读取，解下来遇到的是 g ，执行入栈操作，此时栈中的元素为 [ a + b * c | d * e + f | g ]
Step 12 : 继续读取，解下来遇到的是 * ，出栈两个元素，计算 ( d * e + f ) * g ，然后执行入栈操作，此时栈中的元素为 [ a + b * c | ( d * e + f ) * g ]
Step 13 : 继续读取，解下来遇到的是 + ，出栈两个元素，计算 a + b * c + ( d * e + f ) * g ，然后执行入栈操作，此时栈中的元素为 [ a + b * c + ( d * e + f ) * g ]
Step 14 : 继续读取，到达了末端，执行出栈操作，出栈的结果就是计算的结果 a + b * c + ( d * e + f ) * g
实现代码
class Program{ static List<Priority> priority = new List<Priority>() { new Priority() { level = 0 , symbal ="+" }, new Priority() { level = 0 , symbal ="-" }, new Priority() { level = 1 , symbal ="*" }, new Priority() { level = 1 , symbal ="/" }, new Priority() { level = 2 , symbal ="%" }, new Priority() { level = int.MaxValue , symbal ="(" }, new Priority() { level = int.MaxValue , symbal =")" } }; static void Main(string[] args) { //string expression = "a + b * c + ( d * e + f ) * g"; //string expression ="10 + 1 * 10 + ( 2 * 3 + 4 ) * 10"; // 120 //string expression ="1 + 2 + 3 "; string expression ="3 * ( ( 2 - 4 ) / ( 2 - 1 ) ) "; GenerateExpression(expression); Console.WriteLine(OutputStr); Console.WriteLine(CalculateValue()); } ///生成后缀表达式的栈 static StackForArray<Priority> symbalStack = new StackForArray<Priority>(); /// 输出字符串 static string OutputStr=string.Empty; /// 生成后缀表达式 static void GenerateExpression(string expression) { string[] symbals = expression.Split(' '); foreach(string symbal in symbals) { RecursionExpression(symbal); } while(true) { try { var popElement = symbalStack.Pop(); OutputStr += popElement.symbal +" "; } catch(Exception ex) { break; } } } // 计算表达式的值 static int CalculateValue() { StackForArray<int> valueStack = new StackForArray<int>(); string[] symbals = OutputStr.Split(new char[]{' '} ,StringSplitOptions.RemoveEmptyEntries); foreach(var symbal in symbals) { var temp = priority.Where(x=>x.symbal ==symbal).FirstOrDefault(); if(temp!=null) { var t = 0; var second = valueStack.Pop(); var first = valueStack.Pop(); switch (symbal) { case "*": t = first * second; break; case "/": t = first / second; break; case "+": t = first + second; break; case "-": t = first - second; break; default: throw new Exception(); } valueStack.Push(t); } else { valueStack.Push(int.Parse(symbal)); } } return valueStack.Pop(); } /// 递归表达式 static void RecursionExpression(string symbal) { var temp = priority.Where(x=>x.symbal == symbal).FirstOrDefault(); if(temp==null) { OutputStr+= symbal + " "; return; } var stackCount = symbalStack.count; if(stackCount==0 || temp.symbal =="(") { symbalStack.Push(temp); return; } if(temp.symbal ==")") { while(true) { var popElement = symbalStack.Pop(); OutputStr += popElement.symbal +" "; if(popElement.symbal=="(") { OutputStr=OutputStr.Substring(0,OutputStr.Length -2); break; } } return; } var topElement = symbalStack.GetTop(); if(temp.level > topElement.level || topElement.symbal=="(") { symbalStack.Push(temp); return; } if(temp.level <= topElement.level && topElement.symbal != "(") { var popElement= symbalStack.Pop(); OutputStr += popElement.symbal +" "; RecursionExpression(temp.symbal); return; } } } public class Priority { public string symbal { get; set; } public int level { get; set; } }}
