java框架支持兩種類型的容器：
- 為了存儲(chǔ)一個(gè)元素集合，簡(jiǎn)稱合集
- 為了存儲(chǔ)鍵/值對(duì)熏瞄，稱為映射表
1.集合
- Set用于存儲(chǔ)一組不重復(fù)的元素
- List用于存儲(chǔ)一個(gè)有序元素集合
- Stack用于存儲(chǔ)后進(jìn)先出方式處理的對(duì)象
- Queue用于存儲(chǔ)采用先進(jìn)先出方式處理的對(duì)象
-
Priority Queue用于存儲(chǔ)按照優(yōu)先級(jí)順序處理的對(duì)象
collection接口：
2.迭代器
Iterator是一種經(jīng)典的設(shè)計(jì)模式脚祟，用于在不需要暴露數(shù)據(jù)是如何保存在數(shù)據(jù)結(jié)構(gòu)的細(xì)節(jié)的情況下，來(lái)遍歷一個(gè)數(shù)據(jù)結(jié)構(gòu)强饮。
Collection接口繼承自Iterator接口,Iterator接口中Iterator()方法返回一個(gè)Iterator的實(shí)例由桌。
3.線性表 List
List接口繼承自Collection接口，定義了一個(gè)用于順序存儲(chǔ)元素的集合⌒心可以使用ArrayList（數(shù)組線性表）和LinkedList（鏈表）來(lái)創(chuàng)建一個(gè)線性表铭乾。
-
List接口通用方法
方法listIterator()會(huì)返回ListIterator的一個(gè)實(shí)例。ListIterator接口繼承了Iterator接口娃循，以增加對(duì)線性表的雙向遍歷能力炕檩。
-
數(shù)組線性表類ArrayList和鏈表類LinkedList
ArrayList和LinkedList是實(shí)現(xiàn)List接口的兩個(gè)具體類。
1）ArrayList
ArrayList用數(shù)組存儲(chǔ)元素捌斧，這個(gè)數(shù)組是動(dòng)態(tài)創(chuàng)建的笛质。如果元素個(gè)數(shù)超過了數(shù)組的容量，就創(chuàng)建一個(gè)更大的新數(shù)組捞蚂，并將當(dāng)前數(shù)組中所有元素都復(fù)制到新數(shù)組中妇押。
2）LinkedList
LinkedList在一個(gè)鏈表中存儲(chǔ)元素。
比較：
如果需要通過下標(biāo)隨機(jī)訪問元素姓迅，而不會(huì)在線性表起始末尾位置插入或刪除敲霍，使用ArrayList效率高。
如果需要在線性表起始末尾位置插入刪除元素丁存，選用LinkedList效率高肩杈。
public class text1_線性表 {
public static void main(String[] args ){
//ArrayList
List<Integer> arrayList=new ArrayList();
arrayList.add(1);
arrayList.add(2);
arrayList.add(3);
arrayList.add(0,10);
arrayList.add(3,30);
System.out.println(arrayList);
//linkedList
LinkedList<Object> linkedList=new LinkedList();
linkedList.add("red");
linkedList.add(1);
linkedList.add(2);
linkedList.add(3);
linkedList.addFirst("yellow");
linkedList.removeLast();
System.out.println(linkedList);
//從前向后遍歷
ListIterator listIterator=linkedList.listIterator();
while (listIterator.hasNext()){
System.out.print(listIterator.next()+" ");
}
System.out.println();
//從后向前遍歷
listIterator=linkedList.listIterator(linkedList.size());
while (listIterator.hasPrevious()){
System.out.print(listIterator.previous()+" ");
}
}
}
4.Collections類
Collections類包含了執(zhí)行合集和線性表中通用操作的靜態(tài)方法。
5.Vector和棧
-
Vector
Vector是AbstractList的子類柱嫌，Stack是Vector的子類锋恬。
Vector是同步的，如果不需要同步编丘，建議使用ArrayList效率高
-
stack類
6.隊(duì)列和優(yōu)先隊(duì)列
-
隊(duì)列（queue）是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)与学。元素被追加到隊(duì)列末尾，然后從隊(duì)列頭部出去嘉抓。
- 雙端隊(duì)列（Deque）索守，繼承自Queue接口，增加了如下方法：addFirst(e)抑片、removeFirst()卵佛、addLast(e)、removeLast()敞斋、getFirst()和getLast()這些從隊(duì)列兩端插入和刪除的方法截汪。
- 可以使用LinkedList創(chuàng)建一個(gè)隊(duì)列。
public class text2_隊(duì)列 {
public static void main(String[] args){
//LinkedList實(shí)現(xiàn)了List和Deque接口植捎，Deque接口繼承了Queue接口衙解，使用LinkedList()創(chuàng)建隊(duì)列
Queue queue=new LinkedList();
queue.offer("hello");
queue.offer("Queue");
queue.offer("Deque");
while (queue.size()>0){
System.out.print(queue.remove()+" ");
}
}
}
-
優(yōu)先隊(duì)列PriorityQueue
優(yōu)先隊(duì)列默認(rèn)字符串以升序從隊(duì)列刪除
圖片.png
7.示例：算數(shù)表達(dá)式求值
分析：
準(zhǔn)備兩個(gè)棧，一個(gè)用于準(zhǔn)備放符號(hào)operatorStack焰枢，一個(gè)用于準(zhǔn)備放數(shù)字operandStack蚓峦。
準(zhǔn)備：為得到的字符串表達(dá)式的()+-/左右兩邊添加空格舌剂，方便將多位數(shù)區(qū)分出來(lái)。以空格隔開暑椰。
1）如果遇到的是數(shù)字霍转，將其push到operandStack中
2）如果遇到的符號(hào)是+或-：
operatorStack不為空，并且棧頂元素是+-/一汽，循環(huán)pop得到操作符避消，同時(shí)operandStack彈出兩個(gè)操作數(shù)，將計(jì)算結(jié)果push進(jìn)operandStack角虫。直到 operatorStack為空
operatorStack為空沾谓，直接將操作符push進(jìn)operatorStack。
3）如果遇到的是或/戳鹅，棧頂元素是/，就彈出計(jì)算昏兆，循環(huán)直到operatorStack為空枫虏。
operatorStack為空，直接將操作符push進(jìn)operatorStack爬虱。
4）如果遇到的是（隶债，直接壓入符號(hào)棧；
如果遇到）跑筝，取出操作符計(jì)算死讹，直到棧頂元素是（，最后彈出（曲梗。
5）如果 operatorStack不為空赞警，就循環(huán)，彈出 operatorStack操作符虏两，彈出operandStack中兩個(gè)數(shù)據(jù)愧旦，計(jì)算結(jié)果push進(jìn)operandStack。
6）返回operandStack的值就是結(jié)果
public class text3_算數(shù)表達(dá)式求值 {
public static void main(String[] args){
System.out.println("輸入算數(shù)表達(dá)式");
Scanner input=new Scanner(System.in);
String caculate=input.nextLine();
try {
System.out.println(evaluateExpression(caculate));
}catch (Exception e){
System.out.println("Wrong expression");
}
}
private static Double evaluateExpression(String caculate) {
//定義了操作符的棧
Stack<Character> operatorStack=new Stack();
//定義了操作數(shù)的棧
Stack<Double> operandStack=new Stack();
//需要在所有符號(hào)前后加上空格定罢，來(lái)分割數(shù)字笤虫，多位數(shù)才能正確讀取
caculate=insertBlanks(caculate);
String[] tokens=caculate.split(" ");
for(String token:tokens){
//分割后token，第一個(gè)是空格祖凫，可能分割后是第一個(gè)是空串
if(token.length()==0)
continue;
//如果遇到的是+ -
if(token.charAt(0)=='+'||token.charAt(0)=='-'){
while(!operatorStack.isEmpty()&&(operatorStack.peek()=='+'||operatorStack.peek()=='-'||operatorStack.peek()=='*'||operatorStack.peek()=='/')){
processAnOperator(operandStack,operatorStack);
}
operatorStack.push(token.charAt(0));
}
//如果遇到的是* /
else if(token.charAt(0)=='*'||token.charAt(0)=='/'){
while (!operatorStack.isEmpty()&&(operatorStack.peek()=='*'||operatorStack.peek()=='/')){
processAnOperator(operandStack,operatorStack);
}
operatorStack.push(token.charAt(0));
}
//如果是（
else if(token.charAt(0)=='('){
operatorStack.push(token.charAt(0));
}
//如果是）
else if(token.charAt(0)==')'){
while (operatorStack.peek()!='('){
processAnOperator(operandStack,operatorStack);
}
operatorStack.pop();//把（彈出
}
//是數(shù)字
else{
operandStack.push(new Double(token));
}
}
while (!operatorStack.isEmpty()){
processAnOperator(operandStack,operatorStack);
}
//返回最后在數(shù)字棧內(nèi)的值就是結(jié)果
return operandStack.pop();
}
private static String insertBlanks(String caculate) {
String result="";
for(int i=0;i<caculate.length();i++)
{
if(caculate.charAt(i)=='('||caculate.charAt(i)==')'||caculate.charAt(i)=='+'||caculate.charAt(i)=='-'
||caculate.charAt(i)=='*'||caculate.charAt(i)=='/')
result+=" "+caculate.charAt(i)+" ";
else
result+=caculate.charAt(i);
}
return result;
}
private static void processAnOperator(Stack<Double> operandStack, Stack<Character> operatorStack) {
char op=operatorStack.pop();
double num2=operandStack.pop();
double num1=operandStack.pop();
switch (op){
case '+':operandStack.push(num1+num2);break;
case '-':operandStack.push(num1-num2);break;
case '*':operandStack.push(num1*num2);break;
case '/':operandStack.push(num1/num2);break;
}
}
}
