博客一:轉載自http://shmilyaw-hotmail-com.iteye.com/blog/1825171 java stack的詳細實現分析 簡介 我們最常用的數據結構之一大概就是stack了。在實際的程式執行,方法調用的過程中都離不開stack。那麼,在一個成熟的類庫裡面,它的實現是怎麼 ...
博客一:轉載自http://shmilyaw-hotmail-com.iteye.com/blog/1825171
java stack的詳細實現分析
簡介
我們最常用的數據結構之一大概就是stack了。在實際的程式執行,方法調用的過程中都離不開stack。那麼,在一個成熟的類庫裡面,它的實現是怎麼樣的呢?也許平時我們實踐的時候也會嘗試著去寫一個stack的實現玩玩。這裡,我們就仔細的分析一下jdk里的詳細實現。
Stack
如果我們去查jdk的文檔,我們會發現stack是在java.util這個包里。它對應的一個大致的類關係圖如下:
通過繼承Vector類,Stack類可以很容易的實現他本身的功能。因為大部分的功能在Vector裡面已經提供支持了。
Stack裡面主要實現的有一下幾個方法:
方法名 | 返回類型 | 說明 |
empty | boolean | 判斷stack是否為空。 |
peek | E | 返回棧頂端的元素。 |
pop | E | 彈出棧頂的元素 |
push | E | 將元素壓入棧 |
search | int | 返回最靠近頂端的目標元素到頂端的距離。 |
因為前面我們已經提到過,通過繼承Vector,很大一部分功能的實現就由Vector涵蓋了。Vector的詳細實現我們會在後面分析。它實現了很多的輔助方法,給Stack的實現帶來很大的便利。現在,我們按照自己的思路來分析每個方法的具體步驟,再和具體實現代碼對比。
empty
從我們的思路來說,如果要判斷stack是否為空,就需要有一個變數來計算當前棧的長度,如果該變數為0,則表示該棧為空。或者說我們有一個指向棧頂的變數,如果它開始的時候是設置為空的,我們可以認為棧為空。這部分的實現代碼也很簡單:
Java代碼- public boolean empty() {
- return size() == 0;
- }
如果更進一步分析的話,是因為Vector已經實現了size()方法。在Vector裡面有一個變數elementCount來表示容器里元素的個數。如果為0,則表示容器空。這部分在Vector裡面的實現如下:
Java代碼- public synchronized int size() {
- return elementCount;
- }
peek
peek是指的返回棧頂端的元素,我們對棧本身不做任何的改動。如果棧里有元素的話,我們就返回最頂端的那個。而該元素的索引為棧的長度。如果棧為空的話,則要拋出異常:
Java代碼- public synchronized E peek() {
- int len = size();
- if (len == 0)
- throw new EmptyStackException();
- return elementAt(len - 1);
- }
這個elementAt方法也是Vector裡面的一個實現。在Vector裡面,實際上是用一個elementData的Object數組來存儲元素的。所以要找到頂端的元素無非就是訪問棧最上面的那個索引。它的詳細實現如下:
Java代碼- public synchronized E elementAt(int index) {
- if (index >= elementCount) {
- throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
- }
- return elementData(index);
- }
- @SuppressWarnings("unchecked")
- E elementData(int index) {
- return (E) elementData[index];
- }
pop
pop方法就是將棧頂的元素彈出來,如果棧里有元素,就取最頂端的那個,否則就要拋出異常:
Java代碼- public synchronized E pop() {
- E obj;
- int len = size();
- obj = peek();
- removeElementAt(len - 1);
- return obj;
- }
在這裡,判斷是否可以取棧頂元素在peek方法里實現了,也將如果棧為空則拋異常的部分包含在peek方法裡面。這裡有必要註意的一個細節就是,在通過peek()取到頂端的元素之後,我們需要用removeElementAt()方法將最頂端的元素移除。我們平時可能不太會留意到這一點。為什麼要移除呢?我們反正有一個elementCount來記錄棧的長度,不管它不是也可以嗎?
實際上,這麼做在程式運行的時候會有一個潛在的記憶體泄露的問題。因為在java裡面,如果我們普通定義的類型屬於強引用類型。比如這裡vector就底層用的Object[]這個數組強類型來保存數據。強類型在jvm中做gc的時候,只要程式中有引用到它,它是不會被回收的。這就意味著在這裡,只要我們一直在用著stack,那麼stack裡面所有關聯的元素就都別想釋放了。這樣運行時間一長就會導致記憶體泄露的問題。那麼,為瞭解決這個問題,這裡就是用的removeElementAt()方法。
Java代碼
- 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) {
- System.arraycopy(elementData, index + 1, elementData, index, j);
- }
- elementCount--;
- elementData[elementCount] = null; /* to let gc do its work */
- }
這個方法實現的思路也比較簡單。就是用待刪除元素的後面元素依次覆蓋前面一個元素。這樣,就相當於將數組的實際元素長度給縮短了。因為這裡這個移除元素的方法是定義在vector中間,它所面對的是一個更加普遍的情況,我們移除的元素不一定就是數組尾部的,所以才需要從後面依次覆蓋。如果只是單純對於一個棧的實現來說,我們完全可以直接將要刪除的元素置為null就可以了。
push
push的操作也比較直觀。我們只要將要入棧的元素放到數組的末尾,再將數組長度加1就可以了。
Java代碼- public E push(E item) {
- addElement(item);
- return item;
- }
這裡,addElement方法將後面的細節都封裝了起來。如果我們更加深入的去考慮這個問題的話,我們會發現幾個需要考慮的點。1. 首先,數組不會是無窮大的 ,所以不可能無限制的讓你添加元素下去。當我們數組長度到達一個最大值的時候,我們不能再添加了,就需要拋出異常來。2. 如果當前的數組已經滿了,實際上需要擴展數組的長度。常見的手法就是新建一個當前數組長度兩倍的數組,再將當前數組的元素給拷貝過去。前面討論的這兩點,都讓vector把這份心給操了。我們就本著八卦到底的精神看看它到底是怎麼乾的吧:
Java代碼- public synchronized void addElement(E obj) {
- modCount++;
- ensureCapacityHelper(elementCount + 1);
- elementData[elementCount++] = obj;
- }
- private void ensureCapacityHelper(int minCapacity) {
- // overflow-conscious code
- if (minCapacity - elementData.length > 0)
- grow(minCapacity);
- }
- 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);
- }
- private static int hugeCapacity(int minCapacity) {
- if (minCapacity < 0) // overflow
- throw new OutOfMemoryError();
- return (minCapacity > MAX_ARRAY_SIZE) ?
- Integer.MAX_VALUE :
- MAX_ARRAY_SIZE;
- }
看到這部分代碼的時候,我不由得暗暗嘆了口氣。真的是拔了蘿蔔帶出泥。本來想看看stack的細節實現,結果這些細節把vector都深深的出賣了。在vector中間有幾個計數的變數,elementCount表示裡面元素的個數,elementData是保存元素的數組。所以一般情況下數組不一定是滿的,會存在著elementCount <= elementData.length這樣的情況。這也就是為什麼ensureCapacityHelper方法里要判斷一下當新增加一個元素導致元素的數量超過數組長度了,我們要做一番調整。這個大的調整就在grow方法里展現了。
grow方法和我們所描述的方法有點不一樣。他不一樣的一點在於我們可以用一個capacityIncrement來指示調整數組長度的時候到底增加多少。預設的情況下相當於數組長度翻倍,如果設置了這個變數就增加這個變數指定的這麼多。
search
search這部分就相當於找到一個最靠近棧頂端的匹配元素,然後返回這個元素到棧頂的距離。
Java代碼- public synchronized int search(Object o) {
- int i = lastIndexOf(o);
- if (i >= 0) {
- return size() - i;
- }
- return -1;
- }
對應在vector裡面的實現也相對容易理解:
Java代碼- public synchronized int lastIndexOf(Object o) {
- return lastIndexOf(o, elementCount-1);
- }
- public synchronized int lastIndexOf(Object o, int index) {
- if (index >= elementCount)
- throw new IndexOutOfBoundsException(index + " >= "+ elementCount);
- if (o == null) {
- for (int i = index; i >= 0; i--)
- if (elementData[i]==null)
- return i;
- } else {
- for (int i = index; i >= 0; i--)
- if (o.equals(elementData[i]))
- return i;
- }
- return -1;
- }
這個lastIndexOf的實現無非是從數組的末端往前遍歷,如果找到這個對象就返回。如果到頭了,還找不到對象呢?...不好意思,誰讓你找不到對象的?活該你光棍,那就返回個-1吧。
Vector
在前面對stack的討論和分析中,我們幾乎也把vector這部分主要的功能以及實現給涵蓋了。vector和相關類以及介面的關係類圖如下:
因為Java沒有內置對List類型的支持,所以Vector內部的實現是採用一個object的array。其定義如下:
Java代碼- protected Object[] elementData;
這裡從某種角度來說可以說是java里對泛型支持的不足,因為內部保存數據的是Object[],在存取數據的時候如果不註意的話會出現存取數據類型不一致的錯誤。所以在以下的某些個方法里需要加上@SuppressWarnings("unchecked")的聲明。
Java代碼- @SuppressWarnings("unchecked")
- E elementData(int index) {
- return (E) elementData[index];
- }
我們前面討論的那些數組的增長,刪除元素,查找元素以及修改等功能就占據了vector的大部分。如果有興趣看vector的源代碼的話,會發現裡面主要就是這些功能的實現再加上一個迭代器功能。總共的代碼不是很多,1200多行,這裡就不再贅述了。
可以說,vector它本身就是一個可以動態增長的數組。和我們常用的ArrayList很像。和ArrayList的不同在於它對元素的訪問都用synchronized修飾,也就是說它是線程安全的。在多線程的環境下,我們可以使用它。
總結
看前面這些代碼,不但理順了棧和vector的具體實現,還可以從中發現一些其他的東西。比如說,棧最大的長度取決於vector裡面數組能有多長。這裡vector裡面最大能取到Integer.MAX_VALUE。 以前寫c程式的代碼時經常感嘆,要是有那種可以自動增長的數組類型就好了。當然,c99後面確實提供了這個福利。在java裡面,比較典型這一部分就由vector提供了。你看,他可以自動按照需要增長,本身是線程安全的,順便幫你把清除元素時的記憶體泄露問題都考慮到了。簡直是自動、安全、健康又環保啊:)
參考資料:
http://docs.oracle.com/javase/7/docs/api/java/util/Stack.html
http://docs.oracle.com/javase/7/docs/api/java/util/Vector.html
博客二:轉載自http://www.jb51.net/article/37872.htm
Java中Vector與ArrayList的區別詳解
首先看這兩類都實現List介面,而List介面一共有三個實現類,分別是ArrayList、Vector和LinkedList。List用於存放多個元素,能夠維護元素的次序,並且允許元素的重覆。
3個具體實現類的相關區別如下:
1.ArrayList是最常用的List實現類,內部是通過數組實現的,它允許對元素進行快速隨機訪問。數組的缺點是每個元素之間不能有間隔,當數組大小不滿足時需要增加存儲能力,就要講已經有數組的數據複製到新的存儲空間中。當從ArrayList的中間位置插入或者刪除元素時,需要對數組進行複製、移動、代價比較高。因此,它適合隨機查找和遍歷,不適合插入和刪除。
2.Vector與ArrayList一樣,也是通過數組實現的,不同的是它支持線程的同步,即某一時刻只有一個線程能夠寫Vector,避免多線程同時寫而引起的不一致性,但實現同步需要很高的花費,因此,訪問它比訪問ArrayList慢。
3.LinkedList是用鏈表結構存儲數據的,很適合數據的動態插入和刪除,隨機訪問和遍歷速度比較慢。另外,他還提供了List介面中沒有定義的方法,專門用於操作表頭和表尾元素,可以當作堆棧、隊列和雙向隊列使用。
查看Java源代碼,發現當數組的大小不夠的時候,需要重新建立數組,然後將元素拷貝到新的數組內,ArrayList和Vector的擴展數組的大小不同。
ArrayList中:
public boolean add(E e) {
ensureCapacity(size + 1); // 增加元素,判斷是否能夠容納。不能的話就要新建數組
elementData[size++] = e;
return true;
}
public void ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
Object oldData[] = elementData; // 此行沒看出來用處,不知道開發者出於什麼考慮
int newCapacity = (oldCapacity * 3)/2 + 1; // 增加新的數組的大小
if (newCapacity < minCapacity)
newCapacity = minCapacity;
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
Vector中:
private void ensureCapacityHelper(int minCapacity) {
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
Object[] oldData = elementData;
int newCapacity = (capacityIncrement > 0) ?
(oldCapacity + capacityIncrement) : (oldCapacity * 2);
if (newCapacity < minCapacity) {
newCapacity = minCapacity;
}
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
關於ArrayList和Vector區別如下:
1.ArrayList在記憶體不夠時預設是擴展50%
+ 1個,Vector是預設擴展1倍。
2.Vector提供indexOf(obj,
start)介面,ArrayList沒有。
3.Vector屬於線程安全級別的,但是大多數情況下不使用Vector,因為線程安全需要更大的系統開銷。
博客三:轉載自http://uule.iteye.com/blog/2095650?utm_source=tuicool
隊列Queue、雙端隊列Deque
註意:這都只是介面而已
1、Queue
在java5中新增加了java.util.Queue介面,用以支持隊列的常見操作。該介面擴展了java.util.Collection介面。
Java代碼
- 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來用。
Java代碼- 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
Java代碼- 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 方法,如下表所示: