由于之前對ArrayList和LinkedList 的分析,是以在看Vector和Stack的源碼實作就會非常簡單

觀察上圖,我們可以看到本文要說的 Stack 和 Vector 是父子關系,我們依舊從源碼入手,期望能夠對你有幫助,如果本文有了解不對的地方,請及時指正,謝謝您

Vector

我們知道Vector的實作和ArrayList一樣,都是底層以數組的方式存儲的,但是不同的Vector是線程安全的,這一點我們可以從源碼中看出來

定義

@since 1.0
public class Vector<E>
    extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{...}

屬性

//儲存元素的數組
protected Object[] elementData;
//容量增量,就是數組按多少速度擴容,這裡是2倍
protected int capacityIncrement;
//元素個數
protected int elementCount;
//最大容量,跟ArrayList一樣的
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

對于屬性列出了這幾個,我們看到一些ArrayList中出現的屬性值,可能是由于出現的過早的原因,其中的屬性變量名定義的并不是很直覺,比如elementCount在ArrayList中稱為size
對于其中的方法實作的源碼我就不列的很詳細了,我看了一下,其實作基本都是在方法上加上了sync關鍵字

初始化

public Vector() {
    this(10);
}
public Vector(int initialCapacity) {
    this(initialCapacity, 0);
}
public Vector(int initialCapacity, int capacityIncrement) {
    super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    this.elementData = new Object[initialCapacity];
    this.capacityIncrement = capacityIncrement;
}
public Vector(Collection<? extends E> c) {
    elementData = c.toArray();
    elementCount = elementData.length;
    if (elementData.getClass() != Object[].class)
        elementData = Arrays.copyOf(elementData, elementCount, Object[].class);
}

如上實作較簡單,我們從中可以看到,對于Vector的增量和初始化容量我們都可以進行自定義

add

跟之前的ArrayList的實作基本一緻,是以就不再贅述

public synchronized boolean add(E e) {
    modCount++;
    add(e, elementData, elementCount);
    return true;
}
private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)
        elementData = grow();
    elementData[s] = e;
    elementCount = s + 1;
}

public void add(int index, E element) {
    insertElementAt(element, index);
}
public synchronized void insertElementAt(E obj, int index) {
    if (index > elementCount) {
        throw new ArrayIndexOutOfBoundsException(index
                                                 + " > " + elementCount);
    }
    modCount++;
    final int s = elementCount;
    Object[] elementData = this.elementData;
    if (s == elementData.length)
        elementData = grow();
    //核心方法arrycopy,将要插入的位置挪出來
    System.arraycopy(elementData, index,
                     elementData, index + 1,
                     s - index);
    elementData[index] = obj;
    elementCount = s + 1;
}

//邏輯跟ArrayList中的完全一緻,不再贅述
public synchronized boolean addAll(int index, Collection<? extends E> c) {
    if (index < 0 || index > elementCount)
        throw new ArrayIndexOutOfBoundsException(index);
    Object[] a = c.toArray();
    modCount++;
    int numNew = a.length;
    if (numNew == 0)
        return false;
    Object[] elementData = this.elementData;
    final int s = elementCount;
    if (numNew > elementData.length - s)
        elementData = grow(s + numNew);

    int numMoved = s - index;
    if (numMoved > 0)
        System.arraycopy(elementData, index,
                         elementData, index + numNew,
                         numMoved);
    System.arraycopy(a, 0, elementData, index, numNew);
    elementCount = s + numNew;
    return true;
}

對于上面代碼我們基本都分析過了在ArrayList中,是以下面的方法我不打算都貼出來了,直貼一個實作相較複雜的實作,我們已經貼出增加的方法,下面我們湊齊CRUD

remove

public boolean remove(Object o) {
    return removeElement(o);
}
public synchronized boolean removeElement(Object obj) {
    modCount++;
    //indexOf方法就跟之前介紹的node方法一緻,根據元素找出其位置
    int i = indexOf(obj);
    if (i >= 0) {
        removeElementAt(i);
        return true;
    }
    return false;
}
public synchronized void removeElementAt(int index) {
  //檢查索引
    if (index >= elementCount) {
        throw new ArrayIndexOutOfBoundsException(index + " >= " +
                                                 elementCount);
    }
    else if (index < 0) {
        throw new ArrayIndexOutOfBoundsException(index);
    }
    //j 就是要删除元素的位置
    int j = elementCount - index - 1;
    if (j > 0) {
        System.arraycopy(elementData, index + 1, elementData, index, j);
    }
    modCount++;
    elementCount--;
    elementData[elementCount] = null; /* to let gc do its work */
}

set

public synchronized E set(int index, E element) {
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);
    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

get

public synchronized E get(int index) {
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);
    return elementData(index);
}

上面實作沒得可說的了,很簡單,從中我們可以看出,Vector和ArrayList的實作之差一個sync,是以Vector是線程安全的,但是由于是線程安全的,是以Vector要比ArrayList要慢,因為鎖競争的原因,并且Vector的實作也不好,因為一個操作隻能是一個線程進行操作,這樣當競争高的時候會慢的要死.

Stack

從最上面的類圖中可以看到Stack是基于Vector實作的,是其子類,Stack是用于模拟棧這種資料結構,是指後進先出LIFO的容器,最後push進棧的元素,将最先被pop出棧,我們來看一下實作

public
class Stack<E> extends Vector<E> {...}

//由于父類Vector中的屬性都是protected修飾,是以本類的屬性就是使用了繼承下來的Vector類中的屬性

public Stack() {
}

push

自身的方法比較少,但是有些方法是直接調用了父類的預設實作,以提高代碼的複用性,我們可以都來看一下

Stack:
public E push(E item) {
    addElement(item);
    return item;
}
Vector:
public synchronized void addElement(E obj) {
    modCount++;
    add(obj, elementData, elementCount);
}

add的實作就是從數組頭開始一直加嘛,是以Stack就是這樣的,依次往數組中添加

pop

public synchronized E pop() {
    E obj;
    //Vector:size
    int len = size();
    //Stack:peek
    obj = peek();
    //Vector:removeElementAt之前有貼實作的源代碼
    removeElementAt(len - 1);
    return obj;
}

peek

public synchronized E peek() {
    ////Vector:size
    int len = size();
    if (len == 0)
        throw new EmptyStackException();
    ////Vector:elemenAt方法是将len-1位置上的資料傳回但是不删除
    return elementAt(len - 1);
}

search

public synchronized int search(Object o) {
    //Vector:lastIndexOf,從0開始一直往後循環搜尋,遇到第一個相等的傳回相同元素的index
    int i = lastIndexOf(o);
    if (i >= 0) {
        return size() - i;
    }
    //代表不存在
    return -1;
}

這就是一些核心的方法了,實作起來還是很簡單的,是以我就沒有很大篇幅的一句句注釋,但是需要注意的是,Stack的出入棧都是Object的,那麼Stack是一種棧結構,我們除了使用Stack,也可以考慮 ArrayDeque
ArrayDeque 底層是基于數組實作的,是以其性能也是很好的

隊列和棧

說到了上面的Stack實作類,那麼我們就應該再去了解一下,看看List中有哪些實作類可以直接拿過來當做隊列或者棧使用,我們之前介紹的LinkedList就可以,我們已經分析過了,是以我們這就不再詳細說LinkedList了
我們看一張類圖

Queue代表隊列的抽象,而Deque是其一個子類,其進一步擴充了Queue的方法,Deque就既可以實作棧又可以實作隊列了,我們分别看一下其中的方法定義
```
Queue:
boolean add(E e);
boolean offer(E e);
E remove();
E poll();
E element();
E peek();           
```

上面一些方法的作用和差別如下,摘自 CSDN

add()和offer()都是向隊列中添加一個元素。一些隊列有大小限制，是以如果想在一個滿的隊列中加入一個新項，調用 add() 方法就會抛出一個 unchecked 異常，而調用 offer() 方法會傳回 false。是以就可以在程式中進行有效的判斷

remove() 和 poll() 方法都是從隊列中删除第一個元素。如果隊列元素為空，調用remove() 的行為與 Collection 接口的版本相似會抛出異常，但是新的 poll() 方法在用空集合調用時隻是傳回 null。是以新的方法更适合容易出現異常條件的情況。

element() 和 peek() 用于在隊列的頭部查詢元素。與 remove() 方法類似，在隊列為空時， element() 抛出一個異常，而 peek() 傳回 null。

然後是Deque的方法

void push(E e);
E pop();
void addFirst(E e);
...

方法較多,但是我們從push和pop已經看出,Deque接口已經為我們定義了棧的操作,是以我們可以使用Deque的具體實作類來完成棧和隊列的操作,我們在這使用的是

ArrayDeque

public static void main(String[] args) throws Exception {
    Deque<String> queue = new ArrayDeque<>();
    queue.offer("A");
    queue.offer("B");
    queue.offer("C");
    System.out.println(queue.poll());
    System.out.println(queue.poll());
    System.out.println(queue.poll());
    //ABC
    Deque<String> stack = new ArrayDeque<>();
    stack.push("A");
    stack.push("B");
    stack.push("C");
    System.out.println(stack.pop());
    System.out.println(stack.pop());
    System.out.println(stack.pop());
    //CBA
}

在這我先不仔細分析ArrayDeque類,打算再單獨寫一下這個類,現在我們隻要知道他可以作為棧或者隊列就可以了
還有一種隊列,是有序隊列,如 PriorityQueue ,下面是他的實作方法,既然是保證了元素的有序,那麼添加進入的元素肯定是實作 Comparable 接口的,這裡所說的有序不是加入順序,而是排列順序,是以這個類就可以定制排序了,下面隻是介紹一下使用方法,具體的分析我會跟 ArrayDeque 一起寫出來的.
```
PriorityQueue<Integer> queue = new PriorityQueue<>();
queue.add(1);
queue.add(10);
queue.add(3);
queue.add(7);
//[1, 7, 3, 10]
System.out.println(queue);
int size = queue.size();
for (int i = 0; i < size; i++) {
    //1 3 7 10
    System.out.println(queue.poll());
}           
```

然後是定制排序

Comparator<Integer> comparator = (x,y) -> - Integer.compare(x,y);

将上面對象傳入構造參數中就可以實作數值的從大到小輸出

各種線性表的性能分析

Java提供的List就是一個線性表接口,而ArrayList,LinkedList又是線性表的兩種典型實作:基于數組的線性表和基于鍊的線性表.Queue代表了隊列,Deque代表了雙端隊列,既可以作為隊列使用,又可以當做棧使用
LinkedList集合不僅提供了List的功能,還提供了雙端隊列,棧的功能
一般來說,由于數組以一塊連續記憶體區來儲存所有的數組元素,是以數組在随機通路時性能最好,所有的内部以數組作為底層實作的集合在随機通路時性能都比較好.而内部以連結清單作為底層實作的集合在執行插入,删除操作時有較好的性能.但總體來說,ArrayList的性能比LinkedList的性能要好.是以大部分時候都應該考慮使用ArrayList.
使用List集合的一些建議
- 如果需要周遊List集合,對于ArrayList,Vector集合,應該是用随機通路方法get來周遊集合元素,這樣性能更好.對于LinkedList集合,則應該采用疊代器Iterator來周遊集合元素.
- 如果需要經常執行插入,删除操作來改變含大量資料的List集合的大小,則可考慮使用LinkedList集合,使用ArrayList,Vector集合可能需要經常配置設定内部數組的大小.效果可能較差.
- 如果有多個線程需要通路List集合中的元素,需要考慮使用Collections将幾個包裝成線程安全集合.

Java總結 - List實作類Vector&StackVectorStack隊列和棧各種線性表的性能分析

Vector

定義

屬性

初始化

add

remove

set

get

Stack

push

pop

peek

search

隊列和棧

各種線性表的性能分析

繼續閱讀

關于Gradle配置的小結

Java小案例——随機數猜測随機數猜測

nginx location中斜線的位置的重要性

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

neo4j之cypher使用文檔

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

scala (3) Function 和 Method

Java總結 - List實作類Vector&amp;StackVectorStack隊列和棧各種線性表的性能分析

Vector

定義

屬性

初始化

add

remove

set

get

Stack

push

pop

peek

search

隊列和棧

各種線性表的性能分析

繼續閱讀

Java總結 - List實作類Vector&StackVectorStack隊列和棧各種線性表的性能分析