java框架支持两种类型的容器：
- 为了存储一个元素集合，简称合集
- 为了存储键/值对，称为映射表
1.集合
- Set用于存储一组不重复的元素
- List用于存储一个有序元素集合
- Stack用于存储后进先出方式处理的对象
- Queue用于存储采用先进先出方式处理的对象
-
Priority Queue用于存储按照优先级顺序处理的对象
collection接口：
2.迭代器
Iterator是一种经典的设计模式，用于在不需要暴露数据是如何保存在数据结构的细节的情况下，来遍历一个数据结构。
Collection接口继承自Iterator接口,Iterator接口中Iterator()方法返回一个Iterator的实例。
3.线性表 List
List接口继承自Collection接口，定义了一个用于顺序存储元素的集合。可以使用ArrayList（数组线性表）和LinkedList（链表）来创建一个线性表。
-
List接口通用方法
方法listIterator()会返回ListIterator的一个实例。ListIterator接口继承了Iterator接口，以增加对线性表的双向遍历能力。
-
数组线性表类ArrayList和链表类LinkedList
ArrayList和LinkedList是实现List接口的两个具体类。
1）ArrayList
ArrayList用数组存储元素，这个数组是动态创建的。如果元素个数超过了数组的容量，就创建一个更大的新数组，并将当前数组中所有元素都复制到新数组中。
2）LinkedList
LinkedList在一个链表中存储元素。
比较：
如果需要通过下标随机访问元素，而不会在线性表起始末尾位置插入或删除，使用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类包含了执行合集和线性表中通用操作的静态方法。
5.Vector和栈
-
Vector
Vector是AbstractList的子类，Stack是Vector的子类。
Vector是同步的，如果不需要同步，建议使用ArrayList效率高
-
stack类
6.队列和优先队列
-
队列（queue）是一种先进先出的数据结构。元素被追加到队列末尾，然后从队列头部出去。
- 双端队列（Deque），继承自Queue接口，增加了如下方法：addFirst(e)、removeFirst()、addLast(e)、removeLast()、getFirst()和getLast()这些从队列两端插入和删除的方法。
- 可以使用LinkedList创建一个队列。
public class text2_队列 {
public static void main(String[] args){
//LinkedList实现了List和Deque接口，Deque接口继承了Queue接口，使用LinkedList()创建队列
Queue queue=new LinkedList();
queue.offer("hello");
queue.offer("Queue");
queue.offer("Deque");
while (queue.size()>0){
System.out.print(queue.remove()+" ");
}
}
}
-
优先队列PriorityQueue
优先队列默认字符串以升序从队列删除
图片.png
7.示例：算数表达式求值
分析：
准备两个栈，一个用于准备放符号operatorStack，一个用于准备放数字operandStack。
准备：为得到的字符串表达式的()+-/左右两边添加空格，方便将多位数区分出来。以空格隔开。
1）如果遇到的是数字，将其push到operandStack中
2）如果遇到的符号是+或-：
operatorStack不为空，并且栈顶元素是+-/，循环pop得到操作符，同时operandStack弹出两个操作数，将计算结果push进operandStack。直到 operatorStack为空
operatorStack为空，直接将操作符push进operatorStack。
3）如果遇到的是或/，栈顶元素是/，就弹出计算，循环直到operatorStack为空。
operatorStack为空，直接将操作符push进operatorStack。
4）如果遇到的是（，直接压入符号栈；
如果遇到），取出操作符计算，直到栈顶元素是（，最后弹出（。
5）如果 operatorStack不为空，就循环，弹出 operatorStack操作符，弹出operandStack中两个数据，计算结果push进operandStack。
6）返回operandStack的值就是结果
public class text3_算数表达式求值 {
public static void main(String[] args){
System.out.println("输入算数表达式");
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();
//定义了操作数的栈
Stack<Double> operandStack=new Stack();
//需要在所有符号前后加上空格，来分割数字，多位数才能正确读取
caculate=insertBlanks(caculate);
String[] tokens=caculate.split(" ");
for(String token:tokens){
//分割后token，第一个是空格，可能分割后是第一个是空串
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();//把（弹出
}
//是数字
else{
operandStack.push(new Double(token));
}
}
while (!operatorStack.isEmpty()){
processAnOperator(operandStack,operatorStack);
}
//返回最后在数字栈內的值就是结果
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;
}
}
}
