java的容器与迭代器是一个老生常谈的话题了。

本文旨在与大家分享一些关于双向链表与迭代器的运用小技巧，并希望本篇文章的内容能够在项目中给你带来帮助。

Stack与LinkedList

Stack是一个LIFO(后进先出)的容器。若要在java中定义一个Stack应该怎么办？

也许你马上会想到，java中对Stack类型的容器提供了源生支持，所以我们使用jdk包中提供的Stack类不就解决问题了吗？

是的，这是很合理的思路。重复造轮子不是java的风格。那么就让我们来看看源生的Stack容器应该如何使用。

先来一睹jdk中的源生Stack容器类：

* @author Jonathan Payne
 * @since JDK1.0
 */
public
class Stack<E> extends Vector<E> {
 /**
 * Creates an empty Stack.
 */
 public Stack() {
 }
 /**
 * Pushes an item onto the top of this stack. This has exactly
 * the same effect as:
 * <blockquote><pre>
 * addElement(item)</pre></blockquote>
 *
 * @param item the item to be pushed onto this stack.
 * @return the <code>item</code> 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<T> {
 
 // 容器
 private LinkedList<T> lt = new LinkedList<T>();
 
 // 模拟栈的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<String> sk = new Stack<String>();
 sk.push("hello");
 sk.push("world");
 System.out.println(sk.pop());
 System.out.println(sk.pop());
 }
}
---------------------
world
hello

太好了。通过LinkedList，我们模拟了一个LIFO数据结构的实现，并且这个类的名字也叫做Stack。

除此之外他还没有Vector的一大堆“特性”。这就是我们需要的单纯的LIFO容器。

迭代器

在上一小节，我们实现了我们自己的LIFO容器。在这一小节，我们想办法让这个LIFO容器变得更“完美”一些。

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

显然，我们创造的Stack容器目前还未拥有迭代器特征。由于追求完美和代码洁癖是一个合格的程序员所应该具有的素养，所以接下来让我们对这个Stack进行一点小小的改造。

import java.util.Iterator;
import java.util.LinkedList;
// 继承Iterable接口，使其成为可迭代对象。
public class Stack<T> implements Iterable<T> {
 
 // 容器
 private LinkedList<T> lt = new LinkedList<T>();
 
 // 模拟栈的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<T> iterator() {
 return lt.iterator();
 }
 public static void main(String[] args) {
 Stack<String> sk = new Stack<String>();
 sk.push("hello");
 sk.push("world");
 // 通过foreach迭代对象（内部通过获取迭代器进行迭代）
 for (String s : sk) {
 System.out.println(s);
 }
 
 // 显示的通过获取Stack迭代器进行迭代
 Iterator<String> skit = sk.iterator();
 while (skit.hasNext()) {
 System.out.println(skit.next());
 }
 
 System.out.println(sk.pop());
 System.out.println(sk.pop());
 }
}
---------------------
hello
world
hello
world
world
hello

现在，Stack是一个标准的LIFO容器了。他就像其他的源生java容器一样，是一个可迭代对象并且能够被foreach所迭代。任何一个Java程序员，都能够像使用其他源生容器一样使用我们的自定义Stack容器了！

反向迭代

好景不长。

正当你在项目中愉快的使用上面的Stack容器解决一个又一个需求时，难题出现了。

业务方提出了一个讨人厌的需求，它需要反向遍历Stack容器。而追求严谨优雅的你，绝对不会允许使用for循环去遍历容器的这种low逼方式出现。

看来只好再对Stack容器的功能进行一些增强了。

import java.util.Iterator;
import java.util.LinkedList;
// 继承Iterable接口，使其成为可迭代对象。
public class Stack<T> implements Iterable<T> {
 
 // 容器
 private LinkedList<T> lt = new LinkedList<T>();
 
 // 模拟栈的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<T> iterator() {
 return lt.iterator();
 }
 // 返回一个可迭代对象。重写可迭代对象的iterator方法，返回重写了next()方法的迭代器对象。
 public Iterable<T> reversed() {
 return new Iterable<T>() {
 public Iterator<T> iterator() {
 return new Iterator<T>() {
 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<String> sk = new Stack<String>();
 sk.push("hello");
 sk.push("world");
 for (String s : sk) {
 System.out.println(s);
 }
 
 Iterator<String> skit = sk.iterator();
 while (skit.hasNext()) {
 System.out.println(skit.next());
 }
 
 // 通过foreach反向迭代sk
 for (String s : sk.reversed()) {
 System.out.println(s);
 }
 // 显示的调用反向迭代器反向迭代sk
 Iterator<String> 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("容器为空");
 }
 }
}
---------------------
hello
world
hello
world
world
hello
world
hello
容器为空

现在的Stack容器不仅是一个可迭代对象。通过调用reversed()方法还能支持反向迭代。利用这个容器不仅能解决问题，还能让解决问题的方式变得更优雅。真棒！

总结

大多数情况下，我认为都应该使用LinkedList来实现Stack。同理LinkedList也能够用来实现Queue。不过，需要注意的是通过这种方法实现的容器，依然和java中其他容器一样，默认情况下在并发状态中是不安全的。

并且，对于自己实现的容器，尽量通过迭代器设计模式对其进行功能增强，以符合java Collection的标准，并满足项目中的需求。