前言

java共有八大类型的数据类型，int、byte、double、long、boolean、 float 、short、char，这些远远不够使用，因为我们还需要用到集合类型的数据结构，如数组、链表等。在这里主要实现一下背包、队列和栈三种数据结构，基于链表实现。

定义api

链表节点定义

private class Node{
    Item item;
    Node next;
}

背包

背包是一种不支持从中删除元素的集合类型，他的目的是帮助用例收集元素并迭代遍历所有收集到的元素。

定义节点

private Node first;//链表的首结点
private Integer N = 0;//元素数

添加元素到首结点

public void add(Item item){
    Node oldFirst = first;
    first = new Node();
    first.item = item;
    first.next = oldFirst;
    N ++;
}

判断大小和判空实现

public boolean isEmpty(){
    return N <= 0;
}
public Integer size(){
    return N;
}

添加迭代器

因为集合需要迭代，就要实现Iterable接口，并实现iterator()方法。我们可以通过该方法获取迭代器对象。

public class Bag<Item> implements Iterable<Item> {//实现迭代接口
    @Override
    public Iterator<Item> iterator() {
        return new BagIterator();//通过该方法获取迭代器
    }
    private class BagIterator implements Iterator<Item> {//迭代器内部类实现Iterator接口
        private Node itNode = first;
        @Override
        public boolean hasNext() {
            return itNode!=null;
        }
        @Override
        public Item next() {
            Item item = itNode.item;
            itNode = itNode.next;
            return item;
        }
        @Override
        public void remove() {
        }
    }

完整代码为

package com.tp.collection;
import java.util.Iterator;

/**
* 背包
* @param <Item>
*/
public class Bag<Item> implements Iterable<Item> {
    private Node first;
    private Integer N = 0;
    private class Node{
        private Item item;
        private Node next;
    }
    public void add(Item item){
        Node oldFirst = first;
        first = new Node();
        first.item = item;
        first.next = oldFirst;
        N ++;
    }
    public boolean isEmpty(){
        return N <= 0;
    }
    public Integer size(){
        return N;
    }
    @Override
    public Iterator<Item> iterator() {
        return new BagIterator();
    }
    private class BagIterator implements Iterator<Item> {
        private Node itNode = first;
        @Override
        public boolean hasNext() {
            return itNode!=null;
        }
        @Override
        public Item next() {
            Item item = itNode.item;
            itNode = itNode.next;
            return item;
        }
        @Override
        public void remove() {


        }
    }
}

队列

队列是链表的尾部添加节点，在链表的头部删除节点。

由于需要在尾部操作节点，因此需要增加一个last节点指向尾部节点。

完成代码如下：

package com.tp.collection;
import java.util.Iterator;
/**
* 队列
* @param <Item>
*/
public class Queue<Item> implements Iterable<Item> {
    private Node first;
    private Node last;
    private Integer N = 0;
    private class Node{
        private Node next;
        private Item item;
    }
    //尾结点添加
    public void enqueue(Item item){
        Node oldLast = last;
        last = new Node();
        last.item = item;
        last.next = null;
        if (isEmpty()){
            first = last;
        } else {
            oldLast.next = last;
        }
        N++;
    }
    //首节点删除
    public Item dequeue(){
        Node oldFirst = first;
        if (oldFirst!=null){
            first = oldFirst.next;
            N --;
            return oldFirst.item;
        }else{
            return null;
        }
    }
    public boolean isEmpty(){
        return N<=0;
    }
    public Integer size(){
        return N;
    }
    @Override
    public Iterator<Item> iterator() {
        return new QueueIterator();
    }
    private class QueueIterator implements Iterator<Item>{
        Node current = first;
        @Override
        public boolean hasNext() {
            return current!=null;
        }
        @Override
        public Item next() {
            Item item = current.item;
            current = current.next;
            return item;
        }
        @Override
        public void remove() {
        }
    }
}

栈

基于链表的栈是在链表的头部插入和删除节点。

package com.tp.collection;
import java.util.Iterator;
public class Stack<Item> implements Iterable<Item> {
    private Node first;
    private Integer N = 0;
    private class Node{
        private Node next;
        private Item item;
    }
    //添加元素
    public void push(Item item){
        Node oldFirst = first;
        first = new Node();
        first.next = oldFirst;
        first.item = item;
        N++;
    }
    //删除元素
    public Item pop(){
        Node current = first;
        if (current==null){
            return null;
        }else {
            first = current.next;
            N--;
            return current.item;
        }
    }
    public boolean isEmpty(){
        return N<=0;
    }
    public Integer size(){
        return N;
    }
    @Override
    public Iterator<Item> iterator() {
        return new StackIterator();
    }
    private class StackIterator implements Iterator<Item>{
        Node current = first;
        @Override
        public boolean hasNext() {
            return current!=null;
        }
        @Override
        public Item next() {
            if (current!=null){
                Item item = current.item;
                current = current.next;
                return item;
            }
            return null;
        }
        @Override
        public void remove() {
        }
    }
}

测试用例

package com.tp;
import com.tp.collection.Bag;
import com.tp.collection.Queue;
import com.tp.collection.Stack;
import java.util.Iterator;

/**
* Hello world!
*
*/
public class App
{
    public static void main( String[] args )
{
        Bag<String> bag = new Bag<>();
        bag.add("aaa");
        bag.add("bbb");
        bag.add("ccc");
        System.out.println( bag.isEmpty() );
        System.out.println( bag.size() );
        Iterator it= bag.iterator();
        while(it.hasNext()){
            System.out.println( it.next() );
        }

        Queue<String> queue = new Queue();
        queue.enqueue("aaa");
        queue.enqueue("bbb");
        queue.enqueue("ccc");
        System.out.println( queue.dequeue() );
        System.out.println( queue.size());
        Iterator<String> it = queue.iterator();
        System.out.println( it.hasNext());System.out.println( it.next());
        System.out.println( queue.dequeue() );
        System.out.println( queue.size() );
        System.out.println( queue.dequeue() );
        System.out.println( queue.isEmpty());

        Stack<String> stack = new Stack<>();
        stack.push("aaa");
        stack.push("bbb");
        stack.push("ccc");
        for (String s:stack){
            System.out.println(s);
        }
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.size());
        System.out.println(stack.isEmpty());
    }
}

总结

基于链表实现这三个集合都是比较类似的，都需要创建内部节点，需要创建迭代器内部类。