ArrayList的底层实现是可以增长的数组，LinkedList的底层是使用了双链表。从底层实现来看，我们可以知道，ArrayList 获取元素的时间复杂度仅为常数，而 插入和 删除的时间复杂度都为线性时间复杂度O(n)。而LinkedList则刚好相反，因为底层是链表,所以 插入和 删除的时间复杂度为常数，而 获取元素的时间复杂度却是线性时间复杂度。
另外，ArrayList和LinkedList的contains和remove方法的时间复杂度都为线性时间复杂度O(n)，对于contains方法来说，ArrayList和linkedList都需要遍历操作来实现contains方法，所以时间复杂度都是线性的；对于remove操作，ArrayList删除后需要移动元素，所以时间复杂度是线性的，而LinkedList的remove操作虽然是常数时间的，但是查找到元素的时间复杂度是线性的，所以，对已LinkedList的remove操作来说也是线性时间复杂的。
本章用Java来是实现一个计算含有+，-，*，\和括号的表达式的值，包括的知识点有：
Java语言中栈Stack和Queue的使用中缀表达式转后缀表达式的技巧计算后缀表达式的值Java提供了栈的实现Stack对象，它继承了Vector类，底层实现是数组。Queue是一个Java队列接口，其中提供了队列必要的方法，而LinkedList实现了Queue接口，可以使用LinkedList来实现队列操作。例如：入队操作为add或insert方法，出队操作为 poll方法，获取队头的元素为peek方法。
中缀表达式是人们常用的算术表示方式，其标志是操作符处于操作数之间。而后缀表达式是操作符处于操作数之后，并且暗含的运算顺序，易于计算机进行计算。形象点的例子，例如1+2*3+(1+2)是中缀表达式，将其转换成后缀表达式为1, 2, 3, * , +, 1, 2, +, +。其转换过程如下：
输入：1
操作：将数字直接加入到结果队列
postfix(结果队列, 从队头到队尾)：1
opStack(操作符队列，从栈底到栈顶，)：空
输入：+
操作：因为opStack栈为空，所以将+号如操作符栈
postfix: 1
opStack: +
输入：2
操作：将数字直接加入结果队列
postfix: 1, 2
opStack: +
输入*
操作：因为*的计算优先级大于站定+号的优先级，所以入栈
postfix: 1,2
opStack: +,*
输入3
操作：数字直接入结果 队列
postfix: 1,2,3
opStack: +,*
输入+
操作：因为+号的优先级不大于栈顶的*，所以*弹栈并且放到结果队列中；此时栈顶的仍为+号，但是输入的+号的优先级不大于栈顶的+号，所以，栈顶的+号出栈；此时栈为空，所以当前的+号入栈
postfix: 1,2,3,*,+
opStack: +
输入(
操作：对于( 的输入来说，直接操作栈即可，也就是说( 在入栈前比任何操作符的优先级都大；而另一中特殊情况是如果栈顶元素是(, 那么只有）的输入才可以使其出栈，也就是或对于其他操作符来说，它们的优先级又比已经入栈的( 的优先级大。
postfix: 1,2,3,*,+
opStack: +,(
输入1
操作：直接加入结果队列
postfix: 1,2,3,*,+,1
opStack: +,(
输入+
操作：遇到栈顶为(, 所以直接+号入操作符栈
postfix: 1,2,3,*,+
opStack: +,(,+
输入2
操作：直接加入结果队列
postfix: 1,2,3,*,+,1,2
opStack: +,(,+
输入)
操作：对于)的输入，应该对操作符栈进行弹栈，直至遇到(, 弹栈才结束，这也就是说，)的在入栈前的优先级比其他操作的优先级都低。在假设表达式合法的前提下，不存在)处在栈顶的情况，)会和(一起出栈，但不会放入结果队列中。这一次，+号和(出栈，+号加入结果队列。
postfix:1,2,3,*,+,1,2,+
opStack:+
如果操作符栈不为空，全部弹出加入结果队列
postfix: 1,2,3,*,+,1,2,+,+
opStack: 空
接下来，我将要介绍一下我的小型计算器的实现，表达式的特征是包含+，-，*，/和（），并且数字是整数，可以是多位的。整个实现分为3大部分：
读取优先级列表中缀表达式转换成后缀表达式计算后缀表达式的值当然了，最难的部分是第二步，下面一一介绍。
优先级列表我是用一个文件来存储操作符和对应的优先级，每行存储一个，采用操作符-空格-优先级的方式，如下：+ 1
完整的优先级列表如下
+ 1 - 1 * 2 / 2使用HashMap保存优先级列表，这里涉及了如何将一个char转化成一个int值的过程，我们使用了先将char转化成String，然后将String转化成Integer的方法
//读入优先级文件 Map<Character,Integer> priority=new HashMap<Character,Integer>(); BufferedReader breader=new BufferedReader(new FileReader("priority.txt")); String pline=breader.readLine(); while(pline!=null) { char[] plineChar=pline.toCharArray(); priority.put(plineChar[0], Integer.parseInt(String.valueOf(plineChar[2]))); pline=breader.readLine(); } System.out.println("优先级："+priority); breader.close(); 中缀表达式转后缀表达式因为数字是多位的，所以用了一个栈来numStack来记录数，并且使用一个静态方法拼接成一个整数。opStack< Character>是用来存储操作符的，postfix是用来存储转换好的后缀表达式的。整个过程如下：
//numStack用于存储存储操作数 Stack<Integer>numStack=new Stack<>(); //opStack用于存储操作符 Stack<Character>opStack=new Stack<>(); //postfix存储后缀表达式的， //其中有Integer和Character类型，所以用Object作为泛型参数 Queue<Object>postfix=new LinkedList<>(); Scanner scanner=new Scanner(System.in); String myExp=scanner.nextLine(); while(myExp!=null && !"end".equalsIgnoreCase(myExp)) { char[] charExp=myExp.toCharArray(); //System.out.println(charExp); for(char charitem:charExp) { switch (charitem) { case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9': case '0': numStack.push(Integer.parseInt(String.valueOf(charitem))); break; case '+': case '-': case '*': case '/': case '(':case ')': //在遇到操作符号之前弹出数字拼接 pushNumber2Result(numStack, postfix); if(opStack.isEmpty()) { opStack.push(charitem); }else { //对右括号特殊处理 if(charitem==')'&&!opStack.isEmpty()) { while(opStack.peek()!='(') { postfix.add(opStack.pop()); } //弹出左括号 opStack.pop(); }else if(charitem=='(') { opStack.push(charitem); }else { //对非括号的符号输入 //如果碰到左括号操作符号入栈 if(opStack.peek()=='(') { opStack.push(charitem); }else if(priority.get(charitem)>priority.get(opStack.peek())) { //如果下一个操作符的优先级大于栈顶的优先级， //压栈,此时栈顶一定有操作符 opStack.push(charitem); }else { //否则，出栈直至当前操作符入栈 //注意当栈不空的情况下比较 while(!opStack.isEmpty() && priority.get(charitem) <=priority.get(opStack.peek())) { postfix.add(opStack.pop()); } opStack.push(charitem); } } } } } pushNumber2Result(numStack, postfix); //注意剩余的操作符可能有多个 while(!opStack.isEmpty()) { postfix.add(opStack.pop()); } System.out.println(postfix);其中，pushNumber2Result函数的定义如下：
public static void pushNumber2Result(Stack<Integer>numStack, Queue<Object>result) { int num=0; int base=1; while(!numStack.isEmpty()) { num=num+numStack.pop()*base; base=base*10; } //注意如果num!=0才添加进去 if(num!=0) result.add(num); }几个值得注意的地方：
栈的循环操作注意判空操作数的添加如果是0的话不应该添加
利用后缀表达式 计算表达式的值 numStack.clear(); while(!postfix.isEmpty()) { Object head=postfix.poll(); if(head instanceof Integer) { numStack.push((Integer)head); }else if(head instanceof Character){ Character op=(Character) head; int num2=numStack.pop(); int num1=numStack.pop(); switch(op) { case '+': numStack.push(num1+num2); break; case '-': numStack.push(num1-num2); break; case '*': numStack.push(num1*num2); break; case '/': numStack.push(num1/num2); break; } } } if(numStack.size()==1) { System.out.println("result:"+numStack.pop()); }else { System.out.println("计算出错！"); } 测试结果 优先级：{*=2, +=1, -=1, /=2} 1+2*3+(1*2) [1, 2, 3, *, +, 1, 2, *, +] result:9 1+2*4-5/(1+1) [1, 2, 4, *, +, 5, 1, 1, +, /, -] result:7大功告成！
