栈的简单介绍

    栈就像是一摞放在一起的碟子，都是从下往上一个一个的放，取得时候从上往下一个一个的拿。实际上，栈可以用数组来实现叫顺序栈，如果用链表来实现，叫链式栈。

① 用数组来实现一个栈：

②用链表来尝试：

栈的实际应用

①比较经典的一个应用场景就是函数调用栈：

    如下，操作系统为每个线程分配了一块独立的内存空间，这块内存被组织成“栈”结构，用来储存函数调用的临时变量，每进入一个函数，就会把一个变量作为一个栈帧入栈，当被调用函数执行完成，就会将这个函数出栈。

②栈在表达式求值中的应用

    比如说一个只包含加减乘除的算法：3+5*8-6。对于这个运算画成图就如下：

    从左到右开始遍历表达式，如果遇到数字，就把他直接压入数字操作栈，当遇到运算符，就与运算符的栈顶元素作比较，如果比栈顶运算符的优先级高，就把他放到栈中，如果比栈顶运算符优先级低或相同，从运算符栈中取栈顶运算符，从操作数栈的栈顶取2个操作数，然后进行计算，再把计算完的结果压入操作数栈，继续比较。

（本文是个人听课笔记，不少东西摘取于王争老师的原文，原文链接http://gk.link/a/10aMZ）