前言：算法第四版1.3节 背包、队列和栈 学习总结
Stack：
import java.util.Iterator; /** * 动态调整数组大小的栈 * 功能： LIFO * @author Chuanjie * @param <T> * */ public class ResizingArrayStack<T> implements Iterable<T> { private T[] a = (T[])new Object[1];; private int n = 0; private void resize(int sz){ T[] temp = (T[])new Object[sz]; for(int i = 0;i < n;i++) temp[i] = a[i]; a = temp; } public boolean isEmpty(){ return n == 0; } public int size(){ return n; } public void push(T item){ if(n == a.length) resize(2*a.length); a[n++] = item; } public T pop(){ T item = a[--n]; a[n] = null;//释放引用， 避免对象游离，垃圾回收器可以将其回收 if(n > 0 && n == a.length/4) resize(a.length/2); return item; } @Override public Iterator<T> iterator() { return new ReverseArrayIterator(); } private class ReverseArrayIterator implements Iterator<T>{ private int i = n; @Override public boolean hasNext(){ return i > 0; } @Override public T next() { return a[--i]; } @Override public void remove() { } } } import java.util.Iterator; /** * 链表实现栈 * 功能：LIFO * @author Chuanjie * */ public class Stack <T> implements Iterable<T>{ private Node first; private int n; private class Node{ T item; Node next; } public boolean isEmpty(){ return first == null; } public int size(){ return n; } public void push(T item){ Node oldfirst = first; first = new Node(); first.item = item; first.next = oldfirst; n++; } public T pop(){ T item = first.item; first = first.next; n--; return item; } @Override public Iterator<T> iterator() { return new ListIterator(); } private class ListIterator implements Iterator<T>{ private Node current = first; @Override public boolean hasNext() { return current != null; } @Override public T next() { T item = current.item; current = current.next; return item; } @Override public void remove() { } } } Queue: import java.util.Iterator; /** * 链表实现队列 * 功能：FIFO * @author Chuanjie * */ public class Queue<T> implements Iterable<T> { private Node first; private Node last; private int n; private class Node{ T item; Node next; } public boolean isEmpty(){ return first == null; } public int size(){ return n; } public void enqueue(T item){ //向表尾添加元素 Node oldlast = last; last = new Node(); last.item = item; last.next = null; if(isEmpty()) first = last; //找到last else oldlast.next = last; n++; } public T dequeue(){ //从表头删除元素 T item = first.item; first = first.next; if(isEmpty()) last = null; n--; return item; } @Override public Iterator<T> iterator() { return null; } } Bag: import java.util.Iterator; /** * 链表实现背包 * 功能：保存添加的元素 * @author Chuanjie * * @param <T> */ public class Bag <T> implements Iterable<T>{ private Node first; private int n; private class Node{ T item; Node next; } public boolean isEmpty(){ return first == null; } public int size(){ return n; } public void add(T item){ Node oldfirst = first; first = new Node(); first.item = item; first.next = oldfirst; n++; } @Override public Iterator<T> iterator() { return new ListIterator(); } private class ListIterator implements Iterator<T>{ private Node current = first; @Override public boolean hasNext() { return current != null; } @Override public T next() { T item = current.item; current = current.next; return item; } @Override public void remove() { } } } 总结：1. 结构化存储中，链表（链式存储）是数组（顺序存储）的重要替代方式：可以处理任意类型的数据、所需空间总是和集合大小成正比、一次操作的时间和集合大小无关。2. 学习底层实现，尝试写API是深入理解的必经之路，Don't use a library until you understand its API!
