ArrayList和LinkedList的實(shí)現(xiàn)方式
ArrayList的底層實(shí)現(xiàn)是可以增長(zhǎng)的數(shù)組纳鼎，LinkedList的底層是使用了雙鏈表旨枯。從底層實(shí)現(xiàn)來看漏麦，我們可以知道游添，ArrayList 獲取元素的時(shí)間復(fù)雜度僅為常數(shù)，而 插入和 刪除的時(shí)間復(fù)雜度都為線性時(shí)間復(fù)雜度O(n)秉馏。而LinkedList則剛好相反耙旦，因?yàn)榈讓邮擎湵?所以 插入和 刪除的時(shí)間復(fù)雜度為常數(shù)，而 獲取元素的時(shí)間復(fù)雜度卻是線性時(shí)間復(fù)雜度萝究。
另外免都，ArrayList和LinkedList的contains和remove方法的時(shí)間復(fù)雜度都為線性時(shí)間復(fù)雜度O(n)，對(duì)于contains方法來說帆竹，ArrayList和linkedList都需要遍歷操作來實(shí)現(xiàn)contains方法绕娘，所以時(shí)間復(fù)雜度都是線性的；對(duì)于remove操作栽连，ArrayList刪除后需要移動(dòng)元素险领，所以時(shí)間復(fù)雜度是線性的，而LinkedList的remove操作雖然是常數(shù)時(shí)間的秒紧，但是查找到元素的時(shí)間復(fù)雜度是線性的绢陌，所以，對(duì)已LinkedList的remove操作來說也是線性時(shí)間復(fù)雜的熔恢。
棧的運(yùn)用--計(jì)算表達(dá)式的值
本章用Java來是實(shí)現(xiàn)一個(gè)計(jì)算含有+脐湾，-，*叙淌，\和括號(hào)的表達(dá)式的值秤掌，包括的知識(shí)點(diǎn)有：
- Java語言中棧Stack和Queue的使用
- 中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式的技巧
- 計(jì)算后綴表達(dá)式的值
Java提供了棧的實(shí)現(xiàn)Stack對(duì)象愁铺，它繼承了Vector類，底層實(shí)現(xiàn)是數(shù)組闻鉴。Queue是一個(gè)Java隊(duì)列接口茵乱，其中提供了隊(duì)列必要的方法，而LinkedList實(shí)現(xiàn)了Queue接口椒拗，可以使用LinkedList來實(shí)現(xiàn)隊(duì)列操作似将。例如：入隊(duì)操作為add或insert方法，出隊(duì)操作為 poll方法蚀苛，獲取隊(duì)頭的元素為peek方法在验。
中綴表達(dá)式是人們常用的算術(shù)表示方式，其標(biāo)志是操作符處于操作數(shù)之間堵未。而后綴表達(dá)式是操作符處于操作數(shù)之后腋舌，并且暗含的運(yùn)算順序，易于計(jì)算機(jī)進(jìn)行計(jì)算渗蟹。形象點(diǎn)的例子块饺，例如1+2*3+(1+2)是中綴表達(dá)式，將其轉(zhuǎn)換成后綴表達(dá)式為1, 2, 3, * , +, 1, 2, +, +雌芽。其轉(zhuǎn)換過程如下：
輸入：1
操作：將數(shù)字直接加入到結(jié)果隊(duì)列
postfix(結(jié)果隊(duì)列, 從隊(duì)頭到隊(duì)尾)：1
opStack(操作符隊(duì)列授艰，從棧底到棧頂，)：空
輸入：+
操作：因?yàn)閛pStack棧為空世落，所以將+號(hào)如操作符棧
postfix: 1
opStack: +
輸入：2
操作：將數(shù)字直接加入結(jié)果隊(duì)列
postfix: 1, 2
opStack: +
輸入*
操作：因?yàn)?的計(jì)算優(yōu)先級(jí)大于站定+號(hào)的優(yōu)先級(jí)淮腾，所以入棧
postfix: 1,2
opStack: +,*
輸入3
操作：數(shù)字直接入結(jié)果 隊(duì)列
postfix: 1,2,3
opStack: +,*
輸入+
操作：因?yàn)?號(hào)的優(yōu)先級(jí)不大于棧頂?shù)?，所以*彈棧并且放到結(jié)果隊(duì)列中屉佳；此時(shí)棧頂?shù)娜詾?號(hào)谷朝，但是輸入的+號(hào)的優(yōu)先級(jí)不大于棧頂?shù)?號(hào)，所以武花，棧頂?shù)?號(hào)出棧圆凰；此時(shí)棧為空，所以當(dāng)前的+號(hào)入棧
postfix: 1,2,3,*,+
opStack: +
輸入(
操作：對(duì)于( 的輸入來說体箕，直接操作棧即可专钉，也就是說( 在入棧前比任何操作符的優(yōu)先級(jí)都大；而另一中特殊情況是如果棧頂元素是(, 那么只有）的輸入才可以使其出棧干旁，也就是或?qū)τ谄渌僮鞣麃碚f驶沼，它們的優(yōu)先級(jí)又比已經(jīng)入棧的( 的優(yōu)先級(jí)大。
postfix: 1,2,3,*,+
opStack: +,(
輸入1
操作：直接加入結(jié)果隊(duì)列
postfix: 1,2,3,*,+,1
opStack: +,(
輸入+
操作：遇到棧頂為(, 所以直接+號(hào)入操作符棧
postfix: 1,2,3,*,+
opStack: +,(,+
輸入2
操作：直接加入結(jié)果隊(duì)列
postfix: 1,2,3,*,+,1,2
opStack: +,(,+
輸入)
操作：對(duì)于)的輸入争群，應(yīng)該對(duì)操作符棧進(jìn)行彈棧，直至遇到(, 彈棧才結(jié)束大年，這也就是說换薄，)的在入棧前的優(yōu)先級(jí)比其他操作的優(yōu)先級(jí)都低玉雾。在假設(shè)表達(dá)式合法的前提下，不存在)處在棧頂?shù)那闆r轻要，)會(huì)和(一起出棧复旬，但不會(huì)放入結(jié)果隊(duì)列中。這一次冲泥，+號(hào)和(出棧驹碍，+號(hào)加入結(jié)果隊(duì)列。
postfix:1,2,3,*,+,1,2,+
opStack:+
如果操作符棧不為空凡恍，全部彈出加入結(jié)果隊(duì)列
postfix: 1,2,3,*,+,1,2,+,+
opStack: 空
計(jì)算表達(dá)式的值--Java版實(shí)現(xiàn)
接下來志秃，我將要介紹一下我的小型計(jì)算器的實(shí)現(xiàn)，表達(dá)式的特征是包含+嚼酝，-浮还，*，/和（）闽巩，并且數(shù)字是整數(shù)钧舌，可以是多位的。整個(gè)實(shí)現(xiàn)分為3大部分：
- 讀取優(yōu)先級(jí)列表
- 中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式
- 計(jì)算后綴表達(dá)式的值
當(dāng)然了涎跨，最難的部分是第二步洼冻，下面一一介紹。
- 優(yōu)先級(jí)列表
我是用一個(gè)文件來存儲(chǔ)操作符和對(duì)應(yīng)的優(yōu)先級(jí)隅很，每行存儲(chǔ)一個(gè)撞牢，采用操作符-空格-優(yōu)先級(jí)的方式，如下：+ 1
完整的優(yōu)先級(jí)列表如下
+ 1
- 1
* 2
/ 2
使用HashMap保存優(yōu)先級(jí)列表外构，這里涉及了如何將一個(gè)char轉(zhuǎn)化成一個(gè)int值的過程普泡，我們使用了先將char轉(zhuǎn)化成String，然后將String轉(zhuǎn)化成Integer的方法
//讀入優(yōu)先級(jí)文件
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("優(yōu)先級(jí)："+priority);
breader.close();
- 中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式
因?yàn)閿?shù)字是多位的审编，所以用了一個(gè)棧來numStack來記錄數(shù)撼班，并且使用一個(gè)靜態(tài)方法拼接成一個(gè)整數(shù)。opStack< Character>是用來存儲(chǔ)操作符的垒酬，postfix是用來存儲(chǔ)轉(zhuǎn)換好的后綴表達(dá)式的砰嘁。整個(gè)過程如下：
//numStack用于存儲(chǔ)存儲(chǔ)操作數(shù)
Stack<Integer>numStack=new Stack<>();
//opStack用于存儲(chǔ)操作符
Stack<Character>opStack=new Stack<>();
//postfix存儲(chǔ)后綴表達(dá)式的，
//其中有Integer和Character類型勘究，所以用Object作為泛型參數(shù)
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 ')':
//在遇到操作符號(hào)之前彈出數(shù)字拼接
pushNumber2Result(numStack, postfix);
if(opStack.isEmpty()) {
opStack.push(charitem);
}else {
//對(duì)右括號(hào)特殊處理
if(charitem==')'&&!opStack.isEmpty()) {
while(opStack.peek()!='(') {
postfix.add(opStack.pop());
}
//彈出左括號(hào)
opStack.pop();
}else if(charitem=='(') {
opStack.push(charitem);
}else {
//對(duì)非括號(hào)的符號(hào)輸入
//如果碰到左括號(hào)操作符號(hào)入棧
if(opStack.peek()=='(') {
opStack.push(charitem);
}else if(priority.get(charitem)>priority.get(opStack.peek())) {
//如果下一個(gè)操作符的優(yōu)先級(jí)大于棧頂?shù)膬?yōu)先級(jí)矮湘，
//壓棧,此時(shí)棧頂一定有操作符
opStack.push(charitem);
}else {
//否則，出棧直至當(dāng)前操作符入棧
//注意當(dāng)棧不空的情況下比較
while(!opStack.isEmpty() && priority.get(charitem) <=priority.get(opStack.peek())) {
postfix.add(opStack.pop());
}
opStack.push(charitem);
}
}
}
}
}
pushNumber2Result(numStack, postfix);
//注意剩余的操作符可能有多個(gè)
while(!opStack.isEmpty()) {
postfix.add(opStack.pop());
}
System.out.println(postfix);
其中口糕，pushNumber2Result函數(shù)的定義如下：
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才添加進(jìn)去
if(num!=0)
result.add(num);
}
幾個(gè)值得注意的地方：
- 棧的循環(huán)操作注意判空
- 操作數(shù)的添加如果是0的話不應(yīng)該添加
- 利用后綴表達(dá)式 計(jì)算表達(dá)式的值
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("計(jì)算出錯(cuò)缅阳！");
}
- 測(cè)試結(jié)果
優(yōu)先級(jí)：{*=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
大功告成！
