前面我們已經接觸過幾種數據結構了,有數組、鍊錶、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:後進先出,實現了一些棧基本操作的方法(其實並不是只能後進先出,因為繼承自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 方法,如下表所示: