ArrayList和LinkedList的实现方式
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: 空
计算表达式的值--Java版实现
接下来，我将要介绍一下我的小型计算器的实现，表达式的特征是包含+，-，*，/和（），并且数字是整数，可以是多位的。整个实现分为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
大功告成！
