Java数据结构基础——线性表、栈、队列和优先队列

亦凉 2022-05-20 07:35 195阅读 0赞

### 文章目录 ###

*   *  1. 引言
     *  2. 合集
     *  3. 迭代器
     *  4. 线性表
     *   *  4.1 List接口中的通用方法
         *  4.2 数组线性表类ArrayList和链表类LinkedList
     *  5. Comparator接口
     *  6. 线性表和合集的静态方法
     *  7. 向量类和栈类
     *  8. 队列和优先队列
     *   *  8.1 双端队列Deque和链表LinkedList
     *  9. 总结

## 1. 引言 ##

为一个特定的任务选择最好的数据结构和算法是开发高性能软件的一个关键。在面向对象思想里，**一种数据结构也被认为是一个容器(container)或者容器对象(container object) ,他是一个能存储其他对象的对象**，这里的其他对象常称为数据或者元素。  
Java提供了很多能有效地组织和操作数据的数据结构。这些数据结构通常称为Java合集框架。(Java Collections Framework)。

## 2. 合集 ##

Java合集框架支持一下两种类型的容器：

*  一种是为了存储一个元素合集，简称为合集(collection)
 *  另一种是为了存储键/值对，称为映射表(map)

本篇主要将精力放在集合上。

*  Set用于存储一组不重复的元素
 *  List用于存储一个有序元素合集
 *  Stack用于存储采用后进先出方式处理的对象
 *  Queue用于存储采用先进先出方式处理的对象
 *  PriorityQueue用于存储按照优先级顺序处理的对象  
    ![collection合集框架][collection]

> <interface> java.lang.Iterable<E>

hasNext(): boolean
    next(): E
    remove(): void              //移除使用next方法获取的上一个元素

⇧

> <interfact>java.util.Collection<E>

add(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                                      //返回该合集中的元素数目
    ......

## 3. 迭代器 ##

每个合集都是可迭代的(Iterable)。可以获得集合的Iterator对象来遍历集合中的所有元素。Iterator是一种经典的设计模式，用于在不需要暴露数据结构具体细节的情况下，来遍历一个数据结构。  
Collection接口继承自**Iterable接口**，Iterable接口中定义了**iterator方法**返回**Iterator接口**（迭代器），Iterator接口为遍历各种类型的合集中的元素提供了一种统一的方法。

注意：

*  迭代器中remove()方法和next()一起配合使用，迭代器的初始指针指向第一个元素之前，需要先用next()，再用remove()。
 *  使用foreach方法其实就是对iterator方法的封装，通过反编译可以看到。

package collection;
    import java.util.ArrayList;
    import java.util.Collection;
    import java.util.Iterator;
    
    public class TestIterator {
      public static void main(String[] args) {
        Collection<String> collection = new ArrayList<>();
        collection.add("a");
        collection.add("b");
        collection.add("c");
        
        //iterator头指针指向集合头元素前面，hasNext判断有没有下一个元素，但是指针不会变
        //next方法移向下一个元素，并且返回指针移动后返回的值
        Iterator<String> iterator = collection.iterator();
        //注意collection接口中提供的remove方法和iterator中的remove方法不能同时出现，会产生并发修改错误
        System.out.println(collection);
        //foreach反编译后其实是对iterator方法的包装
        for(String content : collection) {
          System.out.println(content);
        } 
      }
    }

反编译后的代码：

package collection;
    
    import java.util.ArrayList;
    import java.util.Iterator;
    
    public class TestIterator {
    	public static void main(String[] args) {
    		ArrayList collection = new ArrayList();
    		collection.add("a");
    		collection.add("b");
    		collection.add("c");
    		Iterator iterator = collection.iterator();
    		System.out.println(collection);
    
                    //很明显的发现此处是用iterator包装的
    		Iterator arg3 = collection.iterator();
    
    		while (arg3.hasNext()) {
    			String content = (String) arg3.next();
    			System.out.println(content);
    		}
    
    	}
    }

## 4. 线性表 ##

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

### 4.1 List接口中的通用方法 ###

List接口定义了一个允许重复的有序合集。List接口增加了面向位置的操作，并且增加了一个能够双向遍历线性表的新线性表迭代器。

> <interface>java.util.List<E>

add(index: int, element: Object): boolean          //在指定的索引处增加一个新的元素
    //备注：若果原来的位置有元素，那么将其及后面的所有元素索引加1
    get(intdex: int): E                                //返回指定索引位置的元素
    indexOf(element: Object): int                      //返回第一个匹配元素的索引
    listIterator(): ListIterator<E>                    //返回针对该线性表元素的迭代器
    listIterator(startIndex: int): ListIterator<E>     //返回从指定为止开始的迭代器
                                                       //此方法可以用来逆序迭代
    remove(index: int): E                              //移除指定索引位置处的元素
    set(intdex: int, element: Object): Object          //设置指定索引处的元素

ListIterator接口继承了Iterator接口，以增加对线性表的双向遍历能力。

> <interface> java.util.ListIterator<E>

add(element: E): void                              //添加一个指定元素到线性表中
    hasPrevious(): boolean                             //逆向遍历时如果当前元素之前还有元素返回true
    next(): E                                          //返回下一个元素
    nextIndex(): int                                   //返回下一个元素的索引
    previous(): E                                      //返回前一个元素
    previousIndex(): int                               //返回前一个元素的索引
    set(element: E): void                              //使用指定的元素替换previous或next方法返回的最后一个元素

### 4.2 数组线性表类ArrayList和链表类LinkedList ###

ArrayList用数组存储元素，这个数组是动态创建的，如果元素个数超过了数组的容量，就创建一个更大的数组，并将当前数组中所有的元素都复制到新的数组当中。LinkedList在一个链表中存储元素。  
**要选用两种类中的哪一个依赖于特定的需求**。如果需要下标随机访问而不会在线性表的起始位置插入或删除元素，那么ArrayList效率高，反之就用LinkedList。向ArrayList中添加元素时，其容量会自动增大。ArrayList不能自动减小，可以使用方法trimToSize()将数组容量减小到线性表的大小。

> java.util.AbstractList<E>

⇧

> java.util.ArrayList<E>

ArrayList()                                  //使用默认的出事容量构建一个空线性表
    ArrayList(c: Collection<? extends E>)        //从已存在的合集中创建一个线性表
    ArrayList(initialCapacity: int)              //创建一个指定初始容量的空数组线性表
    trimToSize(): void                           //将ArrayList实例容量裁剪到当前大小

LinkedList除了实现List接口外，这个类还提供从线性表两端读取、插入和删除元素的方法。

> java.util.AbstractSequentialList<E>

⇧

> java.util.LinkedList<E>

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

Java提供了静态的asList方法，将数组转为线性表：

List<String> list1 = Arrays.asList("red","green","blue");

## 5. Comparator接口 ##

**Comparable接口**定义了compareTo方法，用于比较实现了Comparable接口的同一个类的两个元素，比如String、Date、Calendar、BigInteger、BigDecimal以及所有基本类型的数字包装类。  
如果元素类没有实现Comparable接口，可以定义一个比较器(comparator)，**Comparator接口实现类**可以用于比较没有实现Comparable的类的对象。即实现java.util.Comparator<T>接口类并重写compara方法。

> public int compara(T element1,T element2)

## 6. 线性表和合集的静态方法 ##

**Collections类**包含了执行合集和线性表中通用操作的静态方法

## 7. 向量类和栈类 ##

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

> java.util.Vector<E>

⇧

> java.util.Stack<E>

Stack()                                            //创建一个空的栈
    empty(): boolean                                   //若为空则返回true
    peek(): E                                          //返回栈顶元素
    pop(): E                                           //返回并移除栈顶元素
    push(o: E): E                                      //压入一个元素
    search(o: Object): int                             //返回指定元素的索引

## 8. 队列和优先队列 ##

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

> <interace>java.util.Collection<E>

⇧

> <interface>java.util.Queue<E>

add(element: E): boolean              //插入一个元素到队列中
    offer(element: E): boolean            //插入一个元素到队列中，在大部分情况下两者是相同的，但是在有容量限制的queue中，当队列已满时，add方法抛出错误，而offer方法返回false
    poll(): E                                         //获取并移除队列头元素，如果空返回null
    remove(): E                                       //获取并移除队列头元素，如果空抛出异常
    peek(): E                                         //获取但不移除队列的头元素，如果队列为空则返回null
    element(): E                                      //获取但不移除队列的头元素，如果为空则抛出异常

### 8.1 双端队列Deque和链表LinkedList ###

Deque支持在两端插入和删除元素，LinkedList类实现了Deque接口。  
PriorityQueue类实现了一个优先队列。

## 9. 总结 ##

*  Java合集框架支持集合、线性表、队列和映射表，他们分别定义在接口Set、List、Queue、Map中
 *  除去PriorityQueue，Java合集框架中的所有实例类都实现了Cloneable和Serializable接口。所以他们的实例都是可克隆和可实例化的。
 *  Comparator可以用于比较没有实现Comparable接口的类的对象。
 *  Vector向量类和ArrayList基本一样，不同的是Vector访问和修改向量的方法是同步的。

参考文章：《Java语言程序设计（进阶篇）》

[collection]: /images/20220520/560e8424b39e4135ab40458a089d0cd4.png