前面我們已經接觸過幾種數據結構了，有數組、鏈表、Hash表、紅黑樹(二叉查詢樹)，今天再來看另外一種數據結構：棧。
什么是棧呢，我們先看一個例子：棧就相當于一個很窄的木桶，我們往木桶里放東西，往外拿東西時會發現，我們最開始放的東西在最底部，最先拿出來的是剛剛放進去的。所以，棧就是這么一種先進后出（FirstInLastOut，或者叫后進先出）的容器，它只有一個口，在這個口放入元素，也在這個口取出元素。那么我們接下來學習JDK中的棧。
一、Vector&Stack的基本介紹和使用
我們先看下JDK種的定義：
public class Stack<E> extends Vector<E> {從上面可以看到Stack 是繼承自于Vector的，因此我們要對Vector 也要有一定的認識。
Vector：線程安全的動態數組
Stack：繼承Vector，基于動態數組實現的一個線程安全的棧；
1.Vector 和 Stack的特點：
Vector與ArrayList基本是一致的，不同的是Vector是線程安全的，會在可能出現線程安全的方法前面加上synchronized關鍵字；
Vector：隨機訪問速度快，插入和移除性能較差(數組的特點)；支持null元素；有順序；元素可以重復；線程安全；
Stack：后進先出，實現了一些?；静僮鞯姆椒ǎㄆ鋵嵅⒉皇侵荒芎筮M先出，因為繼承自Vector，可以有很多操作，從某種意義上來講，不是一個棧）；
2.Vector 和 Stack 結構：
Vector類
與ArrayList基本一致，剩下的主要不同點如下：
1、Vector是線程安全的
2、ArrayList增長量和Vector的增長量不一致
其它，如構造方法不一致，Vector可以通過構造方法初始化capacityIncrement，另外還有其它一些方法，如indexOf方法，Vector支持從指定位置開始搜索查找；另外，Vector還有一些功能重復的冗余方法，如addElement，setElementAt方法，之所以這樣，是由于歷史原因，像addElement方法是以前遺留的，當集合框架引進的時候，Vector加入集合大家族，改成實現List接口，需要實現List接口中定義的一些方法，但是出于兼容考慮，又不能刪除老的方法，所以出現了一些功能冗余的舊方法；現在已經被ArrayList取代，基本很少使用，了解即可。
Stack類
實現了棧的基本操作。方法如下：
public Stack();
創建空棧
public synchronized E peek();
返回棧頂的值；
public E push(E item);
入棧操作；
public synchronized E pop();
出棧操作；
public boolean empty();
判斷棧是否為空；
public synchronized int search(Object o);
返回對象在棧中的位置；
對于上述的棧而言，我們基本只會經常用到上面的方法，雖然它繼承了Vector，有很多方法，但基本不會使用，而只是當做一個棧來看待。
3.基本使用
Vector中的部分方法使用如下，另外Vector的遍歷方式跟ArrayList一致，可以用foreach，迭代器，for循環遍歷；
import java.util.Arrays;import java.util.Iterator;import java.util.List;import java.util.ListIterator;import java.util.Vector;public class Test { public static void main(String[] args) { Vector<Integer> vector = new Vector<Integer>(); for(int i = 0; i < 10; i++){ vector.add(i); } //直接打印 System.out.println(vector.toString()); //size() System.out.println(vector.size()); //contains System.out.println(vector.contains(2)); //iterator Iterator<Integer> iterator = vector.iterator(); while(iterator.hasNext()){ System.out.print(iterator.next() + " "); } //toArray Object[] objArr = vector.toArray(); System.out.println("/nobjArr:" + Arrays.asList(objArr)); Integer[] intArr = vector.toArray(new Integer[vector.size()]); System.out.println("intArr:" + Arrays.asList(intArr)); //add vector.add(5); //remove vector.remove(5); System.out.println(vector); //containsAll System.out.println(vector.containsAll(Arrays.asList(5,6))); //addAll vector.addAll(Arrays.asList(555,666)); System.out.println(vector); //removeAll vector.removeAll(Arrays.asList(555,666)); System.out.println(vector); //addAll方法 vector.addAll(5, Arrays.asList(666,666, 6)); System.out.println(vector); //get方法 System.out.println(vector.get(5)); //set方法 vector.set(5, 55); System.out.println(vector.get(5)); //add方法 vector.add(0, 555); System.out.println(vector); //remove方法 vector.remove(0); System.out.println(vector); //indexof方法 System.out.println(vector.indexOf(6)); //lastIndexOf方法 System.out.println(vector.lastIndexOf(6)); //listIterator方法 ListIterator<Integer> listIterator = vector.listIterator(); System.out.println(listIterator.hasPrevious()); //listIterator(index)方法 ListIterator<Integer> iListIterator = vector.listIterator(5); System.out.println(iListIterator.previous()); //subList方法 System.out.println(vector.subList(5, 7)); //clear vector.clear(); System.out.println(vector); }}Stack中的部分方法使用如下，因為Stack繼承Vector，所以Vector可以用的方法，Stack同樣可以使用，以下列出一些Stack獨有的方法的例子，很簡單，就是棧的一些基本操作,另外stack除了Vector的幾種遍歷方式外，還有自己獨有的遍歷元素的方式（利用empty方法和pop方法實現棧頂到棧底的遍歷）：
import java.util.Stack;public class Test { public static void main(String[] args) { Stack<Integer> stack = new Stack<Integer>(); for(int i = 0; i < 10; i++){ stack.add(i); } System.out.println(stack); System.out.println(stack.peek()); stack.push(555); System.out.println(stack); System.out.println(stack.pop()); System.out.println(stack); System.out.println(stack.empty()); System.out.println(stack.search(6)); System.out.println("stack遍歷："); while(!stack.empty()){ System.out.print(stack.pop() + " "); } }}小節：
Vector是線程安全的，但是性能較差，一般情況下使用ArrayList,除非特殊需求；
如果打算用Stack作為棧來使用的話，就老老實實嚴格按照棧的幾種操作來使用，否則就是去了使用stack的意義，還不如用Vector;
二、Vector&Stacke的結構和底層存儲
public class Vector<E>extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable
Vector是List的一個實現類，其實Vector也是一個基于數組實現的List容器，其功能及實現代碼和ArrayList基本上是一樣的。那么不一樣的是什么地方的，一個是數組擴容的時候，Vector是*2，ArrayList是*1.5+1；另一個就是Vector是線程安全的，而ArrayList不是，而Vector線程安全的做法是在每個方法上面加了一個synchronized關鍵字來保證的。但是這里說一句，Vector已經不官方的（大家公認的）不被推薦使用了，正式因為其實現線程安全方式是鎖定整個方法，導致的是效率不高，那么有沒有更好的提到方案呢，其實也不能說有，但是還真就有那么一個，Collections.synchronizedList()
由于Stack是繼承和基于Vector，那么簡單看一下Vector的一些定義和方法源碼：
// 底層使用數組存儲數據 protected Object[] elementData; // 元素個數 protected int elementCount ; // 自定義容器擴容遞增大小 protected int capacityIncrement ; public Vector( int initialCapacity, int capacityIncrement) { super(); // 越界檢查 if (initialCapacity < 0) throw new IllegalArgumentException( "Illegal Capacity: " + initialCapacity); // 初始化數組 this.elementData = new Object[initialCapacity]; this.capacityIncrement = capacityIncrement; } // 使用synchronized關鍵字鎖定方法，保證同一時間內只有一個線程可以操縱該方法 public synchronized boolean add(E e) { modCount++; // 擴容檢查 ensureCapacityHelper( elementCount + 1); elementData[elementCount ++] = e; return true; } private void ensureCapacityHelper(int minCapacity) { // 當前元素數量 int oldCapacity = elementData .length; // 是否需要擴容 if (minCapacity > oldCapacity) { Object[] oldData = elementData; // 如果自定義了容器擴容遞增大小，則按照capacityIncrement進行擴容，否則按兩倍進行擴容（*2） int newCapacity = (capacityIncrement > 0) ? (oldCapacity + capacityIncrement) : (oldCapacity * 2); if (newCapacity < minCapacity) { newCapacity = minCapacity; } // 數組copy elementData = Arrays.copyOf( elementData, newCapacity); } }Vector就簡單看到這里，其他方法Stack如果沒有調用的話就不進行分析了，不明白的可以去看ArrayList源碼解析。
三、主要方法分析
1.peek()——獲取棧頂的對象
/** * 獲取棧頂的對象，但是不刪除 */ public synchronized E peek() { // 當前容器元素個數 int len = size(); // 如果沒有元素，則直接拋出異常 if (len == 0) throw new EmptyStackException(); // 調用elementAt方法取出數組最后一個元素（最后一個元素在棧頂） return elementAt(len - 1); } /** * 根據index索引取出該位置的元素，這個方法在Vector中 */ public synchronized E elementAt(int index) { // 越界檢查 if (index >= elementCount ) { throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount); } // 直接通過數組下標獲取元素 return (E)elementData [index]; }2.pop()——彈棧（出棧），獲取棧頂的對象，并將該對象從容器中刪除
/** * 彈棧，獲取并刪除棧頂的對象 */ public synchronized E pop() { // 記錄棧頂的對象 E obj; // 當前容器元素個數 int len = size(); // 通過peek()方法獲取棧頂對象 obj = peek(); // 調用removeElement方法刪除棧頂對象 removeElementAt(len - 1); // 返回棧頂對象 return obj; } /** * 根據index索引刪除元素 */ public synchronized void removeElementAt(int index) { modCount++; // 越界檢查 if (index >= elementCount ) { throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount); } else if (index < 0) { throw new ArrayIndexOutOfBoundsException(index); } // 計算數組元素要移動的個數 int j = elementCount - index - 1; if (j > 0) { // 進行數組移動，中間刪除了一個，所以將后面的元素往前移動（這里直接移動將index位置元素覆蓋掉，就相當于刪除了） System. arraycopy(elementData, index + 1, elementData, index, j); } // 容器元素個數減1 elementCount--; // 將容器最后一個元素置空（因為刪除了一個元素，然后index后面的元素都向前移動了，所以最后一個就沒用了 ） elementData[elementCount ] = null; /* to let gc do its work */ }3.push(E item)——壓棧（入棧），將對象添加進容器并返回
/** * 將對象添加進容器并返回 */ public E push(E item) { // 調用addElement將元素添加進容器 addElement(item); // 返回該元素 return item; } /** * 將元素添加進容器，這個方法在Vector中 */ public synchronized void addElement(E obj) { modCount++; // 擴容檢查 ensureCapacityHelper( elementCount + 1); // 將對象放入到數組中，元素個數+1 elementData[elementCount ++] = obj; }4.search(Object o)——返回對象在容器中的位置，棧頂為1
/** * 返回對象在容器中的位置，棧頂為1 */ public synchronized int search(Object o) { // 從數組中查找元素，從最后一次出現 int i = lastIndexOf(o); // 因為棧頂算1，所以要用size()-i計算 if (i >= 0) { return size() - i; } return -1; }5.empty()——容器是否為空
/** * 檢查容器是否為空 */ public boolean empty() { return size() == 0; }小節：
到這里Stack的方法就分析完成了，由于Stack最終還是基于數組的，理解起來還是很容易的（因為有了ArrayList的基礎啦）。
雖然jdk中Stack的源碼分析完了，但是這里有必要討論下，不知道是否發現這里的Stack很奇怪的現象，
（1）Stack為什么是基于數組實現的呢？
我們都知道數組的特點：方便根據下標查詢（隨機訪問），但是內存固定，且擴容效率較低。很容易想到Stack用鏈表實現最合適的。
（2）Stack為什么是繼承Vector的？
繼承也就意味著Stack繼承了Vector的方法，這使得Stack有點不倫不類的感覺，既是List又是Stack。如果非要繼承Vector合理的做法應該是什么：Stack不繼承Vector，而只是在自身有一個Vector的引用，聚合對不對？
唯一的解釋呢，就是Stack是jdk1.0出來的，那個時候jdk中的容器還沒有ArrayList、LinkedList等只有Vector，既然已經有了Vector且能實現Stack的功能，那么就干吧。。。既然用鏈表實現Stack是比較理想的，那么我們就來嘗試一下吧：
import java.util.LinkedList; public class LinkedStack<E> { private LinkedList<E> linked ; public LinkedStack() { this.linked = new LinkedList<E>(); } public E push(E item) { this.linked .addFirst(item); return item; } public E pop() { if (this.linked.isEmpty()) { return null; } return this.linked.removeFirst(); } public E peek() { if (this.linked.isEmpty()) { return null; } return this.linked.getFirst(); } public int search(E item) { int i = this.linked.indexOf(item); return i + 1; } public boolean empty() { return this.linked.isEmpty(); }}這里使用的LinkedList實現的Stack，記得在LinkedList中說過，LinkedList實現了Deque接口使得它既可以作為棧（先進后出），又可以作為隊列（先進先出）。
四、Vector&ArrayList的區別
List接口一共有三個實現類，分別是ArrayList、Vector和LinkedList。List用于存放多個元素，能夠維護元素的次序，并且允許元素的重復。
3個具體實現類的相關區別如下：
1.ArrayList是最常用的List實現類，內部是通過數組實現的，它允許對元素進行快速隨機訪問。數組的缺點是每個元素之間不能有間隔，當數組大小不滿足時需要增加存儲能力，就要講已經有數組的數據復制到新的存儲空間中。當從ArrayList的中間位置插入或者刪除元素時，需要對數組進行復制、移動、代價比較高。因此，它適合隨機查找和遍歷，不適合插入和刪除。
2.Vector與ArrayList一樣，也是通過數組實現的，不同的是它支持線程的同步，即某一時刻只有一個線程能夠寫Vector，避免多線程同時寫而引起的不一致性，但實現同步需要很高的花費，因此，訪問它比訪問ArrayList慢。
3.LinkedList是用鏈表結構存儲數據的，很適合數據的動態插入和刪除，隨機訪問和遍歷速度比較慢。另外，他還提供了List接口中沒有定義的方法，專門用于操作表頭和表尾元素，可以當作堆棧、隊列和雙向隊列使用。
五、隊列Queue、雙端隊列Deque簡單了解
1、Queue
在java5中新增加了java.util.Queue接口，用以支持隊列的常見操作。該接口擴展了java.util.Collection接口。
public interface Queue<E> extends Collection<E>
除了基本的 Collection 操作外，隊列還提供其他的插入、提取和檢查操作。
每個方法都存在兩種形式：一種拋出異常（操作失敗時），另一種返回一個特殊值（null 或 false，具體取決于操作）。
隊列通常（但并非一定）以 FIFO（先進先出）的方式排序各個元素。不過優先級隊列和 LIFO 隊列（或堆棧）例外，前者根據提供的比較器或元素的自然順序對元素進行排序，后者按 LIFO（后進先出）的方式對元素進行排序。
在 FIFO 隊列中，所有的新元素都插入隊列的末尾，移除元素從隊列頭部移除。
Queue使用時要盡量避免Collection的add()和remove()方法，而是要使用offer()來加入元素，使用poll()來獲取并移出元素。它們的優點是通過返回值可以判斷成功與否，add()和remove()方法在失敗的時候會拋出異常。如果要使用前端而不移出該元素，使用element()或者peek()方法。
offer 方法可插入一個元素，否則返回 false。這與 Collection.add 方法不同，該方法只能通過拋出未經檢查的異常使添加元素失敗。
remove() 和 poll() 方法可移除和返回隊列的頭。到底從隊列中移除哪個元素是隊列排序策略的功能，而該策略在各種實現中是不同的。remove() 和 poll() 方法僅在隊列為空時其行為有所不同：remove() 方法拋出一個異常，而 poll() 方法則返回 null。
element() 和 peek() 返回，但不移除，隊列的頭。
Queue 實現通常不允許插入 null 元素，盡管某些實現（如 LinkedList）并不禁止插入 null。即使在允許 null 的實現中，也不應該將 null 插入到 Queue 中，因為 null 也用作 poll 方法的一個特殊返回值，表明隊列不包含元素。
值得注意的是LinkedList類實現了Queue接口，因此我們可以把LinkedList當成Queue來用。
import java.util.Queue; import java.util.LinkedList; public class TestQueue { public static void main(String[] args) { Queue<String> queue = new LinkedList<String>(); queue.offer("Hello"); queue.offer("World!"); queue.offer("你好！"); System.out.println(queue.size()); String str; while((str=queue.poll())!=null){ System.out.print(str); } System.out.println(); System.out.println(queue.size()); } }2、Deque
public interface Deque<E> extends Queue<E>
一個線性 collection，支持在兩端插入和移除元素。
名稱 deque 是“double ended queue（雙端隊列）”的縮寫，通常讀為“deck”。
大多數 Deque 實現對于它們能夠包含的元素數沒有固定限制，但此接口既支持有容量限制的雙端隊列，也支持沒有固定大小限制的雙端隊列。
此接口定義在雙端隊列兩端訪問元素的方法。提供插入、移除和檢查元素的方法。因為此接口繼承了隊列接口Queue，所以其每種方法也存在兩種形式：一種形式在操作失敗時拋出異常，另一種形式返回一個特殊值（null 或 false，具體取決于操作）。
a、在將雙端隊列用作隊列時，將得到 FIFO（先進先出）行為。將元素添加到雙端隊列的末尾，從雙端隊列的開頭移除元素。從 Queue 接口繼承的方法完全等效于 Deque 方法，如下表所示：
b、用作 LIFO（后進先出）堆棧。應優先使用此接口而不是遺留 Stack 類。在將雙端隊列用作堆棧時，元素被推入雙端隊列的開頭并從雙端隊列開頭彈出。堆棧方法完全等效于 Deque 方法，如下表所示：
新聞熱點
疑難解答
圖片精選
