栈

定义栈是一种只能在顶端插入和删除的列表。顶端是指最后一个操作的元素，数组中指下标最大的元素，链表中指末尾的元素。所以栈是一种LIFO（后进先出）的数据结构。实现栈可以使用数组、链表两种方式实现。自己动手coding，可以学习怎么处理异常，还有一些其他细节。上一篇中分析到如果在表的末端插入和删除都是O(1)的时间复杂度。 栈的基本操作有：1.E push(E item);2.E pop();3.E peek();4.boolean empty();5.int search(Object o);6.int size() ;应用栈的常用在 1 代码编辑器检查语法错误；2 计算器实现；3 计算机函数递归调用。代码语法检查写代码过程中有”(“必定有”)”，有”[“必定有”]”。这些是平衡符号。实现这个功能的过程中用到栈。思路是这样的： 做一个空栈，读入字符一直到文件结尾。 如果字符是一个封闭符号（])}），则当栈空时报错。否则将栈元素弹出。如果弹出的符号不是对应的开放符号，则报错。 在文件结尾，如果栈非空则报错。 时间复杂度：线性的，与输入的字符串长度有关系。计算器应用例如写一个计算器实现：4.99*1.06+5.99+6.99*1.06，不同计算器给出的答案可能不同，可能是18.69或者19.37。在正确的计算过程中计算顺序是 01 4.99*1.06=A1； 02 A1+5.99=A1; 03 6.99*1.06=A2; 04 A1+A2=答案 这种操作的顺序书写出来：4.99 1.06 * 5.99 + 6.99 1.06 * +。这叫做后缀表达法或者逆波兰记法。4.99*1.06+5.99+6.99*1.06 这种表示方法叫做中缀表达式。如何从中缀到后缀？ 假设输入的字符串是表达式合法的，可以使用栈，实现中缀到后缀的转换。例如中缀表达式为：a+b*c+(d*e+f)*g。这里有两个站，一个是输出栈，一个是符号栈。 01 读到一个操作数，push到输出栈； 02 读到一个操作符，push到符号栈；如果符号是”)”，则弹出符号栈元素到输出栈，直到碰到”(“，”(“弹出，不进入输出栈。如果是其他操作符号（例如：+-*/），从符号栈中弹出元素直到发现优先级更低的元素为止。对于”(“,”)”要特殊对待。 03 读到输入的末尾，把符号栈所有元素弹出，放入输出栈。方法调用在计算机中，当从方法A执行一段，调用方法B，执行B之后，返回A继续执行。当然可能会嵌套多层方法调用。每一次方法跳出，都需要把当前执行状态记录到栈中。保存的信息称为活动记录。当方法调用太多的时候就会发生栈溢出的错误。这种保存是计算机主动帮我们做的。解决栈溢出，首先检查代码逻辑，是否忘记了基本情况判断；其次，如果真的是因为数据量太大，必须进行多次递归调用，则可以显示的使用栈，将递归改为递推，当然要损失的是代码的可读性。代码任务01 栈的数组实现 02 栈的链表实现 03 语法检查工具 04 计算器，中缀到后缀，后缀计算