java线性表增加所有_Java 线性表、队列和有限队列

ゝ一世哀愁。 2022-11-07 11:32 157阅读 0赞

Java合集框架支持一下两种类型的容器：一种是为了存储一个元素合集，简称为合集(collection)

另一种是为了存储键/值对，称为映射表(map)

集合：Set用于存储一组不重复的元素

List用于存储一个有序元素合集

Stack用于存储采用后进先出方式处理的对象

Queue用于存储采用先进先出方式处理的对象

PriorityQueue用于存储按照优先级顺序处理的对象

collectionadd(o: E): boolean                               //添加一个元素

addAll(c: Collection extends E>): boolean

clear(): void                                    //删除所有元素

contains(o: Object): boolean                     //判断合集是否包含元素o

remove(o: Object): boolean                       //从该合集中移除元素o

retainAll(c: Collection extends E>): boolean   //保留同时位于c和该合集中的元素

size(): int                                      //返回该合集中的元素数目

......

迭代器

每个合集都是可迭代的(Iterable)。可以获得集合的Iterator对象来遍历集合中的所有元素。Iterator是一种经典的设计模式，用于在不需要暴露数据结构具体细节的情况下，来遍历一个数据结构。

Collection接口继承自Iterable接口，Iterable接口中定义了iterator方法返回Iterator接口(迭代器)，Iterator接口为遍历各种类型的合集中的元素提供了一种统一的方法。迭代器中remove()方法和next()一起配合使用，迭代器的初始指针指向第一个元素之前，需要先用next()，再用remove()。

使用foreach方法其实就是对iterator方法的封装，通过反编译可以看到。import java.util.ArrayList;

import java.util.Collection;

import java.util.Iterator;

public class TestIterator \{

public static void main(String\[\] args) \{

Collection collection = new ArrayList<>();

collection.add("a");

collection.add("b");

collection.add("c");

//iterator头指针指向集合头元素前面，hasNext判断有没有下一个元素，但是指针不会变

//next方法移向下一个元素，并且返回指针移动后返回的值

Iterator iterator = collection.iterator();

//注意collection接口中提供的remove方法和iterator中的remove方法不能同时出现，会产生并发修改错误

System.out.println(collection);

//foreach反编译后其实是对iterator方法的包装

for(String content : collection) \{

System.out.println(content);

线性表

List接口继承自Collection接口，定义了一个用于顺序存储元素的合集。可以使用他的两个具体类ArrayList或者LinkedList来创建一个线性表。

List接口定义了一个允许重复的有序合集。List接口增加了面向位置的操作，并且增加了一个能够双向遍历线性表的新线性表迭代器add(index: int, element: Object): boolean          //在指定的索引处增加一个新的元素

//备注：若果原来的位置有元素，那么将其及后面的所有元素索引加1

get(intdex: int): E                                //返回指定索引位置的元素

indexOf(element: Object): int                      //返回第一个匹配元素的索引

listIterator(): ListIterator                    //返回针对该线性表元素的迭代器

listIterator(startIndex: int): ListIterator     //返回从指定为止开始的迭代器

//此方法可以用来逆序迭代

remove(index: int): E                              //移除指定索引位置处的元素

set(intdex: int, element: Object): Object          //设置指定索引处的元素

ListIterator接口继承了Iterator接口，以增加对线性表的双向遍历能力。add(element: E): void                              //添加一个指定元素到线性表中

hasPrevious(): boolean                             //逆向遍历时如果当前元素之前还有元素返回true

next(): E                                          //返回下一个元素

nextIndex(): int                                   //返回下一个元素的索引

previous(): E                                      //返回前一个元素

previousIndex(): int                               //返回前一个元素的索引

set(element: E): void                              //使用指定的元素替换previous或next方法返回的最后一个元素ArrayList用数组存储元素，这个数组是动态创建的，如果元素个数超过了数组的容量，就创建一个更大的数组，并将当前数组中所有的元素都复制到新的数组当中。LinkedList在一个链表中存储元素。

要选用两种类中的哪一个依赖于特定的需求。如果需要下标随机访问而不会在线性表的起始位置插入或删除元素，那么ArrayList效率高，反之就用LinkedList。向ArrayList中添加元素时，其容量会自动增大。ArrayList不能自动减小，可以使用方法trimToSize()将数组容量减小到线性表的大小。ArrayList()                                  //使用默认的出事容量构建一个空线性表ArrayList(c: Collection extends E>)        //从已存在的合集中创建一个线性表ArrayList(initialCapacity: int)              //创建一个指定初始容量的空数组线性表trimToSize(): void                           //将ArrayList实例容量裁剪到当前大小LinkedList()

LinkedList(c: Collection extends E>)

addFist(element: E): void                     //添加元素到线性表头部addLast(element: E): void                     //添加元素到线性表尾部getFirst(): E                                 //返回该线性表第一个元素getLast(): E                                  //返回该线性表最后一个元素removeFirst(): E                              //从线性表中返回并删除第一个元素RemoveLast(): E                               //从线性表中返回并删除最后一个元素

Comparator接口

Comparable接口定义了compareTo方法，用于比较实现了Comparable接口的同一个类的两个元素，比如String、Date、Calendar、BigInteger、BigDecimal以及所有基本类型的数字包装类。public int compara(T element1,T element2)//如果element1小于element2，就返回一个负值//如果element1大于element2，就返回一个正值//若两者相等，则返回0

向量类和栈类

在Java API中，Vector是AbstractList的子类，Stack是Vector的子类。除了访问和修改向量的同步方法之外，Vector类与ArrayList是一样的，Vector类被广泛用在Java的遗留代码中。

栈类Stack是作为Vector类的扩展来实现的java.util.Vectorjava.util.Stack

Stack()                                            //创建一个空的栈

empty(): boolean                                   //若为空则返回true

peek(): E                                          //返回栈顶元素

pop(): E                                           //返回并移除栈顶元素

push(o: E): E                                      //压入一个元素

search(o: Object): int                             //返回指定元素的索引

队列和优先队列

队列(queue)是一种先进先出的数据结构。优先队列(priority queue)中，元素被赋予优先级，最高优先级的元素先被删除。java.util.Collection

java.util.Queueadd(element: E): boolean              //插入一个元素到队列中