java的容器與迭代器是一個老生常談的話題了。

本文旨在與大家分享一些關于雙向鏈表與迭代器的運用小技巧，并希望本篇文章的內容能夠在項目中給你帶來幫助。

Stack與LinkedList

Stack是一個LIFO(后進先出)的容器。若要在java中定義一個Stack應該怎么辦？

也許你馬上會想到，java中對Stack類型的容器提供了源生支持，所以我們使用jdk包中提供的Stack類不就解決問題了嗎？

是的，這是很合理的思路。重復造輪子不是java的風格。那么就讓我們來看看源生的Stack容器應該如何使用。

先來一睹jdk中的源生Stack容器類：

* @author Jonathan Payne * @since JDK1.0 */publicclass Stack extends Vector { /** * Creates an empty Stack. */ public Stack() { } /** * Pushes an item onto the top of this stack. This has exactly * the same effect as: * 

 * addElement(item)

* * @param item the item to be pushed onto this stack. * @return the item argument. * @see java.util.Vector#addElement */ public E push(E item) { addElement(item); return item; } ....... ..... ... .

嗯？等等，Stack繼承自Vector？！

糟了！我們僅僅想要一個單純的LIFO容器，而大名鼎鼎的Vector不僅速度慢還帶有一堆我們不需要的“特性”，繼續使用源生的Stack顯然不是一個好的選擇。

這下可棘手了，我們現在要如何實現一個Stack呢？

LinkedList

LinkedList是一個雙向鏈表。關于它，想必不用介紹太多，光看名字就應該能夠猜到，你想要的數據結構它應該都能實現。

所以，我們是不是可以通過LinkedList來實現一個自己的Stack類呢？

import java.util.LinkedList;public class Stack {  // 容器 private LinkedList lt = new LinkedList();  // 模擬棧的push方法 public void push(T e) { // 壓棧 lt.addLast(e); } // 模擬棧的pop方法 public T pop() { // 彈棧 return lt.removeLast(); } // 模擬棧的peek方法 public T peek() { // 取得棧頂元素 return lt.getLast(); } public boolean isEmpty() { return lt.isEmpty(); } public static void main(String[] args) { Stack sk = new Stack(); sk.push("hello"); sk.push("world"); System.out.println(sk.pop()); System.out.println(sk.pop()); }}---------------------worldhello

太好了。通過LinkedList，我們模擬了一個LIFO數據結構的實現，并且這個類的名字也叫做Stack。

除此之外他還沒有Vector的一大堆“特性”。這就是我們需要的單純的LIFO容器。

迭代器

在上一小節，我們實現了我們自己的LIFO容器。在這一小節，我們想辦法讓這個LIFO容器變得更“完美”一些。

在Java中，任何容器都屬于可迭代對象，且能被foreach所迭代。

顯然，我們創造的Stack容器目前還未擁有迭代器特征。由于追求完美和代碼潔癖是一個合格的程序員所應該具有的素養，所以接下來讓我們對這個Stack進行一點小小的改造。

import java.util.Iterator;import java.util.LinkedList;// 繼承Iterable接口，使其成為可迭代對象。public class Stack implements Iterable {  // 容器 private LinkedList lt = new LinkedList();  // 模擬棧的push方法 public void push(T e) { // 壓棧 lt.addLast(e); } // 模擬棧的pop方法 public T pop() { // 彈棧 return lt.removeLast(); } // 模擬棧的peek方法 public T peek() { // 取得棧頂元素 return lt.getLast(); } public boolean isEmpty() { return lt.isEmpty(); }  // 可迭代對象的標準迭代方法 @Override public Iterator iterator() { return lt.iterator(); } public static void main(String[] args) { Stack sk = new Stack(); sk.push("hello"); sk.push("world"); // 通過foreach迭代對象(內部通過獲取迭代器進行迭代) for (String s : sk) { System.out.println(s); }  // 顯示的通過獲取Stack迭代器進行迭代 Iterator skit = sk.iterator(); while (skit.hasNext()) { System.out.println(skit.next()); }  System.out.println(sk.pop()); System.out.println(sk.pop()); }}---------------------helloworldhelloworldworldhello

現在，Stack是一個標準的LIFO容器了。他就像其他的源生java容器一樣，是一個可迭代對象并且能夠被foreach所迭代。任何一個Java程序員，都能夠像使用其他源生容器一樣使用我們的自定義Stack容器了！

反向迭代

好景不長。

正當你在項目中愉快的使用上面的Stack容器解決一個又一個需求時，難題出現了。

業務方提出了一個討人厭的需求，它需要反向遍歷Stack容器。而追求嚴謹優雅的你，絕對不會允許使用for循環去遍歷容器的這種low逼方式出現。

看來只好再對Stack容器的功能進行一些增強了。

import java.util.Iterator;import java.util.LinkedList;// 繼承Iterable接口，使其成為可迭代對象。public class Stack implements Iterable {  // 容器 private LinkedList lt = new LinkedList();  // 模擬棧的push方法 public void push(T e) { // 壓棧 lt.addLast(e); } // 模擬棧的pop方法 public T pop() { // 彈棧 return lt.removeLast(); } // 模擬棧的peek方法 public T peek() { // 取得棧頂元素 return lt.getLast(); } public boolean isEmpty() { return lt.isEmpty(); } // 可迭代對象的標準迭代方法 @Override public Iterator iterator() { return lt.iterator(); } // 返回一個可迭代對象。重寫可迭代對象的iterator方法，返回重寫了next()方法的迭代器對象。 public Iterable reversed() { return new Iterable() { public Iterator iterator() { return new Iterator() { private int current = lt.size() - 1;  // 實現hasNext方法 @Override public boolean hasNext() { return current >= 0; }  // 實現next方法，實現反向迭代 @Override public T next() { if (!hasNext()) { return null; } // 先輸出結果再-- T element = lt.get(current--); return element; }  // 實現remove方法。remove掉最新迭代出的對象。(與源生容器的迭代器實現保持一致) @Override public void remove() { lt.remove(current + 1); } }; } }; } public static void main(String[] args) { Stack sk = new Stack(); sk.push("hello"); sk.push("world"); for (String s : sk) { System.out.println(s); }  Iterator skit = sk.iterator(); while (skit.hasNext()) { System.out.println(skit.next()); }  // 通過foreach反向迭代sk for (String s : sk.reversed()) { System.out.println(s); } // 顯示的調用反向迭代器反向迭代sk Iterator reversedSkit = sk.reversed().iterator(); while (reversedSkit.hasNext()) { System.out.println(reversedSkit.next()); reversedSkit.remove(); }  if (!sk.isEmpty()) { System.out.println(sk.pop()); System.out.println(sk.pop()); } else { System.out.println("容器為空"); } }}---------------------helloworldhelloworldworldhelloworldhello容器為空

現在的Stack容器不僅是一個可迭代對象。通過調用reversed()方法還能支持反向迭代。利用這個容器不僅能解決問題，還能讓解決問題的方式變得更優雅。真棒！

總結

大多數情況下，我認為都應該使用LinkedList來實現Stack。同理LinkedList也能夠用來實現Queue。不過，需要注意的是通過這種方法實現的容器，依然和java中其他容器一樣，默認情況下在并發狀態中是不安全的。

并且，對于自己實現的容器，盡量通過迭代器設計模式對其進行功能增強，以符合java Collection的標準，并滿足項目中的需求。