也谈谈容器与迭代器


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的标准,并满足项目中的需求。


Copyright 2017/08/15 by Chuck Lin

若文章有幸帮到了您,您可以捐助我,以鼓励我写出更棒的作品!

alipay.jpg-17.7kBwechat.jpg-16.7kB

Copyright © chuck Lin 2017 all right reserved,powered by Gitbook该文件修订时间: 2018-07-15 10:39:59

results matching ""

    No results matching ""