集合結合數據結構來看看（三）

一、隊列和棧

什麼是隊列？隊列是一種只能在一端插入，另外一端刪除的有序線性表，隊列中第一個插入也就第一個被移除，所以隊列是一種先進先出的線性表；

什麼是棧？棧是一種有序線性表，只能在表的一端進行插入和刪除，最後插入的元素被第一個刪除，所以棧是一種後進先出的線性表；

接下來還是上圖

二、棧源碼

這裡直接看源代碼吧，因為用單鏈表以及數組實現，如果前幾篇看懂了實現一個棧還是很簡單的，那我們直接看起源碼來吧；

還是老樣子先看繼承結構：

public class Stack<E> extends Vector<E>

這裡看下Stack這個類繼承Vector這個類，那麼我們就需要跳進去看下這個類的實現

public class Vector<E>
extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable

看到這個結構我們一定會很熟悉一下就想到了ArryList這個介面，所以這裡不做過多的強調一些方法，這裡只說一些重點內容；

1).Vertor類所有方法都實現了同步，這裡除去迭代的方法，因為每一個方法上都增加了synchronized這個關鍵字；

2).這裡強調一下擴容的方法，這裡還的看下這個構造函數，才能對比出差別

public Vector(int initialCapacity, int capacityIncrement) {
super;
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
this.capacityIncrement = capacityIncrement;
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}

這個構造函數初始化了一個capacityIncrement變數這個影響了數組擴容的大小，如果不指定就是默認擴展一倍，看到這裡如果看過的第一篇的讀者就知道與ArryList的差別了，忘記的了也沒關係，可以翻看一下，這裡我們稍微延伸性下，由於每個操作都是同步的方法，肯定在操作會影響性能，但是我們通常進行的單一操作，不管是添加還是刪除或者等等一系列操作，我們肯定還需要聲明一個鎖來保證操作的安全性，所以這就需要2個鎖來解決線程的安全問題，想到這裡大家就明白為什麼Vector這個類被廢棄了吧。接下來我們還是繼續Stack這個類在Vector這個類上主要包括了棧的push和 pop 操作，以及取堆棧頂點的 peek方法、測試堆棧是否為空的 empty 方法、在堆棧中查找項並確定到堆棧頂距離的 search方法。

三、隊列源碼

public interface Queue<E> extends Collection<E>

同樣是直接看源碼吧，這裡看到了Collection這個類，這裡需要提一下Collections這2個是不同的類，Collection這個類是一個集合介面。它提供了對集合對象進行基本操作的通用介面方法。Collection介面在Java 類庫中有很多具體的實現。Collection介面的意義是為各種具體的集合提供了最大化的統一操作方式。而這個Collections是一個包裝類，它包含有各種有關集合操作的靜態多態方法。此類不能實例化，就像一個工具類，服務於Java的Collection框架，關於這個類我後面會介紹下這個類的API，先說今天的重點吧，下圖是Collection繼承結構，圖雖然有些不標準，相信大家基本上還是能看明白的。這裡說下每個分支基本上能幹什麼事，對Connlection這個體系的集合有簡單的明白；

首先說一下Iterable，可以通過這個獲取一個Iterator，使用這個進行迭代，下面是介面裡面包含的方法；

Iterator<T> iterator;

接下來說Collection，這個裡面主要包含一些對集合操作的方法，另外還有進行遍歷的方法；剩下的子類就是對其擴展這裡說下之間的不同，List這個介面是有序集合，可以根據索引進行值的查找，另外List裡面可以允許重複值的出現；下面將List不同的API列出來讓大家更明朗一些，可能沒有複製全，因為源碼注釋有點多，另外就是List還提供listIterator這個方法，這個繼承Iterator這個類，是集合可以向前迭代。

E get(int index);

E set(int index, E element);

void add(int index, E element);

E remove(int index);

int indexOf(Object o);

int lastIndexOf(Object o);

ListIterator<E> listIterator;

ListIterator<E> listIterator(int index);

List<E> subList(int fromIndex, int toIndex);

接下來是Set這個不允許保存重複的元素，Set在Collection的介面上沒做什麼變動，完全一樣，SortedSet這個介面最要是一些排序介面，TreeSet主要實現了SortedSet這個介面，內部方法相對比較簡單，主要通過Comparator這個介面進行實現一系列的介面；NavigableSet這個介面主要擴展SortedSet具有搜索元素的方法，這個裡面的介面我感覺說不容易很沒明白大家寫個測試程序看下就可以，真的沒什麼搞頭（我有測試程序大家想要可以私聊下我）；

public interface SortedSet<E> extends Set<E> {
//返回一個比較器
Comparator<? super E> comparator;
//返回2個元素之間的集合
SortedSet<E> subSet(E fromElement, E toElement);
//返回小於該元素的集合
SortedSet<E> headSet(E toElement);
//返回大於或者等於該元素的集合
SortedSet<E> tailSet(E fromElement);
E first;//set中第一個元素
E last;//set中最後一個元素
}

最後來一下今天的主題Queue，這裡主要說下注意的地方Queue使用時要盡量避免Collection的add和remove方法，而是要使用offer來加入元素，使用poll來獲取並移出元素。它們的優點是通過返回值可以判斷成功與否，add和remove方法在失敗的時候會拋出異常。 如果要使用頭部元素而不移出該元素，使用element或者peek方法；接下來說下Deque這個介面，這個需要說下雙端隊列和隊列的差別，隊列只允許在一端插入，在另外一端刪除，而雙端隊列是一種擴展，它可以在兩端進行刪除和插入；因為可以在兩端訪問所以是一種具有棧和隊列性質的數據結構，這裡需要說一下Stack這個介面因為是同步線程，我們在選擇實現隊列的時候應該優先選擇Deque這個介面，下面可以列一個簡單的對應關係，讓大家明白這個介面內部方法與隊列和介面的對應關係；

四、結束語

其實隊列和棧裡面的東西還有好多應用場景，以後有遇到再說嘍，等等把map這些都說完的時候我做一個完整的集合的繼承結構,接下來就是樹嘍，最近還有想法寫下SSH，java我也進入到框架學習了，還有好多路要走，加油吧！

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！