栈（Stack）、队列（Queue）与包（Bag）的实现

使用基本的链表结构实现栈，队列和包三种数据结构。首先用一个嵌套类来定义结点的抽象数据类型：

private class Node{
    Item item;
    Node next;
}

（1）堆栈Stack

import java.util.Iterator;
public class Stack<Item> implements Iterable<Item>{
private Node first;//栈顶
private int N;//元素数量
private class Node{
        Item item;
        Node next;
    }
public void push(Item item){
        Node oldfirst = first;
        first = new Node();
        first.item = item;
        first.next = oldfirst;
        N++;
    }
public Item pop(){
        Item item = first.item;
        first = first.next;
        N--;
return item;
    }
//实现迭代
public Iterator<Item> iterator(){
return new ListIterator();
    }
private class ListIterator implements Iterator<Item>{
private Node current = first;
public boolean hasNext(){
return current != null;
        }
public void remove(){}
public Item next(){
            Item item = current.item;
            current = current.next;;
return item;
        }
    }
}

（2）队列（Queue）的实现

public class Queue<Item> implements Iterator<Item>{
private Node first;
private Node last;
private int N;
private class Node{
        Item item;
        Node next;
    }
//队列向队尾填加元素
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++;
return item;    
    }
public Item dequeue(){
        Item item = first.item;
        first = first.next;
if(isEmpty()) last = null;
        N--;
return item;
    }    
}

（3）包（Bag）

public class Bag<Item>{
private Node first;
private int N;
private class Node{
        Item item;
        Node next;
    }
public void add(Item item){
        Node oldfirst = first;
        first = new Node();
        first.item = item;
        first.next = oldfiirst;
    }
}

顺序存储结构：数组
优点：通过索引可以任意访问元素
缺点：初始化时需要知道元素数量
链式存储结构：链表
优点：使用的空间大小和元素数量成正比
缺点：需要通过引用访问任意元素