也谈谈容器与迭代器
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的标准，并满足项目中的需求。
