【泛型可迭代的基础集合数据类型的API】
背包：就是一种不支持从中删除元素的集合数据类型——它的目的就是帮助用例收集元素并迭代遍历所有收集到的元素。（用例也可以检查背包是否为空， 或者获取背包中元素的数量）
public class Bag<Item> implements Iterable<Item>
Bag() 创建一个空背包
void add(Item item) 添加一个元素
boolean isEmpty() 背包是否为空
int size() 背包中的元素数量
使用Bag的API， 用例可以将元素添加到背包，并通过foreach循环来访问所有元素。用例也可以使用栈或者队列， 但使用Bag可以说明元素的处理顺序不重要 。
先进先出（FIFO）队列：
public class Queue<Item> implements Iterable<Item>
Queue() 创建一个空队列
void enqueue(Item item) 添加一个元素
Item dequeue() 删除最近添加的元素
boolean isEmpty() 队列是否为空
int size() 队列中的元素数量
下压（后进先出，LIFO）栈
public class Stack<Item> implements Iterable<Item>
Stack() 创建一个空栈
void push(Item item) 添加一个元素
Item pop() 删除最近添加的元素
boolean isEmpty() 栈是否为空
int size() 栈中元素数量
Stats类是Bag的一个典型用例。
它的任务是简单地计算标准输入中的所有double值的平均值和样本标准差。数的计算顺序和结果无关，因此我们将它们保存在一个Bag对象中， 并使用foreach循环来计算每个和。
用Bag对象保存所有数字是更复杂的统计计算所必须的 。
背包的典型用例：Stats.java
public class Stats { public static void main(String[] args) { Bag<Double> numbers = new Bag<Double>(); while(!StdIn.isEmpty()) numbers.add(StdIn.readDouble()); int N = numbers.size(); double sum = 0.0; for (Double x : numbers) sum += x; double mean = sum / N; sum = 0.0; for (Double x : numbers) sum += (x-mean)*(x-mean); double std = Math.sqrt(sum/(N-1)); StdOut.printf("mean : %.2f\n", mean); StdOut.printf("Std dev : %.2f\n", std); } }
【打印结果】
【Bag.java】
import java.util.Iterator; import java.util.NoSuchElementException; public class Bag<Item> implements Iterable<Item> { private int N; // number of elements in bag private Node<Item> first; // beginning of bag // helper linked list class private static class Node<Item> {//嵌套类 private Item item; private Node<Item> next; } /** * Initializes an empty bag. */ public Bag() { first = null; N = 0; } /** * Is this bag empty? * @return true if this bag is empty; false otherwise */ public boolean isEmpty() { return first == null; } /** * Returns the number of items in this bag. * @return the number of items in this bag */ public int size() { return N; } /** * Adds the item to this bag. * @param item the item to add to this bag */ public void add(Item item) {//由add()方法可以看出，是头插法。 Node<Item> oldfirst = first; first = new Node<Item>(); first.item = item; first.next = oldfirst; N++; } /** * Returns an iterator that iterates over the items in the bag in arbitrary order. * @return an iterator that iterates over the items in the bag in arbitrary order */ public Iterator<Item> iterator() { return new ListIterator<Item>(first); } // an iterator, doesn‘t implement remove() since it‘s optional private class ListIterator<Item> implements Iterator<Item> { private Node<Item> current; public ListIterator(Node<Item> first) { current = first; } public boolean hasNext() { return current != null; } public void remove() { throw new UnsupportedOperationException(); } public Item next() { if (!hasNext()) throw new NoSuchElementException(); Item item = current.item; current = current.next; return item; } } /** * Unit tests the <tt>Bag</tt> data type. */ public static void main(String[] args) { Bag<String> bag = new Bag<String>(); while (!StdIn.isEmpty()) { String item = StdIn.readString(); bag.add(item); } StdOut.println("size of bag = " + bag.size()); for (String s : bag) { StdOut.println(s); } } }
【Queue.java】
import java.util.Iterator; import java.util.NoSuchElementException; public class Queue<Item> implements Iterable<Item> { private int N; // number of elements on queue private Node<Item> first; // beginning of queue private Node<Item> last; // end of queue // helper linked list class private static class Node<Item> { private Item item; private Node<Item> next; } /** * Initializes an empty queue. */ public Queue() { first = null; last = null; N = 0; } /** * Is this queue empty? * @return true if this queue is empty; false otherwise */ public boolean isEmpty() { return first == null; } /** * Returns the number of items in this queue. * @return the number of items in this queue */ public int size() { return N; } /** * Returns the item least recently added to this queue. * @return the item least recently added to this queue * @throws java.util.NoSuchElementException if this queue is empty */ public Item peek() { if (isEmpty()) throw new NoSuchElementException("Queue underflow"); return first.item; } /** * Adds the item to this queue. * @param item the item to add */ public void enqueue(Item item) { Node<Item> oldlast = last; last = new Node<Item>(); last.item = item; last.next = null; if (isEmpty()) first = last; else oldlast.next = last; N++; } /** * Removes and returns the item on this queue that was least recently added. * @return the item on this queue that was least recently added * @throws java.util.NoSuchElementException if this queue is empty */ public Item dequeue() { if (isEmpty()) throw new NoSuchElementException("Queue underflow"); Item item = first.item; first = first.next; N--; if (isEmpty()) last = null; // to avoid loitering return item; } /** * Returns a string representation of this queue. * @return the sequence of items in FIFO order, separated by spaces */ public String toString() { StringBuilder s = new StringBuilder(); for (Item item : this) s.append(item + " "); return s.toString(); } /** * Returns an iterator that iterates over the items in this queue in FIFO order. * @return an iterator that iterates over the items in this queue in FIFO order */ public Iterator<Item> iterator() { return new ListIterator<Item>(first); } // an iterator, doesn‘t implement remove() since it‘s optional private class ListIterator<Item> implements Iterator<Item> { private Node<Item> current; public ListIterator(Node<Item> first) { current = first; } public boolean hasNext() { return current != null; } public void remove() { throw new UnsupportedOperationException(); } public Item next() { if (!hasNext()) throw new NoSuchElementException(); Item item = current.item; current = current.next; return item; } } /** * Unit tests the <tt>Queue</tt> data type. */ public static void main(String[] args) { Queue<String> q = new Queue<String>(); while (!StdIn.isEmpty()) { String item = StdIn.readString(); if (!item.equals("-")) q.enqueue(item); else if (!q.isEmpty()) StdOut.print(q.dequeue() + " "); } StdOut.println("(" + q.size() + " left on queue)"); } }
【Stack.java】
import java.util.Iterator; import java.util.NoSuchElementException; public class Stack<Item> implements Iterable<Item> { private int N; // size of the stack private Node<Item> first; // top of stack // helper linked list class private static class Node<Item> { private Item item; private Node<Item> next; } /** * Initializes an empty stack. */ public Stack() { first = null; N = 0; } /** * Is this stack empty? * @return true if this stack is empty; false otherwise */ public boolean isEmpty() { return first == null; } /** * Returns the number of items in the stack. * @return the number of items in the stack */ public int size() { return N; } /** * Adds the item to this stack. * @param item the item to add */ public void push(Item item) { Node<Item> oldfirst = first; first = new Node<Item>(); first.item = item; first.next = oldfirst; N++; } /** * Removes and returns the item most recently added to this stack. * @return the item most recently added * @throws java.util.NoSuchElementException if this stack is empty */ public Item pop() { if (isEmpty()) throw new NoSuchElementException("Stack underflow"); Item item = first.item; // save item to return first = first.next; // delete first node N--; return item; // return the saved item } /** * Returns (but does not remove) the item most recently added to this stack. * @return the item most recently added to this stack * @throws java.util.NoSuchElementException if this stack is empty */ public Item peek() { if (isEmpty()) throw new NoSuchElementException("Stack underflow"); return first.item; } /** * Returns a string representation of this stack. * @return the sequence of items in the stack in LIFO order, separated by spaces */ public String toString() { StringBuilder s = new StringBuilder(); for (Item item : this) s.append(item + " "); return s.toString(); } /** * Returns an iterator to this stack that iterates through the items in LIFO order. * @return an iterator to this stack that iterates through the items in LIFO order. */ public Iterator<Item> iterator() { return new ListIterator<Item>(first); } // an iterator, doesn‘t implement remove() since it‘s optional private class ListIterator<Item> implements Iterator<Item> { private Node<Item> current; public ListIterator(Node<Item> first) { current = first; } public boolean hasNext() { return current != null; } public void remove() { throw new UnsupportedOperationException(); } public Item next() { if (!hasNext()) throw new NoSuchElementException(); Item item = current.item; current = current.next; return item; } } /** * Unit tests the <tt>Stack</tt> data type. */ public static void main(String[] args) { Stack<String> s = new Stack<String>(); while (!StdIn.isEmpty()) { String item = StdIn.readString(); if (!item.equals("-")) s.push(item); else if (!s.isEmpty()) StdOut.print(s.pop() + " "); } StdOut.println("(" + s.size() + " left on stack)"); } }
【Queue测试用例 QueueCase.java】
public class QueueCase { public static void main(String[] args) { int[] temp = readInts(name); for (int i = 0; i < temp.length; i++) System.out.println(temp[i] + " "); } public static int[] readInts(String name){ In in = new In(name); Queue<Integer> q = new Queue<Integer>(); while(!in.isEmpty()) q.enqueue(in.readInt()); int N = q.size(); int[] a = new int[N]; for (int i = 0; i < N; i++) a[i] = q.dequeue(); return a; } }
【Stack 测试用例 StackCase.java】
public class StackCase { public static void main(String[] args) { In in = new In(args[0]); Stack<Integer> s = new Stack<Integer>(); while(!StdIn.isEmpty()) s.push(StdIn.readInt()); for (int i : s) { System.out.println(i + " "); } } }